一. 什么是哈希？
1. 哈希概念
顺序结构以及平衡树结构中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数：顺序查找时间复杂度为O(N)，平衡树中为树的高度O(logN )。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立映射关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，最终完整构造出来的搜索结构称为哈希表(Hash Table)(或者称散列表)。
PS：哈希函数有很多种，但里面存储数据的数据结构通常是顺序表，因为顺序表随机访问的效率很高，所以在哈希（散列）表中一般封装的是顺序表。
2. 哈希函数
虽然哈希函数 Hash(key) 有很多种，但它们的设计都应该满足下面几个原则：
哈希函数的定义域必须包括需要存储的全部关键码（key）。
哈希函数计算出来的地址能均匀分布在整个空间中。
常用哈希函数包括两种：直接定址法、除留余数法。
1、直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀 。
缺点：需要事先知道关键字的分布情况 ，且数据范围不能相差太大。
使用场景：适合查找数据范围比较小且连续的情况。
示例
情景：输入一个全是小写字母的字符串，统计每个字符出现的次数。
通过哈希函数：Hash(key) = key - ‘a’，我们可以得到每个字符所映射的唯一下标位置，进而可以拿到或修改字符串中该字符的出现次数。可以看到数据范围较小且连续时，使用直接定址法可以很方便地管理数据。
2、除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将关键码转换成哈希地址。除留余数法可以管理范围相差较大的数据。
示例
情景：给定一个整数集合，之后输入任意一个整数搜索该数字是否在给定集合中。
按照上述哈希方式，继续向集合中插入元素44，发现Hash(44) = 44%10 = 4，可是下标四位置处已经有元素了，那么44应该插到哪里呢？我们把这种情况叫做哈希冲突。
3. 哈希冲突
对于两个数据元素的关键字 i 和 j , ( i != j )；有：Hash( i ) == Hash( j )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
4. 哈希冲突的解决
解决哈希冲突两种常见的方法是：闭散列和开散列。
闭散列（开放定址法）
a、线性探测
b、二次探测
开散列（哈希桶、拉链法、链地址法）
这两种方法的相同点都是控制负载因子的大小来解决哈希冲突，只不过处理数据的方式不同。其中：负载因子 = 表中有效数据个数 / 表的大小。 负载因子越小，冲突的概率越低，效率越高，但是浪费的空间也越多。
对于闭散列：负载因子不能超过1，一般建议控制在 [0.0，0.7] 左右。
对于开散列：负载因子可以超过1，一般建议控制在 [0.0，1.0] 左右。
实际中开散列的解决哈希冲突方法更实用，相比闭散列它有如下两个优点：
空间利用率更高。
发生极端的数据冲突时还有解决方案。比如一个桶中挂的数据个数大于某个约定值时，会把单链表换为红黑树结构。
5. 哈希知识点梳理
6. 哈希概念相关问题
问题一：哈希查找的时间复杂度一定是O(1)吗？
答：不一定，因为存在哈希冲突，一般平均下来是O(1)。
问题三：常见的哈希函数？
答：直接定址法、除留余数法、平方取中法、随机数法、数字分析法、叠加法等。
问题三：解决哈希函数中出现冲突问题常采用的方法？
答：线性探测法、多重散列法、链地址法。
问题四：哈希冲突是可以通过设计好的哈希函数来杜绝的？
答：错误，哈希冲突是不能杜绝的，这个与存储的元素以及哈希函数相关。
问题五：哈希冲突是不同的元素，通过不同的哈希函数而产生相同的哈希地址而引起的？
答：错误，哈希冲突是不同的元素，通过相同的哈希函数而产生相同的哈希地址而引起的。
问题六：哈希冲突产生的原因一定是插入了相同的元素？
答：错误，不同元素在计算出相同的哈希值时就会冲突。
二. 哈希的优缺点？
优点
- 哈希存储在数据的增删查改方面有较高的效率，查找的时间复杂度平均为O(1)。
缺点：
- 哈希是以 key-value的形式存储数据的，因此数据之间没有顺序，无法通过下标随机访问数据。
- 占的空间大，牺牲空间换取了效率。
- 哈希表扩容代价较大。开新空间、重新映射数据、释放旧空间。
三. 哈希表模拟实现
下面我们用到的哈希函数都是除留余数法。
哈希表中元素唯一，即key相同的元素不再进行插入。
1. 非整型key的处理
数据key的类型不一定是整型，还可能是字符型、浮点型、自定义的结构体类型等等，考虑哈希函数中的除留余数法的话，这些非整型的key是不能进行取模运算的，但是我们总有办法把它们转化成整型值：
补充1：关于key类型是字符串时
根据BKDR算法，累加每一个字符的ASCLL码之前，先乘上一个整型数字131，可以避免由于字符串中字符位置、数量不同等产生的哈希冲突：
更详细了解可以参考下面文章：字符串哈希算法
补充2：如果key类型是结构体，能不用结构体的地址作为key呢？
答：不能
虽然地址虽然是一个整型数据，但是地址作为key可读性太差，查找起来不方便。
其次地址是会发生改变的，它的唯一性得不到保证。哈希表中元素唯一，即key相同的元素不再进行插入。比如我有两个同类型的结构体对象，刚好两个结构体的数据一样，但是两个结构体的地址不相等，以地址为key的话两个数据一样的结构体对象都要被插入到哈希表中。
2. 闭散列补充
闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，我们可以把数据存放到冲突位置中的“下一个” 空位置中去。那么如何寻找下一个空位置呢？
1.1 线性探测
从发生冲突的位置开始，依次向后线性探测，直到寻找到下一个空位置为止。
插入数据：
通过哈希函数获取待插入元素在哈希表中的起始位置。
如果该位置中没有元素则在此直接插入新元素，如果该位置中有元素发生哈希冲突，则依次往后寻找下一个空位置，最后插入新元素。
对于线性探测，一旦发生哈希冲突，并且所有的冲突连在一起，很容易产生数据“踩踏”效应。即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
删除数据：采用闭散列处理哈希冲突时，不能随便物理地删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如上图中删除元素4，如果直接删除掉，44查找起来会受到影响。因此线性探测采用标记的伪删除法来删除一个元素。
// 哈希表每个空间给个枚举的标记 enum State { EMPTY, //表示此位置为空 EXIST, //表示此位置已经有元素 DELETE,//表示此位置已经删除 };
1.2 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找。二次探测为了避免该问题，更改了寻找下一个空位置的方法：
3. 除留余数法的闭散列线性探测哈希表模拟实现
下面我们模拟实现一个哈希表：
哈希函数使用除留取余法。
解决哈希冲突的方法是闭散列的线性探测。
哈希表中元素不允许冗余，即key相同的元素只能存在一个。
3.1 基本框架
在哈希表主体中的第三个模板参数GetHashKey是一个仿函数类型，作用是把数据的key转换成整型，key就是整型的话可以不用传，使用默认的就行；因为string类型也常用来作key，所以我们可以专门搞一个string类型的特化仿函数来处理key为字符串类型的情况。
// 把key转化为整型的仿函数 template<class K> struct HashKey { size_t operator()(const K& key) { return key; } }; // 当key为string类型时默认调用的特化版本 // 把每个字符的ASCLL码相加得到的整型值作为哈希的key template<> struct HashKey<string> { size_t operator()(const string& s) { size_t sum = 0; for(const auto& e : s) { sum = sum * 131 + e; } return sum; } }; // 枚举，用来表示每一个位置数据的状态 enum State { EXITS, EMPTY, DELATE, }; // 封装哈希表存储数据的类型 template<class K, class V> struct HashData { pair<K, V> _kv; State _state = EMPTY; }; // 哈希表主体，包含哈希表增删查改功能 template<class K, class V, class GetHashKey = HashKey<K>> class HashTable { typedef struct HashData<K, V> HashData; private: size_t _n = 0;// 当前有效元素个数 vector<HashData> _table;// 存储数据的数组 };
注意事项
使用typedef给结构体类型重命名时，不能直接用结构体名，还应该加上struct关键字，类的话就不用加：
3.2 查找数据
- 先通过除留取余法计算得到key的地址。
- 线性往后逐个探测每一个位置的状态，直到走到空位置为止。如果期间找到key，且状态为EXITS，说明找到了，返回这个位置的数据。
//查找数据 HashData* Find(const K& key) { // 1、一个有效数据都没有的话就直接返回空 if(_n == 0) { return nullptr; } // 2、通过输入的key线性探测，如果如果为空都没有找到说明不存在 GetHashKey kot; size_t index = kot(key) % _table.size(); while(_table[index]._state != EMPTY) { if(_table[index]._state == EXITS && _table[index]._kv.first == key) { return &_table[index]; } ++index; index %= _table.size(); } return nullptr; }
注意事项
线性探测每一次下标加一后，还要模上表的长度，确保index在表的范围内。
哈希表的长度是_table.size()，而不是_table.capacity()。因为顺序表的operator[ ]内部检查的是index必须小于size()。
3.3 插入数据
- 第一步先检查key是否已经已经存在于哈希表中。
- 不在的话就要插入了，插入之前先保证哈希表的空间足够。
- 根据除留取余法找到初始的位置，如果为EMPTY直接插入，否则线性探测找到空位置插入。
// 插入数据 bool Insert(const pair<K, V>& kv) { // 1、先查找要插入的key是否已经存在，存在的话就不能再插入了 if(Find(kv.first)) { return false; } // 2、元素已经确认要插入，接下来需要检查空间是否足够 // a、空间为0，默认开10个空间 // b、负载因子超过0.7，增容确保有适量的空位置 if(_table.size() == 0)// PS：不能用_n判断 { _table.resize(10); } else if((double)_n / (double)_table.size() > 0.7) { HashTable<K, V, GetHashKey> newHashTable; newHashTable._table.resize(_table.size() * 2); for(const auto& e : _table) { if(e._state == EXITS) { newHashTable.Insert(e._kv); } } _table.swap(newHashTable._table); } GetHashKey kot; size_t index = kot(kv.first) % _table.size(); while(_table[index]._state == EXITS) { ++index; index %= _table.size(); } _n++; _table[index]._kv = kv; _table[index]._state = EXITS; return true; }
注意事项
1.判断表的长度是否为0时（我们没有写构造函数去初始化表的长度，所以表的长度刚创建时为0），不能用_n == 0 来判断，要用_table.size()来判断，不然扩容时newHashTable插入数据会出错，因为newHashTable的空间是扩过容，但是没有效数据的。
2. 负载因子大于0.7时，不能直接遍历旧表把它所有位置的元素都插入到新哈希表中，而是应该插入旧表中状态为EXITS的有效数据：
3.4 删除数据
- 先找到找到相应的key数据。
- 找到后把该位置的状态改为DELETE
// 删除数据 bool Erase(const K& key) { HashData* ret = Find(key); if(ret) { --_n; ret->_state = DELATE; return true; } return false; }
3.5 完整代码以及结果测试
HashTable.h
#pragma once #include <iostream> #include <string> #include <vector> using namespace std; // 把key转化为整型的仿函数 template<class K> struct HashKey { K operator()(const K& key) { return key; } }; // 当key为string类型时默认调用的特化版本 // 把每个字符的ASCLL码相加得到的整型值作为哈希的key template<> struct HashKey<string> { size_t operator()(const string& s) { size_t sum = 0; for(const auto& e : s) { sum = sum * 131 + e; } return sum; } }; // 枚举，用来表示每一个位置数据的状态 enum State { EXITS, EMPTY, DELATE, }; // 封装哈希表存储数据的类型 template<class K, class V> struct HashData { pair<K, V> _kv; State _state = EMPTY; }; // 哈希表主体，包含哈希表增删查改功能 template<class K, class V, class GetHashKey = HashKey<K>> class HashTable { typedef struct HashData<K, V> HashData; public: // 插入数据 bool Insert(const pair<K, V>& kv) { // 1、先查找要插入的key是否已经存在，存在的话就不能再插入了 if(Find(kv.first)) { return false; } // 2、元素已经确认要插入，接下来需要检查空间是否足够 // a、空间为0，默认开10个空间 // b、负载因子超过0.7，增容确保有适量的空位置 if(_table.size() == 0)// PS：不能用_n判断 { _table.resize(10); } else if((double)_n / (double)_table.size() > 0.7) { HashTable<K, V, GetHashKey> newHashTable; newHashTable._table.resize(_table.size() * 2); for(const auto& e : _table) { if(e._state == EXITS) { newHashTable.Insert(e._kv); } } _table.swap(newHashTable._table); } GetHashKey kot; size_t index = kot(kv.first) % _table.size(); while(_table[index]._state == EXITS) { ++index; index %= _table.size(); } _n++; _table[index]._kv = kv; _table[index]._state = EXITS; return true; } // 删除数据 bool Erase(const K& key) { HashData* ret = Find(key); if(ret) { --_n; ret->_state = DELATE; return true; } return false; } // 查找数据 HashData* Find(const K& key) { // 1、一个有效数据都没有的话就直接返回空 if(_n == 0) { return nullptr; } // 2、通过输入的key线性探测，如果如果为空都没有找到说明不存在 GetHashKey kot; size_t index = kot(key) % _table.size(); while(_table[index]._state != EMPTY) { if(_table[index]._state == EXITS && _table[index]._kv.first == key) { return &_table[index]; } ++index; index %= _table.size(); } return nullptr; } // 打印哈希表数据 void PrintfHashTable() { for(const auto& e : _table) { if(e._state == EXITS) { cout<<'<'<<e._kv.first<<", "<<e._kv.second<<'>'<<endl; } } } private: size_t _n = 0;// 当前有效元素个数 vector<HashData> _table;// 存储数据的数组 };
Test.cpp
#include "HashTable.h" void TestHashTable() { HashTable<string, size_t> table; string arr[] = {"苹果", "香蕉", "菠萝", "苹果", "香蕉", "菠萝", "橘子"}; for(const auto& e : arr) { HashData<string, size_t>* ret = table.Find(e); if(ret) { ret->_kv.second++; } else { table.Insert(make_pair(e, 1)); } } table.PrintfHashTable(); } int main() { TestHashTable(); return 0; }
编译运行：
4. 除留余数法的开散列哈希表模拟实现
开散列法又叫链地址法(拉链法)，首先对关键码集合用哈希函数计算得到对应的地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中：
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
4.1 基本框架
首先我们声明了一个模板类型struct HashNode作为每一个桶中链起来的节点，它的成员包括：
_kv：类型为pair<K, V>，即需要存到哈希表中的键值对类型数据。
_next：指向下一个节点地址的指针变量。
而哈希表的主体calss HastTable中有两个成员变量：
_n：用来记录表中有效数据个数。
_table：存储HashNode*类型地址的顺序表，其中每一个元素指向单链表的第一个节点·。
template<class K, class V> struct HashNode { HashNode(const pair<K, V>& data) :_kv(data) ,_next(nullptr) {} pair<K, V> _kv; struct HashNode* _next; }; template<class K> struct GetHashKey { size_t operator()(const K& key) { return key; } }; template<> struct GetHashKey<string> { size_t operator()(const string& s) { size_t ret = 0; for(const auto e : s) { ret = ret * 131 + e; } return ret; } }; template<class K, class V, class GetHashKey = HashKey<K>> class HashTable { typedef struct HashNode<K, V> HashNode; private: size_t _n = 0; vector<HashNode*> _table; };
4.2 查找数据
通过除留余数法计算key值的位置，即单链表的第一个节点的位置。
遍历单链表中所有节点的key，看是否有对应的。
有的话返回对应的HashNode节点，没有的话返回nullptr。
// 通过key查找哈希表中的数据 HashNode* Find(const K& key) { // 有效数据为0的话直接退出 if(_n == 0) return nullptr; // 1、通过除留余数法计算key的地址 GetHashKey kot; size_t index = kot(key) % _table.size(); // 2、遍历单链表中所有节点的key，看是否有对应的 if(_table[index]) { HashNode* cur = _table[index]; while(cur) { if(cur->_kv.first == key) { return cur; } else { cur = cur->_next; } } } // 遍历完单链表也没有找到说明不存在，返回空即可 return nullptr; }
4.3 插入数据
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，可能会导致每个桶中链表节点非常多，影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，必定会发生哈希冲突，因此，在元素个数刚好等于桶的个数（即负载因子为1）时，可以给哈希表增容。
具体增容操作：
开辟一块更大空间的顺序表：newTable。
遍历旧的_table，把里面挂的所有节点的key值通过除留取余法映射得到它们在newTable中的桶位置，并挂到新表的桶中。注意这里没必要采用上面闭散列的方法重新创建一个新的大容量开散列哈希表对象，然后调用HashTable::Insert()插入数据到新表中，这样存在有节点的申请、释放开销，得不偿失。
使用std::vector::swap()函数交换_table和newTable的内容。
bool Insert(const pair<K, V>& data) { if(Find(data.first)) return false; GetHashKey kot; if(_n == _table.size()) { size_t length = _table.size()==0 ? 10 : 2 * _table.size(); vector<HashNode*> newTable(length, nullptr); for(size_t i = 0; i < _table.size(); ++i) { if(_table[i]) { HashNode* cur = _table[i]; while(cur) { HashNode* next = cur->_next; size_t index = kot(data.first) % length; cur->_next = newTable[index]; newTable[index] = cur; cur = next; } _table[i] = nullptr; } } _table.swap(newTable); } size_t index = kot(data.first) % _table.size(); HashNode* newNode = new HashNode(data); newNode->_next = _table[index]; _table[index] = newNode; ++_n; return true; }
4.4 删除数据
通过除留取余法找到key值对应的桶的位置。
记录好前一个节点prev，cur从第一个节点开始往后找要删除的节点。
删除节点之前要先连接好prev和cur的后一个节点。
bool Erase(const K& key) { if(_table.size() == 0) return false; GetHashKey kot; size_t index = kot(key) % _table.szie(); HashNode* prev = nullptr; HashNode* cur = _table[index]; while(cur) { if(cur->_kv.first == key) { if(prev == nullptr) { _table[index] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } else { cur = cur->_next; } } return false; }
补充说明
删除一个单链表节点的方法除了记录前一个节点的地址prev外，还有一种替换法删除，即不定义prev，仅仅知道待删除节点cur，我们把cur后一个节点的数据拷贝给cur，然后删除后一个节点即可，但这种方法不适用于最后一个节点的删除。
4.5 完整代码以及结果测试
HashTable.h
#include <iostream> #include <string> #include <vector> using namespace std; template<class K, class V> struct HashNode { HashNode(const pair<K, V>& data) :_kv(data) ,_next(nullptr) {} pair<K, V> _kv; struct HashNode* _next; }; template<class K> struct HashKey { size_t operator()(const K& key) { return key; } }; template<> struct HashKey<string> { size_t operator()(const string& s) { size_t ret = 0; for(const auto e : s) { ret = ret * 131 + e; } return ret; } }; template<class K, class V, class GetHashKey = HashKey<K>> class HashTable { typedef struct HashNode<K, V> HashNode; public: // 通过key查找哈希表中的数据 HashNode* Find(const K& key) { // 有效数据为0的话直接退出 if(_n == 0) return nullptr; // 1、通过除留余数法计算key的地址 GetHashKey kot; size_t index = kot(key) % _table.size(); // 2、遍历单链表中所有节点的key，看是否有对应的 if(_table[index]) { HashNode* cur = _table[index]; while(cur) { if(cur->_kv.first == key) { return cur; } else { cur = cur->_next; } } } // 遍历完单链表也没有找到说明不存在，返回空即可 return nullptr; } bool Insert(const pair<K, V>& data) { if(Find(data.first)) return false; GetHashKey kot; if(_n == _table.size()) { size_t length = _table.size()==0 ? 10 : 2 * _table.size(); vector<HashNode*> newTable(length, nullptr); for(size_t i = 0; i < _table.size(); ++i) { if(_table[i]) { HashNode* cur = _table[i]; while(cur) { HashNode* next = cur->_next; size_t index = kot(data.first) % length; cur->_next = newTable[index]; newTable[index] = cur; cur = next; } _table[i] = nullptr; } } _table.swap(newTable); } size_t index = kot(data.first) % _table.size(); HashNode* newNode = new HashNode(data); newNode->_next = _table[index]; _table[index] = newNode; ++_n; return true; } bool Erase(const K& key) { // 有效数据个数为0时直接退出，删除失败 if(_n == 0) return false; // 1、通过除留取余法找到key值对应的桶的位置 GetHashKey kot; size_t index = kot(key) % _table.szie(); // 2、记录好前一个节点prev，从第一个节点cur开始往后找要删除的节点。 HashNode* prev = nullptr; HashNode* cur = _table[index]; while(cur) { if(cur->_kv.first == key) { if(prev == nullptr) { _table[index] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } else { cur = cur->_next; } } // 遍历完单链表后依然没有找到说明不存在该节点，删除失败 return false; } void PrintHashTable() { for(size_t index = 0; index < _table.size(); ++index) { if(_table[index]) { HashNode* cur = _table[index]; while(cur) { cout<<'<'<<cur->_kv.first<<", "<<cur->_kv.second<<'>'<<endl; cur = cur->_next; } } } } private: size_t _n = 0; vector<HashNode*> _table; };
Test.cpp
#include "HashTable.h" void TestHashTable() { HashTable<string, size_t> table; string arr[] = {"苹果", "香蕉", "菠萝", "苹果", "香蕉", "菠萝", "橘子"}; for(const auto& e : arr) { HashNode<string, size_t>* ret = table.Find(e); if(ret) { ret->_kv.second++; } else { table.Insert(make_pair(e, 1)); } } table.PrintHashTable(); } int main() { TestHashTable(); return 0; }
编译运行：
四. 开散列与闭散列比较
各方面看来开散列是要比闭散列好的：
开散列比闭散列实现起来更简单。闭散列还需要给表的每一个位置设置状态。
开散列比闭散列空间利用率更高。应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于闭散列必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，至少有30%的空间浪费，当数据足够多时这些浪费的表项所占空间会比指针大的多，所以使用链地址法反而比闭散列节省存储空间
极端情况下开散列的数据处理效率会更高。这里的极端情况是指所有数据都映射到同一个位置，这种情况不是增容能解决的，查找数据时，闭散列的查找效率降为O(N)，而开散列可以通过改造使查找效率变为O(logN)。
