哈希表-理论知识 | ChailynCui BLOG

type

status

date

slug

summary

哈希表

哈希表数据结构将元素存储在键值对中，其中

Key - 用于索引值的唯一整数

值 - 与键关联的数据。

Key 和 value 是一对一的。例如，学号和姓名是一一对应的，是一对

哈希函数

在哈希表中，使用键来处理新索引。并且,与该键对应的元素存储在索引中。这个过程称为散列（哈希函数）。

设k为键，h(x)为哈希函数。

这里，h(k)将为我们提供一个新索引来存储与k链接的元素。

可以使用余数等对其进行索引。

💡

如何将一些名称转换为索引并将它们存储在哈希表中？

在这个例子中，我们将所有字母的ASCII码相加，然后除以数组的大小，余数作为索引进行排序

这里面可能还有一些其他的属性，我们可以把它们放在一起。

所以你可以将密钥进行计算然后将其转换成地址

💡

这里只是举一些例子，很多种哈希函数，遇到问题，自己想办法解决

对于key是数字的情况，将键除以可用地址的数目n，取余数即可

对于key是字母的情况，可以转换成ASCII码之和再除以可用地址的数目n，取余数即可

如果key过长可以将其分成相等的部分，再相加

比如：电话号码：014528345654，变成01+45+28+34+56+54 = 218再除以可用地址的数目n，取余数即可

哈希冲突

当哈希函数为多个键生成相同的索引时，将出现冲突（要在该索引中存储什么值）。这称为哈希冲突

我们可以这样理解：

我们可以使用以下技术之一解决哈希冲突。

开放式寻址：线性/二次探测和双哈希

通过链接解决碰撞问题

开放地址法

线性探测

线性探测是一种解决哈希冲突的方法。简单来说，当我们要插入一个新的数据项，但发现它应该放的位置已经被其他数据占用了（这就是冲突），我们就会从那个位置开始，一步一步地往后看，直到找到一个空的位置来放这个新的数据项。

举个例子，假设我们有一个大小为10的哈希表，哈希函数是简单的取模运算（比如对10取模）。现在我们要插入数字5、22和37。

插入数字5：5 % 10 = 5，位置5是空的，所以直接放在那里。

插入数字22：22 % 10 = 2，位置2也是空的，所以放在那里。

插入数字37：37 % 10 = 7，但位置7已经被占用了（比如之前插入了其他数据）。这时，线性探测就派上用场了。我们从位置7开始，一步一步地往后看，看哪个位置是空的。如果8还是有值，那就再往后看，直到找到一个不空的值位置（可以循环找）

再举个例子：这里发现Mia和Sue冲突，于是往后找，5是Zoe已经有值，所以往后找在6处放入值

但在查找时也是线性的，我要找Sue，那就从4查起，5,6！找到答案

在线性探测中，我们往往哈希表长度选择上会尽可能大于元素个数，因为这样所有的元素才能都填进去，那么这就存在负载系数可能在70%的情况

聚集

当哈希表越来越满时聚集越来越严重，这导致产生非常长的探测长度，后续的数据插入将会非常费时。通常数据超过三分之二满时性能下降严重，因此设计哈希表关键确保不会超过这个数据容量的一半，最多不超过三分之二。

举个例子：

想象你有一个大型停车场，这个停车场有很多停车位（就像哈希表的桶），每个停车位都有一个唯一的编号（就像哈希函数的输出）。当汽车（就像哈希表中的元素）进入停车场时，它们会根据编号找到对应的停车位。

如果停车场的使用率很低，汽车可以很容易地找到空的停车位，并且停车场内的流动很顺畅。这就像是哈希表中元素很少的情况，查找和插入操作都很快。

但是，随着时间的推移，越来越多的汽车开始进入停车场。如果某些编号的停车位特别受欢迎（可能是因为它们靠近出口或靠近某个设施），这些停车位就会很快被占满。当新的汽车尝试找到停车位时，它们可能需要检查多个编号的停车位才能找到一个空的。这就像哈希表中发生了聚集，导致查找和插入操作需要更长的时间。

线性探测的问题在于，相邻的空被填满。插入新元素时，必须遍历整个集群。这增加了对哈希表执行操作所需的时间。

另外，如果数据数目是动态的，增加了一些值，可能超出我们数组的容量，那么这显然不是一个好的方案。

二次探测

二次探测的基本思想是探测相隔较远的单元，而不是和原始位置相邻的单元。在线性探测中，探测序列通常是连续的，如hash(key)+1，hash(key)+2等。而在二次探测中，探测的下标序列为hash(key)+1²，hash(key)-1²，hash(key)+2²，hash(key)-2²等，以此类推，探测的步长变成了原步长的“二次方”。

通过二次探测，可以更均匀地分布哈希表中的元素，从而提高哈希表的性能，减少了聚集的可能性。

伪随机数序列

使用伪随机数序列：假设伪随机数为 9，则得到下一个地址 H(1) = (9 + 5) % 11 = 3，3 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 3 的位置。

举个例子：

链地址法

在这个方法中，如果哈希函数为多个元素生成相同的索引，则这些元素将使用双向链表存储在同一索引中。

这里举的例子同上图，只不过这里是链表的形式，每个index相同的值加到对应节点的后面，按照顺序，很好理解

那么我们发现加入我们再寻找Rae，从5开始，变的非常容易，next，next！找到了，所以查找变的更容易

将哈希表定义为一个有 m 个头节点组成的链表指针数组 T，这样在插入关键字的时候，只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i，然后将其以链表节点的形式插入到以 T[i] 为头节点的单链表中。在链表中插入位置可以在表头或表尾，也可以在中间。如果每次插入位置为表头，则插入操作的时间复杂度为 O(1)

关于查询，查询操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。对于哈希地址比较均匀的哈希函数来说，理论上讲，k= n/m，其中 n 为关键字的个数，m 为哈希表的表长。

会牺牲一些存储空间（头结点）但同时减少了插入和查询的平均查找长度

哈希函数的目标

减少哈希冲突

哈希值尽可能均匀分布（有利于查找）

计算简单

解决任何发生的哈希冲突

📎 参考文章

引用视频

(24) 哈希表和字典简介（数据结构和算法 #13）- YouTube

哈希表和哈希函数 (youtube.com)

引用文章

哈希表数据结构(programiz.com)

哈希表（HashTable）-CSDN博客

算法数据结构基础——哈希表（Hash Table）-CSDN博客