哈希表
哈希表的概念
我们现在来假设一下有一个电话本，需要存储名字/电话，那么一般来说会创建一个电话对象，电话对象有两个属性：名字和电话，并将这个电话对象存储到数组当中。当我们需要查找某一个电话的时候，就需要遍历数组，那么这个时间复杂度就为O(n)。如果每一次查找都需要遍历一遍数组，那么这个效率也太低了，如何来提高查找效率呢？
这时候就出现了一个新的数据结构：Hash表。Hash表也称散列表，也有直接译作哈希表，Hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性，它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。
回到上面的电话本如果使用哈希表来存储，以名字为key，电话为value，那么我们只要知道这个key，就可以知道它所对应的value，这个查找的时间复杂度就近似O(1)了。
什么事哈希表?
哈希表(Hash Table)又称为散列表。哈希表是一种可以根据以key-value键值对形式存储数据的数据结构，可以通过关键字Key直接找到数据Value的存储位置，而不需要经过任何的遍历和比较。哈希表_百度百科
哈希表中的四个概念
- 关键字(Key) — 哈希表通过一个信息(Key)来查找另外一个信息(Value)，将两个信息在表中形成映射关系，而关键字就是我们要提供的信息；
- 值(Value) — 存储的值；
- 哈希函数 — 哈希函数是构建哈希表的工具，是key和对应的value的存储位置的一个映射关系，通过把key代入到哈希函数中进行计算，就可以得到value在哈希表中的存储位置；
- 哈希地址 — 哈希地址记录的是我们所需要的数据在哈希表中的存储位置，哈希地址只是单纯的表示哈希表中的存储位置，不是实际的物理存储位置。
关键字、值、哈希函数、哈希地址、哈希表之间的关系？
哈希表是通过哈希函数来构建的，假设哈希函数为f()，而key就是x，既f(x)。那么在经过哈希函数的计算之后可以求出一个值，这个值就是key所对应的值(value)的存储地址，也就是哈希地址。而记录这整个Key-Value信息的表就是哈希表。
还是这个电话本，该电话本以拼音的首字母来区分数据，记录了人名和其电话号码，那么转换成哈希表，拼音首字母可以看成是哈希地址，人名为key，电话为value。
- 哈希地址 key value
- A 爱丽丝 13000000000
- B 包丽丝 13000000000
- C 陈丽丝 13000000000
- D 大丽丝 13000000000
- ……
我们现在把这个电话本代入到我们上面的解析：f(爱丽丝) = A，f(包丽丝) = B等。就是我们知道了爱丽丝，并通过哈希函数计算出了其所代表的哈希地址为A，那么我们就知道了电话的存储地址进而知道爱丽丝的电话号码，那么现在我们就不要遍历整个表就可以直接得到我们先要的数据了。
哈希冲突
因为哈希地址是通过哈希函数和key计算出来的，那么就有可能出现两个不一样的key计算出来的哈希地址是一样的，这种情况就是哈希冲突。回到电话本就是现在有一个爱丽丝，同时还有一个艾热，它们两者的拼音首字母都是A，这就意味着它们同时都存在电话本的A区，那么这就存在冲突了。
有人说上面会冲突是因为我们的算法不够复杂而导致的，其实这是对的也是错的。如果当我们的地址无限大的同时可以保证我们的算法足够复杂不会导致重复，那么哈希冲突就不会出现的。但通常情况下，关键字的合集是大于地址合集的。
地址合集是有限的，这就意味着哈希函数是一个压缩映象，那么哈希冲突是根本无法避免的。我们可以做的只是尽量避免冲突，所以我们可以将冲突的水平平均化，把关键字映射到地址集合中的每个一地址的概率是相等的，也就是我们后面会说到的均匀的哈希函数。
哈希表的大小
哈希表的大小也是构建哈希表的一个关键点，如果哈希表的空间远远大于最后实际存储的记录个数，则会造成很大的空间浪费，如果选小了，那么就会很容易造成哈希冲突。在实际的应用中，一般都是根据最终记录存储的个数和关键字分布的特点来确定哈希表的大小，但如果事先不知道存储个数的话，则需要动态维护哈希表的容量，此时可能需要重新计算哈希地址。
哈希表的平均查找长度
Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。
- 查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数； 查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。
哈希表的优缺点
优点：可以提供快速插入和查找操作，无论有多少数据项，插入与查找只需接近常量的时间：O(1)时间级。而且编程很容易实现。
缺点：它是基于数组的，数组一旦被创建，就难以拓展；某些哈希表的填充因子（填入的元素个数/哈希表长度)过大，性能会急剧下降。
关于哈希表的性能
由于哈希表高效的特性，查找或者插入操作在大多数的情况下都是达到O(1)，时间主要是花在计算哈希地址上，但也会有一种最坏的情况就是哈希地址全都映射到同一个地址上面，即每一个都有冲突，那么在解决冲突的情况下浪费大量的时间。
常见的哈希函数构造方法
怎样才算一个好的哈希函数？
- 均匀的哈希函数： 若对于关键字集合中任一关键字，经过哈希函数映射到地址集合的任何一个地址的概率都是相等的，则称此类函数为均匀的(Uniform)哈希函数，从而减少哈希冲突。
- 如何判断一个哈希函数的优劣：
- 能否将关键字均匀映射到哈希空间上
- 有没有好的解决冲突的方法
- 计算哈希函数是否简单高效
常见的六个构建哈希函数的方法
常见的哈希函数构建思路有六个:
- 直接定值法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
直接定值法
直接定值法的哈希函数就是一个一次函数，去关键字和关键字的某个线性函数值为哈希地址：
- f (Key) = Key
- f (Key) = a * Key + b
第一种形式的哈希地址就是key本身，而第二种形式中的a/b是常数，通过key和常数的计算来获取哈希地址。这类哈希函数叫做自身函数。
直接定值法的哈希表非常简单，但相对来说哈希冲突出现的情况就会很多，不过在实际的使用中，比较少使用。
数字分析法
如果关键字由多位字符或者数字组成，就可以考虑抽取其中的2位或者多位来作为该关键字对应的哈希地址，在取法上尽量选择变化较多的位，避免发生冲突。 举个栗子： 8 1 3 4 6 5 3 2 8 1 3 7 2 3 4 7 8 1 3 9 7 2 8 7 8 1 4 7 9 7 5 2 … 上面展示了4个关键字，每个关键字都是8位的十进制数字，经过分析我们会发现几个特征：
- 第一位和第二位的值都是固定不变的
- 第三位的值为3/4
- 最后一位的值为2/7
综上所述，只有中间4位数的值接近随机。所以为了避免冲突，我们从这4位中取任意两位或者取其中两位和另外两位的和，再做舍去进位处理后得到的结果作为哈希地址。
平方取中法
平方取中法是对关键字做平方操作，取中间几位作为哈希地址(此方法是比较常用的构造哈希函数的方法) 。 例如关键字序列为{421，423，436}，对各个关键字进行平方后的结果为{177241，178929，190096}，我们则可以取中间的两位{72，89，00}作为其哈希地址。
折叠法
折叠法是将关键字分割成位数相同的几个部分(最后一部分的位数可以不同)，然后取这几部分的叠加和（舍去进位）作为哈希地址。关键字位数很多，且关键字每一位上数字分布大致均匀时，可以采用折叠法。折叠又可以分为两种：
- 移位折叠 (移动折叠是将分割后的每一部分的最低位对齐，然后相加)
- 间界折叠 (间接叠加是从一端向另一端来回折叠，然后相加) 举个栗子： 现有图书馆中某藏书的编号为0-442-20586-4，先对其分别采用移位折叠(a)和间界折叠(b)。如下图
- (a) 移位折叠将图书编号作为关键字，分割为几个小的部分，然后以最低位对齐，然后相加，再舍去进位，得4位数作为哈希地址
- (b) 间界折叠就类似于折纸的步骤。从一端向另一端折叠。同样是分割几个小的部分，然后最低位对齐，相加，舍去进位。与移位折叠不同的是，分割部分的数字序列顺序不同。
除留余数法
若已知整个哈希表的最大长度 m，可以取一个不大于 m 的数 p，然后对该关键字 key 做取余运算，即f(key) = key % p.
除留余数法也是最常用，也最简单的哈希函数构造方法，它不仅可以直接去模，也可以先折叠，平方取中后再去模(结合几个方法)。
注意：
除留余数法对p有很高的要求。若p选取的不好，很容易产生同义词。由以往经验可得，p一般取质数或不包含小于20的质因数的合数
随机数法
即取关键字的一个随机函数值作为它的哈希地址，如f(key) = random(key)。
注意：
这里的随机函数其实是伪随机函数，真随机函数是即使每次给定的 key 相同，但是 H（key）都是不同；而伪随机函数正好相反，每个 key 都对应的是固定的 H（key）。
常见哈希冲突的解决方法
在哈希表的构建过程中，哈希冲突是无法避免的，那么必须采取适当的方法去处理这写冲突。这是常见的哈希冲突解决方法:
- 开发定址法
- 再哈希法
- 链地址法(拉链法，位桶法)
- 公共溢出区
开发定址法
H = (f(key) + d) MOD m; // 这里可以看做是f(key) + d
f(key)是哈希函数，m是哈希表的长度，d是一个增量，d这里可以有三种取值:
- 线性探测法(线性探测再散列): d = 1,2,3,4…,m-1;
- 二次探测法(二次探测再散列): d = 1^2,-(1^2),2^2,-(2^2)…,k^2,-(k^2) (k<=m-1)
- 伪随机数探测法(伪随机探测再散列): d = 伪随机序列
现有一个长度为11的哈希表，已填有关键字分别为17、60、29三条记录。其中采用的哈希函数为
f(key) = key MOD 11。现有第四个记录，关键字为38。根据原有的哈希算法，得出的哈希地址为5，跟关键字60的哈希地址一样，产生了冲突，根据增量d的取法不同，有一下三种情况:
- 线性探测法:当发生了冲突，使用线性探测法
f(key) + d，所以首先得出的是5 + 1 = 6得到下一个地址为6，但因为已经存在数据了再冲突，d就向下一位取，以此类推，最后得到空闲的哈希地址8，所以最后将数据填入哈希地址为8的空闲区域； - 二次探测法:首先d取值1^2，得到d = 1，得到哈希地址为6有冲突，取下一个数值-1^2，得到d = -1，哈希地址为4的空闲区域；
- 伪随机数探测法:就是将d的取值交由伪随机数列来决定。 缺点:
- 线性探测法不利于查找，但可以保证只要哈希表没有被填满，就一定可以找到一个不发生冲突的位置；
- 二次探测法只有在哈希表长度m在
4j+3 // j为整数的素数时才能使用； - 随机数探测法取决于伪随机序列。
链地址法(拉链法，位桶法)
将产生冲突的关键字的数据存储在冲突哈希地址的一个线性链表中。
例如有一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79} ，其哈希函数:f (key)=key MOD 13，使用链地址法所构建的哈希表如图：
01,14,27,79 Mod 13 的都得1，所以将它们对应的数据都存储在哈希地址为1的一个线性链表中。
再哈希法
再哈希法就是如果发生了冲突，则使用另外一个哈希函数来计算该关键字的地址，直到不发生冲突。此方法会增加计算时间。
公共溢出区
建立一个公共溢出区，将产生冲突的数据都放到公共溢出区中。即：建立两张表，一张为基本表，另外一张为溢出表，基本表存放的是没有发生冲突的数据，溢出表存放的是发生冲突的数据，不管关键字通过哈希函数得到的哈希地址为什么，只要发生了冲突，都存放到溢出表中。
哈希表的一些实现
这里使用c++来创建一个哈希表:
/*
哈希表的实现
这里解决哈希冲突使用的是拉链法(同一哈希地址的value都放进一个链表中)
*/
#define HASHTABLESIZE 10 // 哈希表的大小
typedef struct Node {
const char *key;
const char *value;
struct Node *next;
} Node;
class HashTable {
private:
Node *node[HASHTABLESIZE];
public:
HashTable(); // 构造方法
~HashTable(); // 析构函数
unsigned hash(const char *key); // 哈希函数
Node *lookup(const char *key); // 查找节点
bool add(const char *key, const char *value); // 添加
const char *get(const char *key); // 获取value
void display(); // 显示所有的节点
};
构造函数:
// 构造函数
HashTable::HashTable() {
for (int i = 0; i < HASHTABLESIZE; i++) {
node[i] = NULL; // 初始化节点
}
}
// 析构函数
HashTable::~HashTable() {
for (int i = 0; i < HASHTABLESIZE; i++) {
node[i] = NULL;
}
}
哈希函数，这里采用的是time33算法:
// 哈希算法
unsigned HashTable::hash(const char *key) {
unsigned hash = 0;
for (; *key; ++key) {
hash = hash * 33 + *key;
}
return hash % HASHTABLESIZE;
}
查找节点的方法:
定义一个查找节点的方法，首先使用hash函数计算出下标(哈希地址)，然后根据头地址向下去一个个查找节点，如果节点的key值与目标key值相同，则匹配成功。这里查找的方法因人而已，因为我这里采用的是拉链法来解决哈希冲突，使用一个链表来存储那些冲突的value，所以计算出哈希地址之后也需要遍历列表来查找对应的值。
// 查找
Node * HashTable::lookup(const char *key) {
Node *np;
unsigned index;
index = hash(key); // 下标
// 查找链表
for (np = node[index]; np; np = np->next) {
if (!strcmp(key, np->key)) {
return np;
}
}
return NULL;
}
添加节点的方法：
首先使用lookup方法来查找是否已存在对应的key值，如存在则直接修改value，否则插入一个新的节点，这里需要注意的是哈希冲突，如果哈希地址已存在值，那么将节点的node->next指向原本的值，并将哈希表node[i]指向新的值。
// 添加
bool HashTable::add(const char *key, const char *value) {
unsigned index;
Node *np;
if (!(np = lookup(key))) { // 该key没有存在
index = hash(key);
np = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
if (!np) {
// 没有创建成功
return false;
}
np->key = key;
np->next = node[index]; // 指向原本的节点
node[index] = np;
}
np->value = value;
return true;
}
小结:
这是一个比较哈希表比较简单的实现，有很多东西都没有考虑到，但哈希表的基本实现就是这样了，其他无非就是解决哈希冲突和哈希函数的选择，还有当哈希表的填充因子变大时的处理。
GitHub - HQL-yunyunyun/HQLHashTable