哈希表

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

哈希函数

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

• 链地址法（Chaining）：每个数组元素指向一个链表，哈希值相同的元素存储在链表中。
• 开放地址法（Open Addressing）：冲突时，通过探测方法（如线性探测、二次探测）寻找下一个空闲位置。
  Java 的 HashMap 采用的是链地址法

线性探测法

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

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

查找操作：

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

删除操作：

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

线性探测法的优缺点：

优点：

• 实现简单，易于理解和实现。
• 不需要额外的数据结构（如链表）来处理冲突。
  缺点：
• 聚集问题（Clustering）：当多个元素发生冲突时，会形成连续的占用区域，导致探测路径变长，影响性能。
• 删除操作复杂：删除元素时需要特殊处理，否则会影响后续的查找操作。常见的做法是使用标记（如“已删除”标记）来标识删除的位置。

示例：

假设哈希表大小为 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

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