fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3.  
  4. class HashElement
  5. {
  6. private:
  7.     int key_;
  8.     std::string value_;
  9. public:
  10.     HashElement(int, std::string);
  11.     ~HashElement();
  12.     HashElement *next_element_;
  13.     int GetKey();
  14.     std::string GetValue();
  15. };
  16.  
  17. class HashMap
  18. {
  19. private:
  20.     HashElement **map_;
  21.     int size_;
  22.     int count_;
  23. public:
  24.     HashMap(int);
  25.     ~HashMap();
  26.     int GetHash(int);
  27.     void Put(int, std::string);
  28.     std::string GetElement(int);
  29.     bool Contains(int);
  30.     void Remove(int);
  31.     int GetCount();
  32. };
  33.  
  34. namespace PrimeChecker
  35. {
  36.     //This method was adapted from http://e...content-available-to-author-only...a.org/wiki/Primality_test
  37.     bool IsPrime(int number)
  38.     {
  39.         if (number <= 3) {
  40.             return number > 1;
  41.         }
  42.         else if (number % 2 == 0 || number % 3 == 0) {
  43.             return false;
  44.         }
  45.         else {
  46.             for (unsigned short i = 5; i * i <= number; i += 6) {
  47.                 if (number % i == 0 || number % (i + 2) == 0) {
  48.                     return false;
  49.                 }
  50.             }
  51.             return true;
  52.         }
  53.     }
  54. }
  55.  
  56. HashElement::HashElement(int key, std::string value)
  57. {
  58.     key_ = key;
  59.     value_ = value;
  60.     next_element_ = nullptr;
  61. }
  62.  
  63. HashElement::~HashElement()
  64. {
  65. }
  66.  
  67. int HashElement::GetKey(){
  68.     return key_;
  69. }
  70.  
  71. std::string HashElement::GetValue(){
  72.     return value_;
  73. }
  74.  
  75.  
  76. HashMap::HashMap(int size)
  77. {
  78.     while (!PrimeChecker::IsPrime(size)){
  79.         size++;
  80.     }
  81.     size_ = size;
  82.     map_ = new HashElement*[size_]();
  83. }
  84.  
  85. HashMap::~HashMap()
  86. {
  87.     for (int i = 0; i < size_; i++){
  88.         int hash = GetHash(i);
  89.         if (!map_[hash]){
  90.             continue;
  91.         }
  92.         HashElement *current_element = map_[hash];
  93.         HashElement *next_element = map_[hash];
  94.         while (next_element->next_element_){
  95.             next_element = next_element->next_element_;
  96.             delete current_element;
  97.             current_element = next_element;
  98.         }
  99.         delete current_element;
  100.     }
  101. }
  102.  
  103. int HashMap::GetHash(int key){
  104.     return key % size_;
  105. }
  106.  
  107. void HashMap::Put(int key, std::string value){
  108.     int hash = GetHash(key);
  109.     if (!map_[hash]){
  110.         map_[hash] = new HashElement(key, value);
  111.     }
  112.     else{
  113.         HashElement *last_element = map_[hash];
  114.         while (last_element->next_element_){
  115.             last_element = last_element->next_element_;
  116.         }
  117.         last_element->next_element_ = new HashElement(key, value);
  118.     }
  119.     count_++;
  120. }
  121.  
  122. std::string HashMap::GetElement(int key){
  123.     int hash = GetHash(key);
  124.     if (map_[hash]){
  125.         HashElement *current_element = map_[hash];
  126.         while (current_element->GetKey() != key && current_element->next_element_){
  127.             current_element = current_element->next_element_;
  128.         }
  129.         return current_element->GetValue();
  130.     }
  131.     return nullptr;
  132. }
  133.  
  134. bool HashMap::Contains(int key){
  135.     int hash = GetHash(key);
  136.     if (map_[hash]){
  137.         HashElement *current_element = map_[hash];
  138.         while (current_element->GetKey() != key && current_element->next_element_){
  139.             current_element = current_element->next_element_;
  140.         }
  141.         if (current_element->GetKey() == key){
  142.             return true;
  143.         }
  144.     }
  145.     return false;
  146. }
  147.  
  148. void HashMap::Remove(int key){
  149.     if (!Contains(key)){
  150.         return;
  151.     }
  152.     int hash = GetHash(key);
  153.     HashElement *current_element = map_[hash];
  154.     if (current_element->GetKey() == key){
  155.         map_[hash] = current_element->next_element_;
  156.         delete current_element;
  157.     }
  158.     else{
  159.         HashElement *previous_element = current_element;
  160.         current_element = current_element->next_element_;
  161.         while (current_element->GetKey() != key){
  162.             previous_element = current_element;
  163.             current_element = current_element->next_element_;
  164.         }
  165.         previous_element->next_element_ = current_element->next_element_;
  166.         delete current_element;
  167.     }
  168.     count_--;
  169. }
  170.  
  171. int HashMap::GetCount(){
  172.     return count_;
  173. }
  174.  
  175. int main(void) {
  176. 	// your code goes here
  177. 	HashMap map(5);
  178. 	map.Put(1, "1");
  179. 	std::cout << "Get(1): " << map.GetElement(1) << "\n";
  180. 	std::cout << "Get(6): " << map.GetElement(6) << "\n";
  181.  
  182. 	return 0;
  183. }
  184.  
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Get(1): 1
Get(6): 1
https://ideone.com/oz5WSy
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!