哈希表

哈希表

哈希表(Hash table)有时候也翻译成散列表,是根据关键码的值而直接进行访问的数据结构
一般都表示为 key,value 这样的键值对,key 就是关键码,value 就是这个当我们输入这个关键码的时候希望拿到的值。
这么说可能有点抽象,咱们举个例子,数组就是一张哈希表。哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。
那么哈希表能解决什么问题呢,一般哈希表都是用来快速判断一个元素是否出现集合里。
例如要查询一个名字是否在这所学校里。
要枚举的话我们得一个学生一个学生的匹配,这个时候的时间复杂度是 O(n)
但如果使用哈希表的话,我们只需要初始化把这所学校里学生的名字都存在哈希表里,key 就是学生名字,value 就是学生的信息,在查询的时候输入名字,如果可以查出来值,那就说明存在这个学生,如果没有查出来值,就说明学校不存在这个名字的学生,这样只需要 O(1) 就可以做到。

哈希函数

哈希函数的作用是将任意大小的数据(key)映射到固定大小的值(哈希值),理想情况下,哈希函数的结果应该是均匀分布的,以减少冲突。一般我们用数组来存储数据(也就是使用数组来作为哈希表的实际实现),哈希函数的结果作为数组的索引。
问题就在于哈希表(默认为数组)的大小通常是有限的。但是需要存储的 key 是无限的,如果多个 key 通过哈希函数的结果相同,表现到实际情况就是两个 key 映射到了数组的同一个索引,这就叫哈希冲突,常见的解决办法有:

线性探测法

线性探测法(Linear Probing)是哈希表中解决冲突的一种开放地址法(Open Addressing)策略。当插入一个新元素时,如果通过哈希函数计算出的位置已经被占用,线性探测法会顺序检查下一个位置,直到找到一个空闲的位置为止。
线性探测法的基本步骤:

  1. 计算哈希值
    • 使用哈希函数 h(k) 计算键 k 的哈希值,得到初始位置 i=h(k)。
  2. 检查位置 i
    • 如果位置 i 为空,则直接将元素插入该位置。
    • 如果位置 i 已被占用,则进行线性探测。
  3. 线性探测
    • 从位置 i 开始,顺序检查下一个位置 i+1,i+2,…(通常对表大小取模,即 (i+j)modN,其中 N 是表的大小,j 是探测次数),直到找到一个空闲位置。
    • 将元素插入找到的空闲位置。

查找操作:

  1. 计算哈希值
    • 使用哈希函数 h(k) 计算键 kk 的哈希值,得到初始位置 i=h(k)。
  2. 检查位置 i
    • 如果位置 i 的键与目标键 k 匹配,则返回对应的值。
    • 如果位置 i 为空,则表示键 k 不存在于哈希表中。
    • 如果位置 i 被占用且键不匹配,则进行线性探测。
  3. 线性探测
    • 从位置 i 开始,顺序检查下一个位置 i+1,i+2,…(同样对表大小取模),直到找到目标键或遇到空位置。

删除操作:

  1. 计算哈希值
    • 使用哈希函数 h(k) 计算键 k 的哈希值,得到初始位置 i=h(k)。
  2. *检查位置 ii
    • 如果位置 i 的键与目标键 k 匹配,则删除该元素。
    • 如果位置 i 为空,则表示键 k 不存在于哈希表中。
    • 如果位置 i 被占用且键不匹配,则进行线性探测。
  3. 线性探测
    • 从位置 i 开始,顺序检查下一个位置 i+1,i+2,…(同样对表大小取模),直到找到目标键或遇到空位置。

线性探测法的优缺点:

优点

示例:

假设哈希表大小为 10,哈希函数为 h(k)=kmod  10。

  1. 插入键 15:
    • h(15)=15 mod  10=5
    • 位置 5 为空,插入 15。
  2. 插入键 25:
    • h(25)=25 mod  10=5
    • 位置 5 已被占用,进行线性探测,检查位置 6。
    • 位置 6 为空,插入 25。
  3. 插入键 35:
    • h(35)=35 mod  10=5
    • 位置 5 已被占用,进行线性探测,检查位置 6。
    • 位置 6 已被占用,继续检查位置 7。
    • 位置 7 为空,插入 35。
  4. 查找键 25:
    • h(25)=25 mod  10=5
    • 位置 5 的键为 15,不匹配,进行线性探测,检查位置 6。
    • 位置 6 的键为 25,匹配,返回对应的值。
  5. 删除键 25:
    • h(25)=25 mod  10=5
    • 位置 5 的键为 15,不匹配,进行线性探测,检查位置 6。
    • 位置 6 的键为 25,匹配,删除该元素,并标记为“已删除”。
      线性探测法是一种简单且常用的冲突解决策略,但在高负载情况下可能会导致性能下降,因此在实际应用中需要根据具体情况选择合适的哈希函数和表大小。

关于 Hash

总的来说,哈希表是一种十分高效的和好用的数据结构,