哈希表
哈希表
哈希表(Hash table)有时候也翻译成散列表,是根据关键码的值而直接进行访问的数据结构。
一般都表示为 key,value
这样的键值对,key 就是关键码,value 就是这个当我们输入这个关键码的时候希望拿到的值。
这么说可能有点抽象,咱们举个例子,数组就是一张哈希表。哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。
那么哈希表能解决什么问题呢,一般哈希表都是用来快速判断一个元素是否出现集合里。
例如要查询一个名字是否在这所学校里。
要枚举的话我们得一个学生一个学生的匹配,这个时候的时间复杂度是
但如果使用哈希表的话,我们只需要初始化把这所学校里学生的名字都存在哈希表里,key 就是学生名字,value 就是学生的信息,在查询的时候输入名字,如果可以查出来值,那就说明存在这个学生,如果没有查出来值,就说明学校不存在这个名字的学生,这样只需要
哈希函数
哈希函数的作用是将任意大小的数据(key)映射到固定大小的值(哈希值),理想情况下,哈希函数的结果应该是均匀分布的,以减少冲突。一般我们用数组来存储数据(也就是使用数组来作为哈希表的实际实现),哈希函数的结果作为数组的索引。
问题就在于哈希表(默认为数组)的大小通常是有限的。但是需要存储的 key 是无限的,如果多个 key 通过哈希函数的结果相同,表现到实际情况就是两个 key 映射到了数组的同一个索引,这就叫哈希冲突,常见的解决办法有:
- 链地址法(Chaining):每个数组元素指向一个链表,哈希值相同的元素存储在链表中。
- 开放地址法(Open Addressing):冲突时,通过探测方法(如线性探测、二次探测)寻找下一个空闲位置。
Java 的 HashMap 采用的是链地址法
线性探测法
线性探测法(Linear Probing)是哈希表中解决冲突的一种开放地址法(Open Addressing)策略。当插入一个新元素时,如果通过哈希函数计算出的位置已经被占用,线性探测法会顺序检查下一个位置,直到找到一个空闲的位置为止。
线性探测法的基本步骤:
- 计算哈希值:
- 使用哈希函数 h(k) 计算键 k 的哈希值,得到初始位置 i=h(k)。
- 检查位置 i:
- 如果位置 i 为空,则直接将元素插入该位置。
- 如果位置 i 已被占用,则进行线性探测。
- 线性探测:
- 从位置 i 开始,顺序检查下一个位置 i+1,i+2,…(通常对表大小取模,即
,其中 N 是表的大小,j 是探测次数),直到找到一个空闲位置。 - 将元素插入找到的空闲位置。
- 从位置 i 开始,顺序检查下一个位置 i+1,i+2,…(通常对表大小取模,即
查找操作:
- 计算哈希值:
- 使用哈希函数 h(k) 计算键 kk 的哈希值,得到初始位置 i=h(k)。
- 检查位置 i:
- 如果位置 i 的键与目标键 k 匹配,则返回对应的值。
- 如果位置 i 为空,则表示键 k 不存在于哈希表中。
- 如果位置 i 被占用且键不匹配,则进行线性探测。
- 线性探测:
- 从位置 i 开始,顺序检查下一个位置 i+1,i+2,…(同样对表大小取模),直到找到目标键或遇到空位置。
删除操作:
- 计算哈希值:
- 使用哈希函数 h(k) 计算键 k 的哈希值,得到初始位置 i=h(k)。
- *检查位置 ii:
- 如果位置 i 的键与目标键 k 匹配,则删除该元素。
- 如果位置 i 为空,则表示键 k 不存在于哈希表中。
- 如果位置 i 被占用且键不匹配,则进行线性探测。
- 线性探测:
- 从位置 i 开始,顺序检查下一个位置 i+1,i+2,…(同样对表大小取模),直到找到目标键或遇到空位置。
线性探测法的优缺点:
优点:
- 实现简单,易于理解和实现。
- 不需要额外的数据结构(如链表)来处理冲突。
缺点: - 聚集问题(Clustering):当多个元素发生冲突时,会形成连续的占用区域,导致探测路径变长,影响性能。
- 删除操作复杂:删除元素时需要特殊处理,否则会影响后续的查找操作。常见的做法是使用标记(如“已删除”标记)来标识删除的位置。
示例:
假设哈希表大小为 10,哈希函数为 h(k)=kmod 10。
- 插入键 15:
- h(15)=15 mod 10=5
- 位置 5 为空,插入 15。
- 插入键 25:
- h(25)=25 mod 10=5
- 位置 5 已被占用,进行线性探测,检查位置 6。
- 位置 6 为空,插入 25。
- 插入键 35:
- h(35)=35 mod 10=5
- 位置 5 已被占用,进行线性探测,检查位置 6。
- 位置 6 已被占用,继续检查位置 7。
- 位置 7 为空,插入 35。
- 查找键 25:
- h(25)=25 mod 10=5
- 位置 5 的键为 15,不匹配,进行线性探测,检查位置 6。
- 位置 6 的键为 25,匹配,返回对应的值。
- 删除键 25:
- h(25)=25 mod 10=5
- 位置 5 的键为 15,不匹配,进行线性探测,检查位置 6。
- 位置 6 的键为 25,匹配,删除该元素,并标记为“已删除”。
线性探测法是一种简单且常用的冲突解决策略,但在高负载情况下可能会导致性能下降,因此在实际应用中需要根据具体情况选择合适的哈希函数和表大小。
关于 Hash
总的来说,哈希表是一种十分高效的和好用的数据结构,