生活随笔
收集整理的这篇文章主要介绍了
哈希表---开链法解决哈希冲突
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
上篇文章已经写过构造哈希表时用开放定址法解决哈希冲突，这次我就来写写这个开链法解决哈希冲突的问题！
一、结点定义
我们已经知道开链法大概是一种什么结构了，（如果不知道，这里有讲哦点我点我）显而易见，实现哈希桶的话我们就必须多一个指针next，至少这样才看起来有个链表的样子嘛！！
[cpp] view plaincopy
template<class K,class V> struct KVNode { K _key; V _value; KVNode<K,V>* _next; KVNode(const K& key,const V& value) :_key(key) ,_value(value) ,_next(NULL) {} };
二、哈希表的实现----Inser、Find、Remove
以数组int a[] = {51, 105, 52, 3, 55, 2, 106, 53, 0}为例
Insert：
老规矩，我们还是得判断这个key在表中是否存在，如果存在就插入失败；当两个key有相同的散列地址时，我们只需将前一个结点的next指针指向新结点即可！那么，我们在同一个散列地上的链表进行插入结点时，用头插好还是尾插好呢？！当然是头插好了，这样我们就不用每次遍历到链表的尾结点，这可省了不少事儿！！
以上面这个数组为例，假设51和105分别都已经插入在正确的位置（此时表长53），接下来需要插入52，我们利用头插进行插入
如果表中的某个位置此时为NULL，当要进行插入时，做法与上述一样。
[cpp] view plaincopy
bool Insert(const K& key,const V& value) { if (Find(key)) return false; _CheckSize(); size_t index = _HashFunc(key,_table.size()); Node* tmp = new Node(key,value); tmp->_next = _table[index]; _table[index] = tmp; _size++; return true; }
Find：
首先要找到key的散列地址，再在这个地址上挂着的链表开始遍历查找，直到找到相同的key为止。
[cpp] view plaincopy
Node* Find(const K& key) { if (_size == 0) return NULL; size_t index = _HashFunc(key,_table.size()); Node* cur = _table[index]; while (cur) { if (cur->_key == key) return cur; cur = cur->_next; } return false; }
Delete：
删除一个数据时就是要删除这个结点，删除结点的方式与删除链表一个结点的方式是一样的，只要改变前一个结点的next指针。不过在这之前我们需要通过散列地址找到这个结点。假如要删除53表示的这个结点
[cpp] view plaincopy
bool Remove(const K& key) { if(_size == 0) return false; size_t index = _HashFunc(key,_table.size()); Node* cur = _table[index]; Node* prev = NULL; while (cur) { while(cur->_key == key) { if (prev == NULL) { _table[index] = cur->_next; } else { prev->_next = cur->_next; } delete cur; _size--; return true; } prev = cur; cur = cur->_next; } return false; }
具体代码：
[cpp] view plaincopy
template<class K,class V> struct KVNode { K _key; V _value; KVNode<K,V>* _next; KVNode(const K& key,const V& value) :_key(key) ,_value(value) ,_next(NULL) {} }; template<class K,class V> class HashTable { typedef KVNode<K,V> Node; public: HashTable() :_size(0) { _table.resize(3); } ~HashTable() { for (size_t i=0; i<_table.size(); ++i) { Node* cur = _table[i]; while (cur) { Node* tmp = cur->_next; delete cur; cur = tmp; } _size = 0; _table.clear(); } } Node* Find(const K& key); bool Remove(const K& key); bool Insert(const K& key,const V& value); void Display() { for (size_t i=0; i<_table.size(); ++i) { printf("Table[%d]->",i); Node* cur = _table[i]; while (cur) { Node* next = cur->_next; cout<<cur->_key<<" "; cur = next; } cout<<NULL; cout<<endl; } } protected: void _CheckSize() { if (_table.size() == 0 || _size == _table.size()) { vector<Node*> tmpTable; tmpTable.resize(_GetPrimer(_table.size())); for (size_t i=0; i<_table.size(); ++i) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; size_t index = _HashFunc(cur->_key,tmpTable.size()); cur->_next = tmpTable[index]; tmpTable[index] = cur; cur = next; } } _table.swap(tmpTable); } } size_t _GetPrimer(size_t size) { const int _PrimeSize = 28; static const unsigned long _PrimeList[_PrimeSize] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; for (size_t i=0; i<_PrimeSize; ++i) { if (_PrimeList[i] > size) { return _PrimeList[i]; } } } size_t _HashFunc(const K& key,size_t size) { return key%size; } protected: vector<Node*> _table; size_t _size; };
总结
以上是生活随笔为你收集整理的哈希表---开链法解决哈希冲突的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
