哈希及其模拟实现

1.哈希的概念

顺序结构以及平衡树中，元素的关键码与其存储位置之间没有对应的关系。因此，在查找一个元素时，必须要经过关键码的多次比较。顺序查找的时间复杂度为O(N)，平衡树中为树的高度，即O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

1.1 哈希思想

哈希(Hash)是一种映射思想，规定存在一个唯一的哈希值与键值之间建立映射关系，由这种思想而构成的数据结构称为哈希表。

哈希表中查找数据的时间复杂度可以做到O(1)，这是非常高效的，比AVL树还要快。

哈希表中插入和查找数据的具体操作如下：
插入数据：根据当前待插入的元素的键值，计算出哈希值，并存入到相应的位置中。
查找元素：根据待查找元素的键值，计算出哈希值，判断对应的位置中存储的值是否与键值相等。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称为散列表)。

例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key)=key%capacity；capacity为存储元素底层空间总的大小。

显然，这个哈希表并没有把所有的位置都填满，数据分布无序且分散。因此，哈希表又称为散列表。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？这就是下面要介绍的哈希冲突。

1.2 哈希冲突

对于两个数据元素的关键字Ki和Kj(i!=j)，有Ki!=Kj，但有Hash(Ki)==Hash(Kj)，即不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或者哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢？
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：
1、哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表运允许有m个地址时，其值域必须在0到m-1之间；
2、哈希函数计算出来的地址能均匀分布在整个空间中；
3、哈希函数应该比较简单。

1.3 常见的哈希函数

1.3.1 直接定址法--(常用)

取关键字的某个线性函数为单列地址：Hash(Key)=A*Key+B。
优点：简单、均匀；
缺点：需要事先知道关键字的分布情况；
使用场景：适合找比较小且连续的情况。

1.3.2 除留余数法--(常用)

设散列表中允许的地址数位m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key)key%p(p<=m)，将关键码转换成哈希地址。
除了以上两种常见的哈希函数之外，还有平方取中法、折叠法、随机数法、数学分析法。

2.哈希冲突

哈希冲突（哈希碰撞）是面试中的常客，可用通过一个哈希冲突间接引出哈希中的其他知识点。

2.1哈希冲突产生的原因

哈希值是键值通过哈希函数计算得出的位置标识符，难以避免重复的问题。比如在下面的哈希表中，存入元素20，哈希值HashI=20%8=4，此时4位置中并没有元素，可以直接存入。

但是如果继续插入元素36，哈希值HashI=36%8=4，此时，4位置处已经有了元素20了，无法继续存入，此时就发生了哈希冲突。

不同的哈希函数引发哈希冲突的概率不同，但最终都会面临哈希冲突这个问题，因此需要一些方法来解决哈希冲突。

2.2 哈希冲突的解决方法

解决哈希冲突两种常见的方法是：闭散列和开散列。

2.2.1 闭散列解决哈希冲突

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去。那如何寻找下一个空位置呢？有两种常见的方法，1、线性探测；2、二次探测。

2.2.1.1 线性探测

如下的场景中，现在需要插入元素36，先通过哈希函数计算哈希地址，hashAddr为4。因此，36理论上应该插在该位置，但是该位置已经存放了值为20的元素，即发生哈希冲突。此时，继续向后探测、找到可用的位置。如下图所示，将36存入位置0处。

规定：当哈希表中存储的数据量与哈希表的容量的比值（负载因子）过大时，扩大哈希表的容量，并重新进行映射。
线性探测：因为有负载因子的存在，所以哈希表一定是有剩余空间的。当发生哈希冲突时，从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

1. 插入
   (1)通过哈希函数获取待插入元素在哈希表中的位置。
   (2)如果该位置没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
2. 2、删除
   采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已经有的元素，若直接删除元素会影响其他元素的搜索。比如直接删除元素4，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

负载因子=存储的有效数据个数/空间的大小
负载因子越大，冲突的概率越高，增删查改的效率越低；
负载因子越小，冲突的概率越低，增删查改的效率越高，但是空间利用率低，浪费多。
负载因子<1，就能保证发生哈希冲突时一定能找到空位置。

2.2.1.2 线性探测的代码实现

