【数据结构】散列（哈希）表简单介绍

散列表也叫做哈希表（Hash table），散列表通过关键码和存储地址建立唯一确定的映射关系，能够快速查找到对应的元素，排序算法中的计数排序就是一种利用哈希进行排序的算法。

一、散列表的概念

散列表（Hash table）是表示集合和字典的另一种有效方法，它提供了一种完全不同的存储和搜索方式，通过将关键码映射到表中的某个位置来存储元素，然后根据关键码用同样的方式直接访问。

二、散列方法

在散列表中搜索元素可以不进行任何大小的比较，只需要支持比较相等即可，因为通过映射关系建立的散列表可以一次从中得到要搜索的元素的集合。

（一）散列函数（Hash function）

元素在散列表中的存储地址和关键码之间的映射关系通过散列函数Hash()来唯一确定，使得每个关键码在散列表中都有一个唯一确定的存储位置相对应。设Address为散列表中距离散列表中第一个存储位置的地址偏移量，key为元素的关键码，那么所确定的存储位置Address和关键码key之间的关系为

$Address = Hash(key)$

一般情况，关键码的集合比散列表地址的集合大得多，所以会出现不同元素的关键码通过同一个散列函数计算出了同一个存储位置，这些不同的关键码称之为同义词（synonym）。这些同义词元素在存储时就会发生哈希冲突，冲突往往是不能够避免的，只能尽量减小，所以我们必须有解决冲突的方法，我们也需要选择合适的散列函数，尽量让散列表中的每一个位置都能有相同的概率被不同关键码映射到，减少冲突的发生。

（二）、散列函数的选择

所有的散列函数需要遵循下面三个规定：

1、散列函数的定义域必须包含全部的关键码，并且如果散列表允许存储的地址个数为size个，那么散列函数计算出的映射地址的值域必须为[0,size - 1]。

2、通过散列函数计算出的地址应能够均匀分布在整个地址空间中，让散列表中的每一个位置都能有相同的概率被不同关键码映射到，减少冲突的发生。

3、散列函数应是简单的，能够在较短时间内计算出结果。

下面来讲一个常用的散列函数，除留余数法。其他的散列函数有很多：数学分析法、平方取中法、折叠法等等，这里不着重介绍。

假设散列表中的存储地址个数为size个，某元素的关键码为key（key需要是整数，如果不是整数类型，则还需要通过某种规则将key转化为整数，例如将字符串按照某种规则转化为整数）。

除留余数法（division）

取一个质数 $p$ ， $p \leqslant size$ ，则可以利用下面的公式将关键码转化为散列地址：

hash(key) = key % p

其中，“%”是运算符中的整数除法取余的操作。当p接近于size并且为质数时，散列函数计算出的映射值冲突最小，为更进一步的减小冲突，p也应当避免为2或10的次幂。当然这不是硬性要求，如果不注重极致的效率，自己设计实现的散列表的p可以不为质数，也不管是否为2或10的次幂。为了简单介绍，下面出现的size就等于并代表p。

举例： size = 10, key = 2233，那么2233通过散列函数映射到的地址offset = hash(2233) = 2233 % 10 = 3。

三、处理冲突的方法

（一）、闭散列（开地址法）

闭散列也叫做开地址法。开一段数组空间作为散列表(hash table)，数组的元素类型即需要存储的元素的类型，该数组有size个存储地址，并将该数组头尾相连作为环状结构使用。当新插入一个元素时，用该元素的关键码key计算其存储的位置hashi，然后将该元素定位到散列表中的第hashi个位置上，如果hashi位置尚未存储有其他元素，那么直接将新的元素存储到hashi的位置。若hashi位置已经被其他元素占取了，此时发生了冲突，需要制定某种方案将新插入的元素存储到“下一个”空的位置中。

线性探查法解决哈希冲突

下面详细讲闭散列中的一种解决哈希冲突的方法：线性探查法（linear probing）。还有其他的解决冲突方法：如二次探查法（quadratic probing）和双散列法，这里不着重介绍。

插入元素

给出一组元素，它们的关键码分别为37,25,15,36,49,68,59,11,表的大小size = 10。散列函数使用除留余数法，hash(key) = key % 10。

这样可得每一个关键码对应的映射地址为：

关键码（key）	映射地址（hash(key)）
37	7
25	5
15	5
36	6
49	9
68	8
59	9
11	1

将上述元素的关键码（为简单起见，键就是要存储的元素值）依次存储到散列表中，散列表中的变化如下：

