7 template<typename _Key, typename _Val>
11 struct hashlistnode<_Key,_Val> *next;
14 template<typename _Key, typename _Val, int _Shift>
17 HashTable(unsigned int initialcapacity, double factor) {
18 // Allocate space for the hash table
19 table = calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val> *));
21 capacity = initialcapacity;
22 threshold = initialcapacity*loadfactor;
23 mask = (capacity << _Shift)-1;
24 size = 0; // Initial number of elements in the hash
31 void insert(_Key key, _Val val) {
32 if(size > threshold) {
34 unsigned int newsize = capacity << 1;
38 struct hashlistnode<_Key,_Val> *ptr = table[(key & mask)>>_Shift];
40 struct hashlistnode<_Key,_Val> *search = ptr;
43 if (search->key==key) {
50 struct hashlistnode<_Key,_Val> *newptr=malloc(sizeof(struct hashlistnode<_Key,_Val>));
54 table[(key&mask)>>_Shift]=newptr;
58 struct hashlistnode<_Key,_Val> *search = table[(key & mask)>>_Shift];
61 if (search->key==key) {
69 void resize(unsigned int newsize) {
70 struct hashlistnode<_Key,_Val> ** oldtable = table;
71 struct hashlistnode<_Key,_Val> ** newtable;
72 unsigned int oldcapacity = capacity;
74 if((newtable = calloc(newsize, sizeof(struct hashlistnode<_Key,_Val> *))) == NULL) {
75 printf("Calloc error %s %d\n", __FILE__, __LINE__);
79 table = newtable; //Update the global hashtable upon resize()
81 threshold = newsize * loadfactor;
82 mask = (newsize << _Shift)-1;
84 for(unsigned int i = 0; i < oldcapacity; i++) {
85 struct hashlistnode<_Key, _Val> * bin = oldtable[i];
89 struct hashlistnode<_Key, _Val> * next=bin->next;
91 unsigned int index = (key & mask) >>_Shift;
92 struct hashlistnode<_Key, _Val> tmp=newtable[index];
99 free(oldtable); //Free the memory of the old hash table
103 struct hashlistnode<_Key,_Val> **table;
104 unsigned int capacity;
107 unsigned int threshold;