存储数据结构的定义：闭散列中存储的数据至少包含两个信息：键值对、状态表示。键值对既可以是K也可以是K/V，我们这里实现的是K/V。

（1）状态

区分哈希表的一个位置有没有数据，如果用两种状态标识，在(1)或不在(0)，那么就会带来两个问题：
1、0表示不在，那么如何存储数据0呢？
2、如果数据发生冲突，当前位置和后面位置都存放的是冲突数据，假如当前位置的数据被删除了，那么查找key时发现当前位置状态为不在时，那么就不会再向后查找了。
因此，要用3个状态位分别表示空、已存在、已删除，用枚举表示状态位。
①空EMPTY--初始状态；
②存在EXITS--插入数据后的状态；
③删除DELETE--删除数据后的状态。
其实也可以分为可用/不可用两种状态，细分出EMPTY与DELETE是为了在进行探测时，提高效率。
探测时，如果探测到空，就不必再往后继续探测了，因为后面必然不存在我们想要找的数据。如果存在，这里就不会为空了。
所以闭散列中的存储数据结构可以用一个结构体定义。

//枚举表示某位置的状态
enum State
{EMPTY,EXITS,DELETE,
};

（2）定义HashData

哈希数据应包含两个成员：数据和状态。

//定义结构体存储数据
template<class T>
struct HashData
{T _data;State _state;
};

（3）哈希表

哈希表包含两个成员：哈希数据、存储的有效数据的个数，模板有3个参数K，T，KeyOfT。
①由于不知道key是K还是pair，所以需要定义两个模板参数K、T来包含key是K或者pair的两种情况；
②由于不知key的数据类型是int还是string、pair、struct，计算key的映射位置时需要取模，但是只能对int类型进行取模，string、pair、struct无法直接取模，KeyOfT作为仿函数，它的实例可用分别应对这些类型的取模。

//定义一个哈希表类
template<class K,class T,class KeyOfT>
class MyHashTable
{typedef HashTable<T> HashData;
public://...private:vector<HashData> _tables;//底层顺序表，用于存储数据size_t _num = 0;//保存的有效数据的个数
};

（4）查找函数

①无论传给哈希表的数据是K还是pair，查找时，都需要用K做key来进行查找；
②计算元素位置；
③如果当前位置元素为key，那么就返回该元素，否则可能发生了冲突，继续向后探测。

//1、查找数据
HashData* Find(const K& key)
{if (_tables.size() == 0)return nullptr;KeyOfT keyoft;size_t hashI = key % _tables.size();//取余查找位置//线性探测size_t i = 1;size_t index = hashI;while (_tables[index]._state != EMPTY){if (keyoft(_tables[index]._data) == key&& _tables[index]._state == EXITS){return &_tables[index];}//如果哈希表中的值与key值不相等，或者与key值相等，但是_state为DELETE，//则继续往后查找index = hashI + i;//线性查找  //index=hashI+i*i;//二次查找index %= _tables.size();//取余防止越界++i;//如果已经查找一圈，那么说明全是存在+删除if (index == hashI){break;}}return nullptr;
}

（5）插入函数

①根据额键值计算出下标(哈希值)；
②线性探测，找到可用的位置[空/删除]；
③插入数据，有效数据量+1。

//2、插入一个数据
bool Insert(const T& data)
{KeyOfT keyoft;if (Find(keyoft(data)))return false;//扩容//假如负载因子大于或者等于7时，以及哈希表的容量为0时，则需要进行扩容操作。//此时，在计算负载因子时应注意哈希表容量的大小不能为0。//取余查找位置，计算data中的key值在表中映射的位置size_t hashI = keyoft(data) % _tables.size();//线性探测写法size_t i = 1;size_t index = hashI;//状态为空就插入节点while (_tables[index]._state == EXITS){index = hashI + i;index %= _tables.size();//取余防止越界++i;}_tables[index]._data = data;_tables[index]._state = EXITS;_num++;return true;
}

如果想降低踩踏发生的概率，可用将线性探测改为二次探测。

HashI += (i * i);	//二次探测

