HashTable简单达成
发布时间：2021-11-21 19:57:14 所属栏目：教程 来源：互联网
导读：本文中实现了一个简单的hashtable，不一定实用，但是反应出了hashtable的原理，而且若是面试中让实现一个hashtable，本文的实现足以应付，我在一次迅雷的面试中就遇到，让实现一个hashtable。 本文中采用开链法（separate chaining）来处理冲突（collision）
|
本文中实现了一个简单的hashtable，不一定实用，但是反应出了hashtable的原理，而且若是面试中让实现一个hashtable，本文的实现足以应付，我在一次迅雷的面试中就遇到，让实现一个hashtable。 本文中采用开链法（separate chaining）来处理“冲突”（collision），而且hashtable只存储唯一的元素，不存在重复。 实现代码如下： class hashtable { public: // 构造函数，n为想要构造的hashtable的bucket数量 hashtable(size_t n); ~hashtable(); // 插入元素。若元素不存在，插入成功返回true；若元素已存在则插入失败，返回false bool insert(const int val); // 查找元素是否在表中出现 bool find(const int val); // 删除元素。若元素存在，删除成功返回true；若元素不存在则删除失败，返回false bool 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) { // 不重复插入。已存在，返回false if(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; else pre->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]; }  （编辑：PHP编程网 - 黄冈站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330482号