fork(1) download
copy 
  1. /**
  2.  * Hash Table with open addressing, linear probing.
  3.  * http://e...content-available-to-author-only...a.org/wiki/Hash_table#Open_addressing
  4.  *
  5.  * INPUT: rows of the format:
  6.  *   <command> <args>
  7.  * available commands:
  8.  *   insert <string> <int>
  9.  *   remove <string>
  10.  *   get <string>
  11.  *   print
  12.  *   reset <int>
  13.  *
  14.  * Author: Erel Segal  http://t...content-available-to-author-only...s.fm/rentabrain
  15.  * Date: 2010-10-13 
  16.  */
  17.  
  18. #include <string>
  19. #include <iostream>
  20. using namespace std;
  21.  
  22. template <typename T,typename K> struct HashTableNode {
  23.   K key;
  24.   T value;
  25.   bool isEmpty, isRemoved;
  26.  
  27.   HashTableNode<T,K>() { isEmpty=true; isRemoved=false; }
  28.   HashTableNode<T,K>(K newKey, T newValue) { set(newKey,newValue); }
  29.  
  30.   void set(K newKey, T newValue) {
  31.     key=newKey;
  32.     value=newValue;
  33.     isEmpty=isRemoved=false;
  34.   }
  35.  
  36.   void remove() {
  37.     isRemoved=true;
  38.   }
  39. };
  40.  
  41.  
  42.  
  43. /**
  44.  * A hash table with open addressing, linear probing.
  45.  * PARAMETERS:
  46.  *   T - type of values stored in hash.
  47.  *   K - type of keys by which the values are stored.
  48.  *   hash - a hash function that gets a key and the table size m, and returns 
  49.  *          an integer in 0...m-1
  50.  */
  51. template <typename T, typename K, int HASH(K, int)> class HashTable {
  52.   HashTableNode<T,K>* myTable;
  53.   int mySize;
  54.  
  55.   int hashFunction(K key, int baseHashValue, int trialNumber) {
  56.     return (baseHashValue + trialNumber) % mySize;
  57.   }
  58. public:
  59.  
  60.   void reset(int newSize) { 
  61.     if (myTable) delete[] myTable;
  62.     myTable = new HashTableNode<T,K>[newSize]; 
  63.     mySize = newSize;
  64.   }
  65.   HashTable<T,K,HASH> (int newSize=10): myTable(NULL) { reset(newSize); }
  66.   ~HashTable<T,K,HASH> () { 
  67.      // if (myTable) delete[] myTable; // runtime error!
  68.    }
  69.  
  70.  
  71.   /**
  72.    * Look for the given key in the hash.
  73.    * If it exists - return a pointer to the matching value.
  74.    * Otherwise - return NULL.
  75.    */
  76.   T* get (K key) {
  77.     int baseHashValue = HASH(key,mySize);
  78.     for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
  79.       int hashValue = hashFunction(key, baseHashValue, trialNumber);
  80.       if (myTable[hashValue].isEmpty) {
  81.         return NULL;      // not found
  82.       }
  83.       if (myTable[hashValue].key==key) {
  84.         if (myTable[hashValue].isRemoved) {
  85.           return NULL;    // found but deleted
  86.         } else {
  87.           return &myTable[hashValue].value;
  88.         }
  89.       }
  90.     }
  91.     return NULL; // not found
  92.   }
  93.  
  94.  
  95.  
  96.   /**
  97.    * Insert the given value to the table, under the given key.
  98.    */
  99.   void insert (K key, T value) {
  100.     int baseHashValue = HASH(key,mySize);
  101.     for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
  102.       int hashValue = hashFunction(key, baseHashValue, trialNumber);
  103.       if (myTable[hashValue].isEmpty || myTable[hashValue].isRemoved || myTable[hashValue].key==key) {
  104.         // found a place to insert:
  105.         myTable[hashValue].set(key,value);
  106.         return;
  107.       }
  108.     }
  109.  
  110.     // could not find a place to insert:
  111.     throw string("Hash Table overflow");
  112.   }
  113.  
  114.  
  115.   /**
  116.    * Look for the given key in the hash.
  117.    * If it exists - remove it.
  118.    * Otherwise - return NULL.
  119.    */
  120.   void remove (K key) {
  121.     int baseHashValue = HASH(key,mySize);
  122.     for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
  123.       int hashValue = hashFunction(key, baseHashValue, trialNumber);
  124.       if (myTable[hashValue].isEmpty) {
  125.         return;      // not found
  126.       }
  127.       if (myTable[hashValue].key==key) {
  128.         myTable[hashValue].remove();
  129.         return;
  130.       }
  131.     }
  132.   }
  133.  
  134.  
  135.  
  136.   friend ostream& operator<< (ostream& out, const HashTable<T,K,HASH> theHash) {
  137.     out << "{ ";
  138.     for (int i=0; i<theHash.mySize; ++i) {
  139.       if (!theHash.myTable[i].isEmpty && !theHash.myTable[i].isRemoved) {
  140.          out << "  (" << i << ") "
  141.              << theHash.myTable[i].key << " -> "
  142.              << theHash.myTable[i].value << ", ";
  143.       }
  144.     }
  145.     out << " }";
  146.     return out;
  147.   }
  148.  
  149.  
  150. };  // template class HashTable<T,K,HASH>
  151.  
  152.  
  153.  
  154. /**
  155.  * calculate a hash value for a string - convert the string to a number modulu the given base
  156.  */
  157. int string2number(string str, int modulu) {
  158.   int num=0;
  159.   for (size_t i=0; i<str.length(); ++i) {
  160.     num = (num*256 + str[i])%modulu;
  161.   }
  162.   return num;
  163. }
  164.  
  165.  
  166. int main() {
  167.   HashTable<int, string, &string2number> mapWordToNumber;
  168.   cout << mapWordToNumber << endl;
  169.   string command, word;
  170.   int number;
  171.   for (;;) {
  172.     cin >> command;
  173.     if (cin.eof()) return 0;
  174.     try {
  175.       if (command=="reset") {
  176.         cin >> number;
  177.         cout << command << " " << number << ":" << endl;
  178.         mapWordToNumber.reset(number);
  179.       } else if (command=="insert") {
  180.         cin >> word >> number;
  181.         cout << command << " " << word << " " << number << ":" << endl;
  182.         mapWordToNumber.insert(word,number);
  183.       } else if (command=="remove") {
  184.         cin >> word;
  185.         cout << command << " " << word << ":" << endl;
  186.         mapWordToNumber.remove(word);
  187.       } else if (command=="get") {
  188.         cin >> word;
  189.         cout << command << " " << word << ":";
  190.         int* value = mapWordToNumber.get(word);
  191.         if (value==NULL)
  192.           cout << "doesn't exist!";
  193.         else
  194.           cout << *value;
  195.         cout << endl;
  196.       } else if (command=="print") {
  197.         cout << mapWordToNumber << endl;
  198.       }
  199.     } catch (string error) {
  200.       cout << "ERROR: " << error << endl;
  201.     }
  202.   }
  203. }
  204.  
  205.  
