Implement HashMap

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

class LinkedHashEntry{ public: int key; int value; LinkedHashEntry *next; LinkedHashEntry(int k, int v):key(k), value(v), next(NULL){} }; class HashMap{ public: int sz; LinkedHashEntry ** table; HashMap(int s):sz(s){ table = new LinkedHashEntry *[sz]; for(int i=0; i<sz; ++i){ table[i] = NULL; } } void set(int key, int value){ int index = key%sz; LinkedHashEntry *entry = table[index]; if(entry == NULL){ table[index] = new LinkedHashEntry(key, value); }else{ LinkedHashEntry *prev; while(entry && entry->key != key){ prev = entry; entry = entry->next; } if(!entry){ prev->next = new LinkedHashEntry(key, value); }else{ entry->value = value; } } } int get(int key){ int index = key%sz; LinkedHashEntry *entry = table[index]; if(entry == NULL){ cout<<"not exist\n"; }else{ while(entry && entry->key != key){ entry = entry->next; } if(entry){ return entry->value; }else{ cout<<"not exist\n"; } } return -1; } void resize(){ int old_sz = sz; sz = sz*2; LinkedHashEntry ** old_table = table; table = new LinkedHashEntry *[sz]; for(int i=0; i<sz; ++i) table[i] = NULL; for(int i=0; i<old_sz; ++i){ LinkedHashEntry *entry = old_table[i]; while(entry){ set(entry->key, entry->value); LinkedHashEntry * old_entry = entry; entry = entry->next; delete old_entry; } } } };

Output:
64
256
not exist
-1
new size is 256
64
256
not exist
-1

Ref
[1] http://www.algolist.net/Data_structures/Hash_table/Chaining
[2] http://www.algolist.net/Data_structures/Hash_table/Dynamic_resizing