以上就是插入操作的具体实现，此时面临着一个棘手的问题：扩容问题。
当数据第一次插入或负载因子达到临界值时，需要进行扩容(因为vector<HashData> _tables一开始为空，所以第一次插入数据时也要扩容)。
当空间扩容后，容量发生了改变，这就意味着数据与下标的映射关系也发生了改变，需要更新数据，即重新进行线性探测。
扩容可分为传统写法和现代写法。
传统写法：

//2、插入一个数据
bool Insert(const T& data)
{KeyOfT keyoft;if (Find(keyoft(data)))return false;//假如负载因子大于或者等于7时，以及哈希表的容量为0时，则需要进行扩容操作。//此时，在计算负载因子时应注意哈希表容量的大小不能为0。if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7){//1、开辟是原旧表2倍大小的新表(不一定是2倍)；//2、遍历旧表的数据，重新计算原旧表数据在新表中的位置；//3、释放旧表//1、写法1：传统的开空间vector<HashData> newtables;//开辟一个新的vector顺序表size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;newtables.resize(newsize);//重新设置newtables的容量大小for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXITS){//计算原旧表数据在新表中的位置，并处理冲突size_t index = keyoft(_tables[i]._data) % newtables.size();while (newtables[index]._state == EXITS){++index;if (index == newtables.size()){index = 0;}}newtables[index] = _tables[i];}}_tables.swap(newtables);}//插入//...
}

传统写法的思路：创建一个容量足够的信标，将原表中的数据映射至新表中，映射完成后，交换新表和原表，目的是为了更新当前哈希表对象中的表。
关于平衡因子的控制：根据别人的试验结果，哈希表中存储的有效数据量超过哈希表容器的70%时，推荐进行扩容。假设容量为M，存储的额有效数据量为N，两者比率N/M==0.7时进行扩容。因为我们这里的容量和数据量都是整数，所以在等式两边*10，可得N*10/M==7。

传统写法比较繁琐，下面来看看现代写法：

//2、插入一个数据
bool Insert(const T& data)
{KeyOfT keyoft;if (Find(keyoft(data)))return false;//假如负载因子大于或者等于7时，以及哈希表的容量为0时，则需要进行扩容操作。//此时，在计算负载因子时应注意哈希表容量的大小不能为0。if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7){//1、开辟是原旧表2倍大小的新表(不一定是2倍)；//2、遍历旧表的数据，重新计算原旧表数据在新表中的位置；//3、释放旧表//写法2：扩容的现代写法MyHashTable<K, T, KeyOfT> newht;size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;newht._tables.resize(newsize);for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXITS){newht.Insert(_tables[i]._data);}}_tables.swap(newht._tables);
}//插入//...
}

其实传统写法中的插入部分逻辑与Insert中的插入操作重复了，因此我们可以借助现代思想，创建一个容量足够的哈希表，将原表中的数据遍历插入新的哈希表中，插入的过程调用Insert，代码很简洁，并且不容易出错。
细节：需不需要将当前对象中的有效数据量_n进行更新？
答案是不需要，往新的哈希表中插入_n个数据，意味着无论是新的哈希表还是当前对象，他们的有效数据量都是一致的，因此不需要更新。

（6）删除

删除操作就十分简单了，获取待删除数据，将其中的状态改为删除--DELETE即可，不必清空数据，只要访问不到就行了。当然，有效数据量-1。

//3、删除一个元素
bool Erase(const T& key)
{HashData* ret = Find(key);if (ret){ret->_state = DELETE;--_num;return true;}else{return false;}
}

像这种线性探测(暴力探测)可用解决哈希冲突的问题，但是会带来新的问题：踩踏。
踩踏：元素的存储位置被别的元素占用了，于是该元素也只能被迫线性探测，引发连锁反应，插入、查找等操作都会越来越慢。哈希冲突越多、效率越低。
优化方案：二次探测，每次向后探测i^2步，尽量减少踩踏。尽管如此，闭散列的实际效果不尽人意。闭散列的实战价值不大，因此只做简单了解即可，真正的重点是开散列。

2.2.2 开散列解决哈希冲突

所谓开散列就是在 原存储位置处 带上一个单链表，如果发生哈希冲突，就将冲突的值依次挂载即可，因此也叫做链地址法、开链法、哈希桶。
开散列中不需要负载因子，开散列的每个桶中存放的都是哈希冲突的元素，如果每个位置都被存满了，直接扩容就好了，当然扩容后也需要重新建立映射关系。
 

