随笔档案

  1 //
  2 //    HashTable
  3 //
  4 //    goonyangxiaofang(AT)163(DOT)com
  5 //    QQ: 五九一二四七八七六
  6 //
  7 
  8 #include <iostream>
  9 #include <string>
 10 
 11 #define MYTRACE(t, f) std::cout << #t": " << t << std::endl; if(f == 1) std::cin.get()
 12 #define PRINTNAME(name) std::cout << #name": " << std::endl
 13 
 14 template <typename Key, typename Data, unsigned int prime = 11>
 15 class HashTable
 16 {
 17     struct Node
 18     {
 19         Key   key;
 20         Data  data;
 21         Node* next;
 22         Node() : next(0) {}
 23         Node(const Key& k) : key(k), next(0) {}
 24         Node(const Key& k, const Data& d) : key(k), data(d), next(0) {}
 25         Node(const Key& k, const Data& d, const Node* p) : key(k), data(d), next(p) {}
 26         Node(const Node& n) : key(n.key), data(n.data), next(n.next) {}
 27         ~Node() {}
 28     };
 29     Node** table;
 30 private:
 31     unsigned int getKey(const Key& k)
 32     {
 33         unsigned int ret = 0;
 34         char* h = reinterpret_cast<char*>(const_cast<Key*>(&k));
 35         for (unsigned int i = 0; i < sizeof (Key); ++i)
 36         {
 37             ret += static_cast<unsigned int>(h[i]) * 10;
 38         }
 39         return ret % prime;
 40     }
 41 public:
 42     HashTable()
 43     {
 44         table = new Node*[prime];
 45         for (unsigned int i = 0; i < prime; ++i)
 46         {
 47             table[i] = 0;
 48         }
 49     }
 50     HashTable(const HashTable& ht)
 51     {
 52         table = new Node*[prime];
 53         for (unsigned int i = 0; i < prime; ++i)
 54         {
 55             table[i] = 0;
 56             Node** p = &(table[i]);
 57             Node*  q = ht.table[i];
 58             while (q)
 59             {
 60                 Node* r = new Node(q->key, q->data);
 61                 *p = r;
 62                 p = &(r->next);
 63                 q = q->next;
 64             }
 65         }
 66     }
 67     HashTable& operator=(const HashTable& ht)
 68     {
 69         if (this != &ht)
 70         {
 71             clear();
 72             table = new Node*[prime];
 73             for (unsigned int i = 0; i < prime; ++i)
 74             {
 75                 table[i] = 0;
 76                 Node** p = &table[i];
 77                 Node*  q = ht.table[i];
 78                 while (q)
 79                 {
 80                     Node* r = new Node(q->key, q->data);
 81                     *p = r;
 82                     p = &(r->next);
 83                     q = q->next;
 84                 }
 85             }
 86         }
 87         return * this;
 88     }
 89     bool find(const Key& k)
 90     {
 91         Node* p = table[getKey(k)];
 92         while (p)
 93         {
 94             if (k == p->key)
 95             {
 96                 return true;
 97             }
 98             p = p->next;
 99         }
100         return false;
101     }
102     bool insert(const Key& k, const Data& d)
103     {
104         if (find(k))
105         {
106             return true;
107         }
108         unsigned int key = getKey(k);
109         Node*& p = table[key];
110         Node* q = new Node(k, d);
111         if (q == 0)
112         {
113             return false;
114         }
115         q->next = p;
116         p = q;
117         return true;
118     }
119     bool insert(const Key& k)
120     {
121         if (find(k))
122         {
123             return true;
124         }
125         unsigned int key = getKey(k);
126         Node*& p = table[key];
127         Node* q = new Node(k);
128         if (q == 0)
129         {
130             return false;
131         }
132         q->next = p;
133         p = q;
134         return true;
135     }
136     Data& get(const Key& k)
137     {
138         Node* p = table[getKey(k)];
139         while (p)
140         {
141             if (k == p->key)
142             {
143                 return p->data;
144             }
145             p = p->next;
146         }
147         insert(k);
148         Data d;
149         return d;
150     }
151     const Data& operator[](const Key& k) const
152     {
153         Node* p = table[getKey(k)];
154         while (p)
155         {
156             if (k == p->key)
157             {
158                 return p->data;
159             }
160             p = p->next;
161         }
162         insert(k);
163         Data d;
164         return d;
165     }
166     Data& operator[](const Key& k)
167     {
168         Node* p = table[getKey(k)];
169         while (p)
170         {
171             if (k == p->key)
172             {
173                 return p->data;
174             }
175             p = p->next;
176         }
177         insert(k);
178         Data d;
179         return d;
180     }
181     bool empty()
182     {
183         for (unsigned int i = 0; i < prime; ++i)
184         {
185             if (table[i] != 0)
186             {
187                 return false;
188             }
189         }
190         return true;
191     }
192     void print()
193     {
194         std::cout << std::endl;
195         for (unsigned int i = 0; i < prime; ++i)
196         {
197             Node* p = table[i];
198             std::cout << i << ": ";
199             while (p)
200             {
201                 std::cout << "( " << p->key << ", " << p->data << " ) ";
202                 p = p->next;
203             }
204             std::cout << std::endl;
205         }
206         std::cout << std::endl;
207     }
208     void clear()
209     {
210         for (unsigned int i = 0; i < prime; ++i)
211         {
212             Node* p = table[i];
213             Node* q = p;
214             while (p)
215             {
216                 p = p->next;
217                 delete q;
218                 q = p;
219             }
220         }
221         delete [] table;
222     }
223     ~HashTable()
224     {
225         clear();
226     }
227 };
228 
229 int main()
230 {
231     HashTable<long, std::string> ht1;
232     for (long i = 0; i < 26; ++i)
233     {
234         std::string s;
235         s += 'A' + i;
236         ht1.insert(i, s);
237     }
238     PRINTNAME(ht1);
239     ht1.print();
240 
241     for (long i = 0; i < 26; ++i)
242     {
243         std::string s;
244         s += 'A' + i;
245         ht1.insert(i, s);
246     }
247     PRINTNAME(ht1);
248     ht1.print();
249 
250     HashTable<long, std::string> ht2(ht1);
251     PRINTNAME(ht2);
252     ht2.print();
253 
254     ht1[25] = "xxxxxxxx";
255     ht1.print();
256     ht2.print();
257 
258     HashTable<long, std::string> ht3;
259     ht3 = ht1;
260     PRINTNAME(ht3);
261     ht3.print();
262     return 0;
263 }