Success #stdin #stdout 0s 2868KB
comments (?)
stdin
copy 
reset 100
print
insert a 1
insert aa 2
insert aaa 3
get a
get aa
get aaa
get aaaa
insert aaaa 4
print
insert c 1
insert cc 2
insert ccc 3
insert cccc 4
print
insert a 6
insert aa 7
insert aaa 8
insert aaaa 9
get a
get aa
get aaa
get aaaa
print
remove a
remove aa
remove aaa
get a
get aa
get aaa
get aaaa
remove aaaa
get c
get cc
get ccc
get cccc
print
insert a 7
insert aa 7
insert aaa 7
get a
get aa
get aaa
get aaaa
insert aaaa 7
print



reset 10
print
print
print
insert a 1
insert aa 2
insert aaa 3
get a
get aa
get aaa
get aaaa
insert aaaa 4
print
insert c 1
insert cc 2
insert ccc 3
insert cccc 4
print
insert a 6
insert aa 7
insert aaa 8
insert aaaa 9
get a
get aa
get aaa
get aaaa
print
remove a
remove aa
remove aaa
get a
get aa
get aaa
get aaaa
remove aaaa
get c
get cc
get ccc
get cccc
print
insert a 7
insert aa 7
insert aaa 7
get a
get aa
get aaa
get aaaa
insert aaaa 7
get c
get cc
get ccc
get cccc
print
stdout
copy 
{  }
reset 100:
{  }
insert a 1:
insert aa 2:
insert aaa 3:
get a:1
get aa:2
get aaa:3
get aaaa:doesn't exist!
insert aaaa 4:
{   (21) aaa -> 3,   (29) aa -> 2,   (73) aaaa -> 4,   (97) a -> 1,  }
insert c 1:
insert cc 2:
insert ccc 3:
insert cccc 4:
{   (7) ccc -> 3,   (21) aaa -> 3,   (29) aa -> 2,   (43) cc -> 2,   (73) aaaa -> 4,   (91) cccc -> 4,   (97) a -> 1,   (99) c -> 1,  }
insert a 6:
insert aa 7:
insert aaa 8:
insert aaaa 9:
get a:6
get aa:7
get aaa:8
get aaaa:9
{   (7) ccc -> 3,   (21) aaa -> 8,   (29) aa -> 7,   (43) cc -> 2,   (73) aaaa -> 9,   (91) cccc -> 4,   (97) a -> 6,   (99) c -> 1,  }
remove a:
remove aa:
remove aaa:
get a:doesn't exist!
get aa:doesn't exist!
get aaa:doesn't exist!
get aaaa:9
remove aaaa:
get c:1
get cc:2
get ccc:3
get cccc:4
{   (7) ccc -> 3,   (43) cc -> 2,   (91) cccc -> 4,   (99) c -> 1,  }
insert a 7:
insert aa 7:
insert aaa 7:
get a:7
get aa:7
get aaa:7
get aaaa:doesn't exist!
insert aaaa 7:
{   (7) ccc -> 3,   (21) aaa -> 7,   (29) aa -> 7,   (43) cc -> 2,   (73) aaaa -> 7,   (91) cccc -> 4,   (97) a -> 7,   (99) c -> 1,  }
reset 10:
{  }
{  }
{  }
insert a 1:
insert aa 2:
insert aaa 3:
get a:1
get aa:2
get aaa:3
get aaaa:doesn't exist!
insert aaaa 4:
{   (1) aaa -> 3,   (3) aaaa -> 4,   (7) a -> 1,   (9) aa -> 2,  }
insert c 1:
insert cc 2:
insert ccc 3:
insert cccc 4:
{   (0) c -> 1,   (1) aaa -> 3,   (2) cccc -> 4,   (3) aaaa -> 4,   (4) cc -> 2,   (7) a -> 1,   (8) ccc -> 3,   (9) aa -> 2,  }
insert a 6:
insert aa 7:
insert aaa 8:
insert aaaa 9:
get a:6
get aa:7
get aaa:8
get aaaa:9
{   (0) c -> 1,   (1) aaa -> 8,   (2) cccc -> 4,   (3) aaaa -> 9,   (4) cc -> 2,   (7) a -> 6,   (8) ccc -> 3,   (9) aa -> 7,  }
remove a:
remove aa:
remove aaa:
get a:doesn't exist!
get aa:doesn't exist!
get aaa:doesn't exist!
get aaaa:9
remove aaaa:
get c:1
get cc:2
get ccc:3
get cccc:4
{   (0) c -> 1,   (2) cccc -> 4,   (4) cc -> 2,   (8) ccc -> 3,  }
insert a 7:
insert aa 7:
insert aaa 7:
get a:7
get aa:7
get aaa:7
get aaaa:doesn't exist!
insert aaaa 7:
get c:1
get cc:2
get ccc:3
get cccc:4
{   (0) c -> 1,   (1) aaa -> 7,   (2) cccc -> 4,   (3) aaaa -> 7,   (4) cc -> 2,   (7) a -> 7,   (8) ccc -> 3,   (9) aa -> 7,  }
https://ideone.com/PfJlC
language:
C++ (gcc 8.3)
created:
13 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!