hashtable.h

   1 #ifndef HASHTABLE_H
   2 #define HASHTABLE_H
   3
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6
   7 template<typename _Key, typename _Val>
   8         struct hashlistnode {
   9                 _Key key;
  10                 _Val val;
  11                 struct hashlistnode<_Key,_Val> *next;
  12         };
  13
  14 template<typename _Key, typename _Val, typename _KeyInt, int _Shift>
  15         class HashTable {
  16  public:
  17         HashTable(unsigned int initialcapacity=1024, double factor=0.5) {
  18                 // Allocate space for the hash table
  19                 table = (struct hashlistnode<_Key,_Val> **) calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val> *));
  20                 loadfactor = factor;
  21                 capacity = initialcapacity;
  22                 threshold = initialcapacity*loadfactor;
  23                 mask = (capacity << _Shift)-1;
  24                 size = 0; // Initial number of elements in the hash
  25         }
  26
  27         ~HashTable() {
  28                 for(unsigned int i=0;i<capacity;i++) {
  29                         struct hashlistnode<_Key,_Val> * bin = table[i];
  30                         while(bin!=NULL) {
  31                                 struct hashlistnode<_Key,_Val> * next=bin->next;
  32                                 free(bin);
  33                                 bin=next;
  34                         }
  35                 }
  36                 free(table);
  37         }
  38
  39         void reset() {
  40                 for(int i=0;i<capacity;i++) {
  41                         struct hashlistnode<_Key,_Val> * bin = table[i];
  42                         while(bin!=NULL) {
  43                                 struct hashlistnode<_Key,_Val> * next=bin->next;
  44                                 free(bin);
  45                                 bin=next;
  46                         }
  47                 }
  48                 memset(table, 0, capacity*sizeof(struct hashlistnode<_Key, _Val> *));
  49                 size=0;
  50         }
  51
  52         void put(_Key key, _Val val) {
  53                 if(size > threshold) {
  54                         //Resize
  55                         unsigned int newsize = capacity << 1;
  56                         resize(newsize);
  57                 }
  58
  59                 struct hashlistnode<_Key,_Val> *ptr = table[(((_KeyInt)key) & mask)>>_Shift];
  60                 size++;
  61                 struct hashlistnode<_Key,_Val> *search = ptr;
  62
  63                 while(search!=NULL) {
  64                         if (search->key==key) {
  65                                 search->val=val;
  66                                 return;
  67                         }
  68                         search=search->next;
  69                 }
  70
  71                 struct hashlistnode<_Key,_Val> *newptr=(struct hashlistnode<_Key,_Val> *)malloc(sizeof(struct hashlistnode<_Key,_Val>));
  72                 newptr->key=key;
  73                 newptr->val=val;
  74                 newptr->next=ptr;
  75                 table[(((_KeyInt)key)&mask)>>_Shift]=newptr;
  76         }
  77
  78         _Val get(_Key key) {
  79                 struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift];
  80
  81                 while(search!=NULL) {
  82                         if (search->key==key) {
  83                                 return search->val;
  84                         }
  85                         search=search->next;
  86                 }
  87                 return (_Val)0;
  88         }
  89
  90         bool contains(_Key key) {
  91                 struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift];
  92
  93                 while(search!=NULL) {
  94                         if (search->key==key) {
  95                                 return true;
  96                         }
  97                         search=search->next;
  98                 }
  99                 return false;
 100         }
 101
 102         void resize(unsigned int newsize) {
 103                 struct hashlistnode<_Key,_Val> ** oldtable = table;
 104                 struct hashlistnode<_Key,_Val> ** newtable;
 105                 unsigned int oldcapacity = capacity;
 106
 107                 if((newtable = (struct hashlistnode<_Key,_Val> **) calloc(newsize, sizeof(struct hashlistnode<_Key,_Val> *))) == NULL) {
 108                         printf("Calloc error %s %d\n", __FILE__, __LINE__);
 109                         exit(-1);
 110                 }
 111
 112                 table = newtable;          //Update the global hashtable upon resize()
 113                 capacity = newsize;
 114                 threshold = newsize * loadfactor;
 115                 mask = (newsize << _Shift)-1;
 116
 117                 for(unsigned int i = 0; i < oldcapacity; i++) {
 118                         struct hashlistnode<_Key, _Val> * bin = oldtable[i];
 119
 120                         while(bin!=NULL) {
 121                                 _Key key=bin->key;
 122                                 struct hashlistnode<_Key, _Val> * next=bin->next;
 123
 124                                 unsigned int index = (((_KeyInt)key) & mask) >>_Shift;
 125                                 struct hashlistnode<_Key, _Val> * tmp=newtable[index];
 126                                 bin->next=tmp;
 127                                 newtable[index]=bin;
 128                                 bin = next;
 129                         }
 130                 }
 131
 132                 free(oldtable);            //Free the memory of the old hash table
 133         }
 134
 135  private:
 136         struct hashlistnode<_Key,_Val> **table;
 137         unsigned int capacity;
 138         _KeyInt mask;
 139         unsigned int size;
 140         unsigned int threshold;
 141         double loadfactor;
 142 };
 143 #endif