数据结构中的哈希表

发表于 2022-08-18 更新于 2022-11-14 分类于 IT ，学习，数据结构阅读次数：评论：本文字数： 927 阅读时长 ≈ 3 分钟

哈希表(Hash Table)也叫散列表，在本文中，哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)。因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表，例如拼音检查器。

哈希表也有自己的缺点，哈希表是基于数组的，我们知道数组创建后扩容成本比较高，所以当哈希表被填满时，性能下降的比较严重。

哈希函数

而哈希表的关键，就是哈希函数。根据这个函数，查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就“预先知道”key所在的位置，直接找到数据，提升效率。

即值地址=H（key）

我们所给的任何符合要求的关键字，代入进哈希函数中，即可得出它所对应的更详细的值或地址。

哈希函数应该满足的三个基本条件：

第一点：因为数组的下标是从0开始，所以哈希函数生成的哈希值也应该是非负数

第二点：同一个key生成的哈希值应该是一样的，因为我们需要通过key查找哈希表中的数据

第三点：看起来非常合理，但是两个不一样的值通过哈希函数之后可能会产生相同的值，因为我们把巨大的空间转出成较小的数组空间时，不能保证每个数字都映射到数组空白处。所以这里就会才生冲突，在哈希表中我们称之为哈希冲突。

对于两个数据元素的关键字 k 和 j ，有k != j，但 Hash(k) == Hash(j)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希冲突不一定出现，但也不可避免的，所以要有解决哈希冲突的方法。解决哈希冲突的方法有：

开放地址法
- 线性探测数据的插入是线性的查找空白单元，直到找到空白地方存放元素
- 再哈希法如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个双哈希的特殊要求：表的容量必须是一个质数
链表法（主用）