哈希表

  1 #include<iostream>  
  2 #include<vector>  
  3 #include<string>  
  4 using namespace std;
  5 template<class K, class V>
  6 struct Node
  7 {
  8     K _key;
  9     V _value;
 10     Node*_next;
 11     Node(const K& key, const V& value)
 12         :_key(key)
 13         ,_value(value)
 14         ,_next(NULL)
 15     {}
 16 };
 17 template<class T>
 18 struct Hasher
 19 {
 20     size_t operator() (const T& key)
 21     {
 22         return key;
 23     }
 24 };
 25 
 26 template<>
 27 struct Hasher<string>
 28 {
 29     size_t operator() (const string& s)
 30     {
 31         const char* str = s.c_str();
 32 
 33         unsigned int seed = 131; // 31 131 1313 13131 131313  
 34         unsigned int hash = 0;
 35         while (*str)
 36         {
 37             hash = hash * seed + (*str++);
 38         }
 39 
 40         return (hash & 0x7FFFFFFF);
 41     }
 42 };
 43 
 44 const int _PrimeSize = 28;
 45 static const unsigned long _PrimeList[_PrimeSize] =
 46 {
 47     53ul, 97ul, 193ul, 389ul, 769ul,
 48     1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
 49     49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
 50     1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
 51     50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
 52     1610612741ul, 3221225473ul, 4294967291ul
 53 };
 54 template<class K, class V, class HashFunc = Hasher<K>>
 55 class HashTable
 56 {
 57 public:
 58     HashTable(size_t capacity)
 59     {
 60         _size = 0;
 61         _table.reserve(capacity);
 62         _table.assign(capacity, NULL);
 63     }
 64     void Insert(const K& key, const V& value)//放入数据  
 65     {
 66         ExpandCapacity();
 67 
 68         int pos = _HashFunc(key, _table.size());
 69         Node<K, V>*begin = _table[pos];
 70         while (begin != NULL)
 71         {
 72             if (begin->_key == key)
 73             {
 74                 return;
 75             }
 76             begin = begin->_next;
 77         }
 78         Node<K, V>*tmp = new Node<K, V>(key, value);
 79         tmp->_next = _table[pos];
 80         _table[pos] = tmp;
 81         ++_size;
 82     }
 83     void Delete(const int&key)//删除结点  
 84     {
 85         size_t pos = (size_t)key % (size_t)_table.capacity();
 86         Node*begin = _table[pos];
 87         Node*prev = NULL;
 88         while (begin)
 89         {
 90             if (begin->_key == key)
 91             {
 92                 if (begin == _table[pos])
 93                 {
 94                     _table[pos] = _table[pos]->_next;
 95                 }
 96                 else
 97                 {
 98                     prev->_next = begin->_next;
 99                 }
100                 delete begin;
101                 return;
102             }
103             prev = begin;
104             begin = begin->_next;
105         }
106     }
107     void Print()
108     {
109         for (int i = 24; i <(int)_table.capacity(); i++)
110         {
111             Node<K, V>*begin = _table[i];
112             while (begin != NULL)
113             {
114                 printf("pos[%d]:", i);
115                 cout << "(" << begin->_key << "," << begin->_value << ")";
116                 cout << "->";
117                 begin = begin->_next;
118             }
119             cout << "NULL" << endl;
120         }
121     }
122 
123 protected:
124     void ExpandCapacity()//实现扩容  
125     {
126         if (_size >= (size_t)_table.capacity())
127         {
128             int NewCapacity = CapacityNum(_size);
129             vector<Node<K, V> *>tmp;
130             tmp.reserve(NewCapacity);
131             tmp.assign(NewCapacity, NULL);
132             for (size_t i = 0; i < (size_t)_table.capacity(); i++)
133             {
134                 while (_table[i] != NULL)
135                 {
136                     //摘节点  
137                     Node<K, V>* head = _table[i];
138                     _table[i] = _table[i]->_next;
139 
140                     //放节点  
141                     int pos = _HashFunc((head->_key), NewCapacity);
142                     head->_next = tmp[pos];
143                     tmp[pos] = head;
144                 }
145             }
146             _table.swap(tmp);
147         }
148     }
149     size_t CapacityNum(size_t num) //得到应该扩展到的容量值  
150     {
151         for (int i = 0; i < _PrimeSize; i++)
152         {
153             if (_PrimeList[i]>num)
154             {
155                 return _PrimeList[i];
156             }
157         }
158         return _PrimeList[_PrimeSize - 1];
159     }
160 
161     int _HashFunc(const K& key, size_t capacity)
162     {
163         HashFunc hashFunc; // operator()  
164         return hashFunc(key) % _table.capacity();
165 
166     }
167 private:
168     vector<Node<K, V>*>_table;
169     size_t _size;
170 };
171 int main()
172 {
173     system("pause");
174     return 0;
175 }