开散列中进行查找时，需要先根据哈希值找到对应的位置，并在单链表中进行遍历。一般情况下，单链表的长度不会太长，因为扩容后，整体长度会降低。
如果单链表真的过长了（几十个节点），我们还可以将其转为红黑树，此时效率依旧非常高。

2.2.2.1 哈希仿函数

在闭散列中，已经实现了Hash仿函数，用来获取哈希表中的元素key，方便后续计算映射位置。

//仿函数
template<class K>
struct _Hash
{const K& operator()(const K& key){return key;}
};

模板特化：string元素使用频率较高，进行模板特化。

//特化，针对某些类型进行特殊处理
template<>
struct _Hash<string>
{size_t operator()(const string& key){//BKDR Hashsize_t hash = 0;for (size_t i = 0; i < key.size(); ++i){hash *= 131;hash += key[i];}return hash;}
};

2.2.2.2 存储节点结构的定义

哈希桶中需要维护一个单链表，因此需要一个_next指针指向下一个节点。

template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}
};

因为引入了单链表，所以哈希桶中表的存储类型也变成了节点指针。

template<class K,class T,class KeyOfT,class Hash=_Hash<K>>
class MyHashTable
{typedef HashNode<T> Node;
public://...private:vector<Node*> _tables;size_t _num;//记录表中存储的数据的个数
};

2.2.2.3 析构函数

因为有单链表，所以在对象析构时，需要手动遍历其中的节点，将其释放，避免内存泄漏。

~MyHashTable()
{Clear();
}void Clear()
{for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}
}

为什么哈希表（闭散列）中不需要些析构函数？
因为在闭散列中，表中存储的数据不涉及自定义类型的动态内存管理，并且vector在对象调用默认析构时，会被调用其析构函数，释放其中的内存。

2.2.2.4 查找

先计算key在哈希表中的位置，然后在该位置的哈希桶中遍历查找。

Node* Find(const K& key)
{if (_tables.size() == 0)return nullptr;KeyOfT keyoft;size_t index = HashFunc(key) % _tables.size();Node* cur = _tables[index];while (cur){if (keyoft(cur->_data) == key){return cur;}else{cur = cur->_next;}}return nullptr;
}

2.2.2.5 插入

在进行数据插入时，既可以尾插，也可以头插，因为桶中的存储顺序没有要求。为了操作简单，我们选择头插。同样的，哈希桶在扩容时，也有传统写法和现代写法，这里采用传统写法。

bool Insert(const T& data)
{KeyOfT keyoft;if (Find(data) != nullptr)return false;//如果负载因子等于1，则增容，避免大量的哈希冲突if (_tables.size() == _num){//使用传统的增容写法vector<Node*> newtables;size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();newtables.resize(newsize);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){//整个过程为单链表的头插//将旧表中的节点取下来，并重新计算在新表中的位置，并插入到新表中Node* next = cur->_next;//计算在新表中的位置size_t index = HashFunc(keyoft(cur->_data)) % newtables.size();cur->_next = newtables[index];newtables[index] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}//计算数据在表中映射的位置size_t index = HashFunc(keyoft(data)) % _tables.size();//1、先检查这个值子在不在表中Node* cur = _tables[index];while (cur){if (keyoft(cur->_data) == keyoft(data)){return false;}else{cur = cur->_next;}}//2、头插到挂的链表中（尾插也可以）Node* newnode = new Node(data);newnode->_next = _tables[index];_tables[index] = newnode;++_num;return true;
}

这里的传统写法有一个很巧妙的地方：节点回收，既然旧表中节点不用了，那么我可用直接把其中的节点转移至新表中，这样可用提高效率。

2.2.2.6 删除

①计算key在表中的位置；
②要删除的数据是不是该位置的第一个哈希桶，如果是，那就让哈希表的第一个节点变成第二个桶，否则让这个桶的前一个桶指向这个桶的下一个桶。

bool Erase(const K& key)
{KeyOfT keyoft;size_t index = HashFunc(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[index];while (cur){if (keyoft(cur->_data) == key){if (prev == nullptr){//表示要删除的值在第一个节点_tables[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;
}

完整代码可用参考：哈希及其模拟实现