哈希表---开链法解决哈希冲突

Biegral 2020/11/5 21:07:02 5116

上篇文章已经写过构造哈希表时用开放定址法解决哈希冲突，这次我就来写写这个开链法解决哈希冲突的问题！

一、结点定义

我们已经知道开链法大概是一种什么结构了，（如果不知道，这里有讲哦点我点我）显而易见，实现哈希桶的话我们就必须多一个指针next，至少这样才看起来有个链表的样子嘛！！

[cpp]  view plain  copy
  1. //开链法（哈希桶）  
  2. template<class K,class V>  
  3. struct KVNode  
  4. {  
  5.     K _key;  
  6.     V _value;  
  7.     KVNode<K,V>* _next;  
  8.   
  9.     KVNode(const K& key,const V& value)  
  10.         :_key(key)  
  11.         ,_value(value)  
  12.         ,_next(NULL)  
  13.     {}  
  14. };  
二、哈希表的实现----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 plain  copy
  在CODE上查看代码片 派生到我的代码片
  1. bool Insert(const K& key,const V& value)  
  2.     {  
  3.   
  4.         if (Find(key))  //已经存在这个数  
  5.             return false;  
  6.       
  7.         _CheckSize();  
  8.         size_t index = _HashFunc(key,_table.size());  
  9.         Node* tmp = new Node(key,value);  
  10.         tmp->_next = _table[index];  
  11.         _table[index] = tmp;  
  12.         _size++;  
  13.         return true;  
  14.     }  

Find：

首先要找到key的散列地址，再在这个地址上挂着的链表开始遍历查找，直到找到相同的key为止。

[cpp]  view plain  copy
  在CODE上查看代码片 派生到我的代码片
  1. Node* Find(const K& key)  
  2.     {  
  3.         if (_size == 0)  
  4.             return NULL;  
  5.   
  6.         size_t index = _HashFunc(key,_table.size());  
  7.         Node* cur = _table[index];  
  8.         while (cur)  
  9.         {  
  10.             if (cur->_key == key)  
  11.                 return cur;  
  12.   
  13.             cur = cur->_next;  
  14.         }  
  15.   
  16.         //没有找到  
  17.         return false;  
  18.     }  

Delete：

删除一个数据时就是要删除这个结点，删除结点的方式与删除链表一个结点的方式是一样的，只要改变前一个结点的next指针。不过在这之前我们需要通过散列地址找到这个结点。假如要删除53表示的这个结点


[cpp]  view plain  copy
  在CODE上查看代码片 派生到我的代码片
  1. bool Remove(const K& key)  
  2.     {  
  3.         if(_size == 0)  
  4.             return false;  
  5.   
  6.         size_t index = _HashFunc(key,_table.size());  
  7.         Node* cur = _table[index];  
  8.         Node* prev = NULL;  
  9.         while (cur)  
  10.         {  
  11.             while(cur->_key == key)  
  12.             {  
  13.                 //删除的是头（第一个）结点  
  14.                 if (prev == NULL)  
  15.                 {  
  16.                     _table[index] = cur->_next;  
  17.                 }  
  18.                 //删除非头结点(中间或后边)  
  19.                 else  
  20.                 {  
  21.                     prev->_next = cur->_next;  
  22.                 }  
  23.   
  24.                 delete cur;  
  25.                 _size--;  
  26.                 return true;  
  27.             }  
  28.             prev = cur;  
  29.             cur = cur->_next;  
  30.         }  
  31.         return false;  
  32.     }  

具体代码：

[cpp]  view plain  copy
  在CODE上查看代码片 派生到我的代码片
  1. //开链法（哈希桶）  
  2. template<class K,class V>  
  3. struct KVNode  
  4. {  
  5.     K _key;  
  6.     V _value;  
  7.     KVNode<K,V>* _next;  
  8.   
  9.     KVNode(const K& key,const V& value)  
  10.         :_key(key)  
  11.         ,_value(value)  
  12.         ,_next(NULL)  
  13.     {}  
  14. };  
  15.   
  16. template<class K,class V>  
  17. class HashTable  
  18. {  
  19.     typedef KVNode<K,V> Node;  
  20. public:  
  21.     HashTable()  
  22.         :_size(0)  
  23.     {  
  24.         _table.resize(3);  
  25.     }  
  26.     ~HashTable()  
  27.     {  
  28.         for (size_t i=0; i<_table.size(); ++i)  
  29.         {  
  30.             Node* cur = _table[i];  
  31.             while (cur)  
  32.             {  
  33.                 Node* tmp = cur->_next;  
  34.                 delete cur;  
  35.                 cur = tmp;  
  36.             }  
  37.             _size = 0;  
  38.             _table.clear();  
  39.         }  
  40.     }  
  41.   
  42.     Node* Find(const K& key);  
  43.     bool Remove(const K& key);  
  44.     bool Insert(const K& key,const V& value);  
  45.     void Display()  
  46.     {  
  47.         for (size_t i=0; i<_table.size(); ++i)  
  48.         {  
  49.             printf("Table[%d]->",i);  
  50.             Node* cur = _table[i];  
  51.             while (cur)  
  52.             {  
  53.                 Node* next = cur->_next;  
  54.                 cout<<cur->_key<<" ";  
  55.                 cur = next;  
  56.             }  
  57.             cout<<NULL;  
  58.             cout<<endl;  
  59.         }  
  60.     }  
  61. protected:  
  62.     void _CheckSize()  
  63.     {  
  64.         if (_table.size() == 0 || _size == _table.size())  
  65.         {  
  66.             vector<Node*> tmpTable;  
  67.             tmpTable.resize(_GetPrimer(_table.size()));  
  68.             //将原表_table中的结点直接放入新表中  
  69.             for (size_t i=0; i<_table.size(); ++i)  
  70.             {  
  71.                 Node* cur = _table[i];  
  72.                 while (cur)  
  73.                 {  
  74.                     Node* next = cur->_next;  
  75.   
  76.                     size_t index = _HashFunc(cur->_key,tmpTable.size());  
  77.                     cur->_next = tmpTable[index];  
  78.                     tmpTable[index] = cur;  
  79.   
  80.                     cur = next;  
  81.                 }  
  82.             }  
  83.             _table.swap(tmpTable);  
  84.         }  
  85.     }  
  86.   
  87.     size_t _GetPrimer(size_t size)  
  88.     {  
  89.         const int _PrimeSize = 28;  
  90.         static const unsigned long _PrimeList[_PrimeSize] =  
  91.         {  
  92.             53ul, 97ul, 193ul, 389ul, 769ul,  
  93.             1543ul, 3079ul, 6151ul, 12289ul, 24593ul,  
  94.             49157ul, 98317ul, 196613ul, 393241ul,  
  95.             786433ul,  
  96.             1572869ul, 3145739ul, 6291469ul, 12582917ul,  
  97.             25165843ul,  
  98.             50331653ul, 100663319ul, 201326611ul, 402653189ul,  
  99.             805306457ul,  
  100.             1610612741ul, 3221225473ul, 4294967291ul  
  101.         };  
  102.         for (size_t i=0; i<_PrimeSize; ++i)  
  103.         {  
  104.             if (_PrimeList[i] > size)  
  105.             {  
  106.                 return _PrimeList[i];  
  107.             }  
  108.         }  
  109.     }  
  110.     size_t _HashFunc(const K& key,size_t size)  
  111.     {  
  112.         return key%size;  
  113.     }  
  114. protected:  
  115.     vector<Node*> _table;  
  116.     size_t _size;   //已有的数据个数  
  117. };  
本文转载:CSDN博客

阅读排行

分类

归档