Implement Hash

来源：Bloomberg面试题

原帖：http://www.cnblogs.com/xiekeli/archive/2012/01/13/2321207.html
            http://www.cnblogs.com/xiekeli/archive/2012/01/16/2323391.html

题目：
Hash表的简单实现可以作为一个好的练习和理解hash结构。使用拉链法实现hash。

代码：

 struct Node {  
   string key;  
   string val;  
   Node* next;  
   Node() {};  
   Node(string k, string v) : key(k), val(v) {}  
 };  
   
 const int HASHSIZE = 10001; // Hashsize; bucket size  
 const int CAPACITY = 1205; // 哈希能够装载最大的容量，一定大于最大元素个数, capacity; < hashsize;  
   
 class Hash {  
 public:  
   Hash() : node(CAPACITY), table(HASHSIZE,NULL), size(0) {}  
   
   bool insert(string k, string v) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) return false;  
       cur = cur->next;  
     }  
     node[size] = Node(k,v);  
     node[size].next = table[code];  
     table[code] = &node[size++];  
     return true;  
   }  
   
   bool find(string k) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) return true;  
       cur = cur->next;  
     }  
     return false;  
   }  
   
   const string& operator[](string k) const {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) {  
         return cur->val;  
       }  
       cur = cur->next;  
     }  
   }  
   
   string& operator[](string k) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) {  
         return cur->val;  
       }  
       cur = cur->next;  
     }  
   }  
   
 private:  
   int hashcode(const string& s) const {  
     unsigned int hash = 0;  
     for (auto i : s) {  
       hash = hash * + i;  
     }  
     return (hash & 0x7FFFFFFF) % HASHSIZE;  
   }  
   
   static const int seed = 131;   
   int size;  
   vector<Node> node;  
   vector<Node*> table;  
 };  
   
   
 int main() {  
   Hash hash;  
   hash.insert("tiger", "1");  
   hash.insert("monkey", "2");  
   hash.insert("cat", "3");  
   
   if (hash.find("tiger")) {  
     cout << "find the animal" << endl;  
   } else {  
     cout << "not find the animal" << endl;  
   }  
     
   cout << hash["tiger"] << endl;  
   return 0;  
 }