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, int _Shift>
  15         class HashTable {
  16  public:
  17         HashTable(unsigned int initialcapacity, double factor) {
  18                 // Allocate space for the hash table
  19                 table = 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                 free(table);
  29         }
  30
  31         void insert(_Key key, _Val val) {
  32                 if(size > threshold) {
  33                         //Resize
  34                         unsigned int newsize = capacity << 1;
  35                         resize(newsize);
  36                 }
  37
  38                 struct hashlistnode<_Key,_Val> *ptr = table[(key & mask)>>_Shift];
  39                 size++;
  40                 struct hashlistnode<_Key,_Val> *search = ptr;
  41
  42                 while(search!=NULL) {
  43                         if (search->key==key) {
  44                                 search->val=val;
  45                                 return;
  46                         }
  47                         search=search->next;
  48                 }
  49
  50                 struct hashlistnode<_Key,_Val> *newptr=malloc(sizeof(struct hashlistnode<_Key,_Val>));
  51                 newptr->key=key;
  52                 newptr->val=val;
  53                 newptr->next=ptr;
  54                 table[(key&mask)>>_Shift]=newptr;
  55         }
  56
  57         _Val get(_Key key) {
  58                 struct hashlistnode<_Key,_Val> *search = table[(key & mask)>>_Shift];
  59
  60                 while(search!=NULL) {
  61                         if (search->key==key) {
  62                                 return search->val;
  63                         }
  64                         search=search->next;
  65                 }
  66                 return (_Val)0;
  67         }
  68
  69         void resize(unsigned int newsize) {
  70                 struct hashlistnode<_Key,_Val> ** oldtable = table;
  71                 struct hashlistnode<_Key,_Val> ** newtable;
  72                 unsigned int oldcapacity = capacity;
  73
  74                 if((newtable = calloc(newsize, sizeof(struct hashlistnode<_Key,_Val> *))) == NULL) {
  75                         printf("Calloc error %s %d\n", __FILE__, __LINE__);
  76                         exit(-1);
  77                 }
  78
  79                 table = newtable;          //Update the global hashtable upon resize()
  80                 capacity = newsize;
  81                 threshold = newsize * loadfactor;
  82                 mask = (newsize << _Shift)-1;
  83
  84                 for(unsigned int i = 0; i < oldcapacity; i++) {
  85                         struct hashlistnode<_Key, _Val> * bin = oldtable[i];
  86
  87                         while(bin!=NULL) {
  88                                 _Key key=bin->key;
  89                                 struct hashlistnode<_Key, _Val> * next=bin->next;
  90
  91                                 unsigned int index = (key & mask) >>_Shift;
  92                                 struct hashlistnode<_Key, _Val> tmp=newtable[index];
  93                                 bin->next=tmp;
  94                                 newtable[index]=bin;
  95                                 bin = next;
  96                         }
  97                 }
  98
  99                 free(oldtable);            //Free the memory of the old hash table
 100         }
 101
 102  private:
 103         struct hashlistnode<_Key,_Val> **table;
 104         unsigned int capacity;
 105         _Key mask;
 106         unsigned int size;
 107         unsigned int threshold;
 108         double loadfactor;
 109 };
 110 #endif