需要加入一个新元素时，通过散列函数计算该元素存储的位置，如果存储的位置存在其他的元素，则查看紧随其后的下一个位置，如果没有被占用，则将新元素存储到该位置，否则继续查看紧随其后的下一个位置，直到找到没有被占用的位置为止（若饶了数组一圈都没法找到空的位置，说明散列表满了），则插入失败（如果在满之前扩容就可以避免发生因为容量不足而插入失败的情况了）。

散列情况统计：

关键码	37	25	15	36	49	68	59	11
映射位置	7	5	5	6	9	8	9	1
冲突位置	无	无	5	6,7	无	8,9	9,0	1
最后存入的位置	7	5	6	8	9	0	1	2
探查次数	1	1	2	3	1	3	3	2

查找元素

将这些关键码存储到散列表中后，后续查找某元素时的查找次数和存入该元素时的探查次数相同，方式也一样。例如在散列表中搜索关键码为36的元素，先通过散列函数定位到6的位置，发现6号位置为15，不相等，则线性探测到下一号7,7号位置为37，不相等，则线性探测到下一号8，发现相等，此时查找到了关键码为36的元素。若探测到的位置存储的元素为空，则查找失败，该元素不在散列表中。

删除元素

需要注意，在闭散列的情形下不能随便物理删除散列表中已有的元素。因为若删除元素会影响其他元素的搜索。例如在上面查找关键码为36的元素例子前，把关键码为37的元素给物理删除了，7号位置为空，那么在查找36时，探测到7号位置，发现为空，此时程序为认为关键码为36的元素不在该散列表中，就发生了漏查的情况，解决方法是对删除的7号位置标记为deleted状态，当查找探测到deleted状态的位置时，继续往下探测，这样就不会发生漏查了。

负载因子α

引入负载因子α来讨论当前散列表是否需要进行扩容，负载因子α的计算方法为：设当前散列表存储的元素个数为n，散列表的大小为size，那么α = n / size。若用线性探查法解决冲突，当α = 1时，说明此时散列表满了，不论如何都要进行扩容操作了。采用线性探查法的散列表一般在α 小于等于0.75前就应该扩容了，因为采用线性探查法的散列表存储过多元素会产生太多的“堆积”会导致该散列表的搜索效率过低。

搜索效率

元素通过关键码可以映射定位到一个接近散列表中存储该元素的位置，能够从接近该元素存储位置的地方开始线性探测，而线性探查法容易产生“堆积（cluster）”问题，即某元素本该映射到的位置被其他的非映射到该位置的元素给占用了，某元素映射到的位置和实际存储的位置不相同，导致插入和搜索时所需要探测的序列长度变长，搜索时间增加。

简单代码实现（C++）

