hashtable简单实现
本文中实现了一个简单的hashtable，不一定实用，但是反应出了hashtable的原理，而且若是面试中让实现一个hashtable，本文的实现足以应付，我在一次迅雷的面试中就遇到，让实现一个hashtable。
本文中采用开链法（separate chaining）来处理“冲突”（collision），而且hashtable只存储唯一的元素，不存在重复。
实现代码如下：
class hashtable{public:// 构造函数，n为想要构造的hashtable的bucket数量hashtable(size_t n);~hashtable();// 插入元素。若元素不存在，插入成功返回true；若元素已存在则插入失败，返回falsebool insert(const int val);// 查找元素是否在表中出现bool find(const int val);// 删除元素。若元素存在，删除成功返回true；若元素不存在则删除失败，返回falsebool erase(const int val);// 清除所有元素void clear();// 返回已有元素数目size_t size();private:// bucket中的节点struct hashtable_node{hashtable_node *next;int val;hashtable_node(int _val, hashtable_node *_next = NULL):val(_val), next(_next){};};// hash函数size_t hash(unsigned int long x);// 寻找大于等于n且最接近n的质数unsigned long next_prime(unsigned long n);// bucket向量表vector<hashtable_node*> buckets;// 元素个数size_t num_elements;};hashtable::hashtable(size_t n){// 将bucket数量设置为大于等于n且最接近n的质数const size_t n_buckets = next_prime(n);buckets.reserve(n_buckets);buckets.insert(buckets.end(), n_buckets, NULL);num_elements = 0;};hashtable::~hashtable(){// 清除所有链中的节点clear();}bool hashtable::insert(const int val){// 不重复插入。已存在，返回falseif(find(val)) return false;// 调用hash函数获得bucket号const size_t k = hash(val);// 将新节点直接插入到链表头部hashtable_node * tmp = new hashtable_node(val);tmp->next = buckets[k];buckets[k] = tmp;++num_elements;// 插入成功return true;}bool hashtable::find(const int val){const size_t k = hash(val);hashtable_node *p = buckets[k];// 在对应的bucket中查找while(p != NULL){if(p->val = val) return true;p = p->next;}return false;}bool hashtable::erase(const int val){const size_t k = hash(val);hashtable_node *p = buckets[k];hashtable_node *pre = NULL;// 找到该节点while(p != NULL && p->val != val){pre = p;p = p->next;}// 删除该节点if(p == NULL) return false;if(pre == NULL)buckets[k] = p->next;elsepre->next = p->next;delete p;return true;}void hashtable::clear(){// 清除所有链中的节点for(int i = 0; i < buckets.size(); i++){hashtable_node *p = buckets[i];while(p != NULL){hashtable_node *next = p->next;delete p;p = next;}}}size_t hashtable::size(){return num_elements;}size_t hashtable::hash(unsigned int long x){return x % buckets.size();}unsigned long hashtable::next_prime(unsigned long n){static const int num_primes = 28;static const unsigned long prime_list[num_primes] = {53, 97, 193, 389, 769,1543, 3079 , 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473ul, 4294967291ul };// 寻找大于等于n且最接近n的质数int i = 0;while(i < num_primes && prime_list[i] < n)i++;return i == num_primes ? prime_list[num_primes-1] : prime_list[i];}