哈希表的原理

1. 基本概念

哈希表是一种通过哈希函数将键（key）映射到表中一个位置来访问记录的数据结构。其核心思想是通过哈希函数快速定位数据的存储位置，从而实现高效的插入、删除和查找操作。

2. 哈希函数

哈希函数是哈希表的核心，它将输入的键（key）映射到一个较小范围的整数值（通常是数组的索引）。就是将一个数据转化成哈希数据. 一个好的哈希函数应该满足以下条件：

• 均匀性：哈希值应均匀分布在哈希表中，减少冲突。

• 快速计算：哈希函数应易于计算，以提高性能。

• 确定性：相同的输入键总是映射到相同的哈希值

数据通过哈希算法执行过后产生新的数据存储到哈希表当中, 但是如果数据量庞大, 那么不可避免就有可能两个数据经过这个哈希算法计算过后生成的数据是相同的,这个就是哈希冲突

哈希冲突解决办法

. 链地址法（Separate Chaining）

链地址法是最常用的解决哈希冲突的方法之一。每个哈希表的槽位存储一个链表，所有映射到该槽位的键值对都存储在链表中。(最常用)

实现

• 每个槽位是一个链表。

• 插入时，将键值对添加到对应槽位的链表中。

• 查找时，遍历链表查找键值对。

• 删除时，从链表中删除键值对。

2. 开放定址法（Open Addressing）

开放定址法通过寻找下一个空闲槽位来解决冲突。常见的开放定址法有以下几种：

2.1 线性探测（Linear Probing）

当发生冲突时，依次检查下一个槽位，直到找到空闲槽位。

实现

• hash(key, i) = (hash(key) + i) % table_size

优点

• 实现简单。

• 适合小规模数据。

缺点

• 容易产生聚集，导致性能下降。

• 删除操作复杂，需要标记删除位置。

2.2 二次探测（Quadratic Probing）

当发生冲突时，检查二次方的槽位，直到找到空闲槽位。

实现

• hash(key, i) = (hash(key) + c1 * i + c2 * i^2) % table_size

优点

• 减少了聚集现象。

缺点

• 实现复杂。

• 仍然可能存在聚集。

• 删除操作复杂。

2.3 双重哈希（Double Hashing）

当发生冲突时，使用第二个哈希函数计算步长，直到找到空闲槽位。

实现

• hash(key, i) = (hash1(key) + i * hash2(key)) % table_size

优点

• 减少了聚集现象。

• 性能较好。

缺点

• 实现复杂。

• 需要设计两个哈希函数。

• 删除操作复杂。

3. 再哈希法（Rehashing）

当哈希表的负载因子过高时，重新选择一个更大的哈希表，并重新计算所有键的哈希值，将所有键重新插入到新的哈希表中。说白了就是再拿一个哈希函数重新计算,直到不重复了为止

优点

• 可以有效解决冲突，提高性能。

• 适合动态数据集。

缺点

• 重新哈希操作代价较高，需要重新计算所有键的哈希值。

• 需要额外的存储空间。

4. 公共溢出区法（Coalesced Hashing）

结合了链地址法和开放定址法的优点。将哈希表分为两部分：主表和溢出区。主表用于存储键值对，溢出区用于存储冲突的键值对。说白了就是再申请一块空间存

实现

• 主表和溢出区分别存储键值对。

• 当主表发生冲突时，将冲突的键值对存储到溢出区。

• 溢出区的键值对通过链表连接。

优点

• 结合了链地址法和开放定址法的优点。

• 性能较好。

缺点

• 实现复杂。

• 需要额外的存储空间。