#pragma once
#include <iostream>
#include <vector>using namespace std;//-----------------------------HashFunc仿函数----------------------------------------
// 描述：将键值转化为哈希值（就是将某类型K的关键码转化为整数的方法）
//-----------------------------------------------------------------------------------
template<class K>
class HashFunc
{
public:size_t operator() (const K& key){return (size_t)key;	//对于可以转化为整形的数据直接强转为整形}
};//对常用的string类型进行特化处理，转化为哈希值
template<>
class HashFunc<std::string>
{
public:size_t operator() (const std::string& str){//进行特殊运算将字符串转化为整形映射//其他的转化方法参考https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.htmlsize_t hash = 0;for (auto& e : str){hash += e;hash *= 31;	//每次加上一个ASCII码值再乘上31}return hash;}
};//闭散列开放地址法
//解决哈希冲突的方法：线性探查法
namespace MySpace1
{//-----------------------------存储状态和存储节点的类型的定义------------------------// //-----------------------------------------------------------------------------------//哈希表中每个位置的存储状态enum KindOfState{EMPTY,	//代表该位置为空EXIST,	//代表该位置存在着元素DELETED,};//哈希表的结点，数组的每一个元素为一个结点，里面存储了要存储的元素和该位置状态template<class T>struct HashNode{public:T _data;	//结点存储的数据KindOfState _state;	//该节点的状态HashNode(T data = T(), KindOfState state = EMPTY) :_data(data), _state(state) {  }};//----------------------------------哈希表的具体实现---------------------------------// 描述：博客上的描述和代码实现上可能有些出入。//-----------------------------------------------------------------------------------template<class T, class Hash = HashFunc<T>>class HashTable{private:typedef HashNode<T> Node;vector<Node> _table;	//哈希表size_t currentSize;	//当前哈希表实际存储的数据个数public:HashTable() :currentSize(0){_table.resize(10);	//默认开十个数据大小}//插入bool insert(const T& key){if (_table[find(key)]._state == EXIST)	//判断要插入的值是否已经存在，如果是则插入失败return false;if (currentSize * 100 / _table.size() >= 75)	//负载超过75%就扩容{//扩容和重新映射//两倍扩容HashTable newTable;newTable._table.resize(2 * _table.size());for (auto& e : _table)	//将原有数据插入到新表中重新计算映射位置newTable.insert(e._data);_table.swap(newTable._table);	//将新表交换给旧表，完成扩容工作//cout << "扩容到" << _table.size() << "个数据大小" << endl;}Hash hash;//除留余数法计算哈希值size_t hashi = hash(key) % _table.size();//找到空位存储key值while (_table[hashi]._state == EXIST){hashi = (hashi + 1) % _table.size();}_table[hashi]._data = key;_table[hashi]._state = EXIST;currentSize++;	//存储的有效数据个数+1return true;}//删除bool erase(const T& key){size_t hashi = find(key);if (_table[hashi]._state == EXIST){_table[hashi]._state = DELETED;currentSize--;return true;}return false;}//查找，返回对应关键码的映射位置size_t find(const T& key) const{Hash hash;size_t hashi = hash(key) % _table.size();while (_table[hashi]._state != EMPTY)	//不为空则往后找{if (_table[hashi]._state == EXIST && _table[hashi]._data == key)	//存在且与key相等return hashi;hashi = (hashi + 1) % _table.size();}//找不到return hashi;}};//--------------------------------测试代码------------------------------------// 描述：需要在调试窗口看具体的存储情况//----------------------------------------------------------------------------void test1(){MySpace1::HashTable<int> hashTable;int a[] = { 11,21,4,14,24,15,9 ,55,66,99,87,15,56,61,32,14,14,16 };for (auto e : a){hashTable.insert(e);}hashTable.erase(15);size_t hash = hashTable.find(55);for (auto e : a){hashTable.erase(e);}}void test2(){HashTable<string> hashTable;hashTable.insert("insert");hashTable.insert("sort");hashTable.insert("good");hashTable.insert("oodg");hashTable.insert("rtos");hashTable.insert("sertin");hashTable.insert("dog");hashTable.insert("cat");hashTable.insert("bird");hashTable.erase("good");size_t i = hashTable.find("good");}
};

（二）、开散列（链地址法）

开散列也叫做链地址法，开一段数组空间作为散列表（hash table），数组的元素类型为指向一个链表头结点的指针类型（若链表为空，则置空）。散列表中的每一个元素都是一个指针，指向不同的链表，每一个链表都为一个桶，该结构又叫做哈希桶。当不同的关键码通过同一个散列函数计算出相同的存储位置hashi时，只需将这些互为同义词的元素存储到第hashi位置的桶上，也就是存储在同一个链表上，每一个桶为同义词的集合。

插入元素

给出一组元素，它们的关键码分别为37,25,15,36,49,68,59,11表的大小size = 10。散列函数使用除留余数法，hash(key) = key % 10。

这样可得每一个关键码对应的映射地址为：

关键码（key）	映射地址（hash(key)）
37	7
25	5
15	5
36	6
49	9
68	8
59	9
11	1

将上述元素的关键码（为简单起见，键就是要存储的元素值）依次存储到散列表中，散列表中的变化如下：

查找和删除元素

查找：待查找的元素x的关键码通过散列函数找到对应的桶号，然后在桶内通过遍历链表的方式依次将遍历的元素和待查找的元素x进行比对即可。

删除：待删除的元素x的关键码通过散列函数找到对应的桶号，执行像链表一样删除某结点的操作即可。

负载因子α

引入负载因子α来讨论当前散列表是否需要进行扩容，负载因子α的计算方法为：设当前散列表存储的元素个数为n，散列表的大小为size，那么α = n / size。若用开散列的哈希桶结构解决冲突，当α = 1时，建议进行扩容操作，因为当α = 1时，说明n = size，在非常理想的情况下，每个桶的结点都均等分，即哈希表中的所有桶都存储有结点，而且每个桶只有一个结点，这个时候对哈希表进行扩容，可以控制每个桶的长度不会过长，保证搜索效率。当存储的元素非常多时，要追求更高效率，可以在桶的长度超过8时，考虑使用红黑树结构存储同义词的集合，而不是桶结构，保证搜索的时间复杂度为常数级别。

搜索效率

在冲突不多，每个桶存储结点的平均长度不长的时候（必要时可考虑使用红黑树结构代替桶），搜索效率高，时间复杂度可以达到常数级 $O(1)$ 。

在这个例子中，搜索成功的平均搜索长度为（1 + 1 + 2 + 1 + 1 + 1 + 1 + 2 ） / 8 = 1.25

搜索失败的平均搜索长度为（1 + 2 + 1 + 1 + 1 + 3 + 2 + 2 + 2 + 3） / 10 = 1.8

简单代码实现（C++）

#pragma once
#include <iostream>
#include <vector>using namespace std;//-----------------------------HashFunc仿函数----------------------------------------
// 描述：将键值转化为哈希值（就是将某类型K的关键码转化为整数的方法）
//-----------------------------------------------------------------------------------
template<class K>
class HashFunc
{
public:size_t operator() (const K& key){return (size_t)key;	//对于可以转化为整形的数据直接强转为整形}
};//对常用的string类型进行特化处理，转化为哈希值
template<>
class HashFunc<std::string>
{
public:size_t operator() (const std::string& str){//其他的转化方法参考字符串Hash函数size_t hash = 0;for (auto& e : str){hash += e;hash *= 31;	//每次加上一个ASCII码值再乘上31}return hash;}
};namespace MySpace2
{//桶的结点定义template<class T>struct HashBucketNode{T _data;HashBucketNode* next;	//指向下一个结点,如果为空，则代表尾结点HashBucketNode(const T& data) :_data(data), next(nullptr) {  }};//散列表的具体实现template<class T, class Hash = HashFunc<T>>class HashTable{private:typedef HashBucketNode<T> Node;	vector<Node*> _table;	//散列表为指针数组，每个指针指向一个桶size_t currentSize;	//存储的有效数据个数public:HashTable() :currentSize(0){_table.resize(10, nullptr);	//默认开10个桶的大小,都为空}~HashTable()	//析构函数，释放所有桶的结点{for (auto& node : _table){Node* pCur = node;Node* pNext = nullptr;while (pCur){pNext = pCur->next;delete pCur;pCur = pNext;}node = nullptr;}}//插入bool insert(const T& value){if (find(value))	//如果要插入的元素已经存在，插入失败				return false;if (currentSize >= _table.size())	//如果当前数据个数等于桶的个数，就扩容{vector<Node*> newTable(_table.size() * 2, nullptr);for (auto& node : _table)	//将每个桶里的结点重新映射，将现有节点移动到新的桶中，而不应是复制结点。{if (node)	//该桶不为空{Node* pNext = nullptr;Node* pCur = node;size_t hashi;Hash hash;while (pCur){pNext = pCur->next;hashi = hash(pCur->_data) % newTable.size();	//计算映射值//头插到新的桶中pCur->next = newTable[hashi];newTable[hashi] = pCur;pCur = pNext;}}}//旧表和新表交换_table.swap(newTable);}Hash hash;size_t hashi = hash(value) % _table.size();//将元素头插到桶上Node* newNode = new Node(value);newNode->next = _table[hashi];_table[hashi] = newNode;	//成为新的头结点currentSize++;	//结点的数量增加return true;}//删除bool erase(const T& key){Hash hash;size_t hashi = hash(key) % _table.size();Node* pPrev = nullptr;	//待删除节点的上一个结点Node* pCur = _table[hashi];	//到对应的桶中找对应结点while (pCur){if (pCur->_data == key)break;pPrev = pCur;pCur = pCur->next;}//如果不存在该结点if (!pCur)return false;//如果删除的是头结点if (pPrev == nullptr){_table[hashi] = pCur->next;delete pCur;}else{pPrev->next = pCur->next;delete pCur;}currentSize--;return true;}//查找Node* find(const T& key){Hash hash;size_t hashi = hash(key) % _table.size();Node* pCur = _table[hashi];	//到对应的桶中找对应结点while (pCur){if (pCur->_data == key)return pCur;pCur = pCur->next;}//找不到return	nullptr;}};void test1(){HashTable<int> hsTable;int a[] = { 37,25,15,36,49,68,59,25,15,36,49};for (auto e : a)	//依次添加案例元素{hsTable.insert(e);}for (auto e : a)	//测试依次删除所有元素{hsTable.erase(e);}}
};