Hash表的C++实现

用C++写了一个链地址型的Hash表

参考博客：https://blog.csdn.net/Bob__yuan/article/details/100016473， https://blog.csdn.net/weixin_38169413/article/details/81612307

Hash表介绍

散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，是的每个关键字key对应一个存储位置f(key)。查找时，根据这个对应的关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。我们把这种对应关系f成为散列函数，又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续空间称为散列表或哈希表(Hash-Table)。

Hash表的构造方法

直接定址法
取余法
数字分析法
平方取中法
折叠法

本文用取余法

Hash表的冲突策略

1.开放地址法

一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址.若发生了第 i 次冲突，试探的下一个地址将增加d_i

2.链地址法

链地址法就是将相应位置上冲突的所有关键词存储在同一个单链表中。将所有关键字为同义词的记录存储在一个单链表中，这种链表叫做同义词子表，使用除留余数法，就不存在冲突的问题了，只是在链表中增加一个结点。

代码实现：将26个字母放在Hash表中，支持增删查功能，并移除字母c。

  1 #include <iostream>
  2 #include <map>
  3 
  4 #define ARRAY_NUMBER 11
  5 
  6 //用于存放数据的节点
  7 template<typename T>
  8 struct LNode{
  9   T data;
 10   LNode* next;
 11 
 12   LNode(T t, LNode* ptNext){
 13       data = t;
 14       ptNext = next;
 15   }
 16 };
 17 
 18 template<typename T>
 19 class HashMap{
 20 public:
 21     //插入元素
 22     void insert(T data)
 23     {
 24         long hashValue = std::hash<T>()(data);  //通过std::hash得到hash值（std::hash可以匹配多种类型）
 25         int hashKey = hashValue % ARRAY_NUMBER;
 26         LNode<T>* pNode = new LNode<T>(data, NULL);
 27         LNode<T>* pInsertNode = mapData[hashKey];
 28         if (pInsertNode == NULL)
 29         {
 30             mapData[hashKey] = pNode;
 31         } else {
 32             LNode<T>* pPreviousNode = NULL;
 33             while (pInsertNode != NULL) {
 34                 pPreviousNode = pInsertNode;
 35                 pInsertNode = pInsertNode->next;
 36             }
 37             pPreviousNode->next = pNode;
 38             pInsertNode = pNode;
 39         }
 40     }
 41 
 42     //查找一个数据
 43     bool find(T data)
 44     {
 45         long hashValue = std::hash<T>()(data);
 46         int hashKey = hashValue % ARRAY_NUMBER;
 47         LNode<T>* pNode =  mapData[hashKey];
 48         while (pNode != NULL)
 49         {
 50             if (pNode->data == data)
 51             {
 52                 std::cout << "Find out data :" << pNode->data << std::endl;
 53                 return true;
 54             }
 55             pNode = pNode->next;
 56         }
 57         std::cout << "Not found" << std::endl;
 58         return false;
 59     }
 60 
 61     //移除一个数据
 62     void remove(T data)
 63     {
 64         long hashValue = std::hash<T>()(data);
 65         int hashKey = hashValue % ARRAY_NUMBER;
 66         LNode<T>* pNode =  mapData[hashKey];
 67         LNode<T>* pPreviousNode = NULL;
 68         while (pNode != NULL)
 69         {
 70             if (pNode->data != data)
 71             {
 72                 pPreviousNode = pNode;
 73                 pNode = pNode->next;
 74             } else {
 75                 if (pPreviousNode)
 76                 {
 77                     pPreviousNode->next = pNode;
 78                 } else {
 79                     mapData[hashKey] = pNode->next;
 80                     break;
 81                 }
 82                 if (pNode->next)
 83                 {
 84                     pPreviousNode->next = pNode->next;
 85                 }
 86                 else
 87                 {
 88                     pPreviousNode->next = NULL;
 89                 }
 90                 break;
 91             }
 92         }
 93     }
 94 
 95     //初始化Hash表，本例用std::map,为每个数组元素创建一个链表
 96     void initialize()
 97     {
 98         for (int i=0; i < ARRAY_NUMBER; i++)
 99         {
100             mapData.insert(std::pair<int, LNode<T>*>(i, NULL));
101         }
102     }
103 
104     //输出Hash表
105     void print()
106     {
107         for (int i=0; i < ARRAY_NUMBER; i++)
108         {
109             std::cout << i;
110             LNode<T>* pNode = mapData[i];
111             while (pNode) {
112                 std::cout << " -> " << pNode->data;
113                 pNode = pNode->next;
114             }
115             std::cout << std::endl;
116         }
117     }
118 
119 
120 private:
121     std::map<int, LNode<T>*> mapData;
122 
123 };
124 
125 
126 int main(int argc, char *argv[])
127 {
128     HashMap<char> hashMap;
129     hashMap.initialize();
130     for (char c = 'a'; c <= 'z'; c++)
131     {
132         hashMap.insert(c);
133     }
134     hashMap.find('c');
135     hashMap.remove('c');
136     hashMap.find('c');
137     hashMap.print();
138     return 0;
139 }

输出：