散列表

散列表

散列表（Hash table）是一种基于哈希函数（Hash function）实现的数据结构，它将键（key）通过 Hash 计算后映射到值（value）上，以常量时间内（平均情况下）进行插入、查找和删除操作。

• Word如何判断某个单词是否拼写正确？

散列表的问题

• Hash函数的选择：哈希函数的设计要考虑到键的特点，以及散列表的大小等因素。如果哈希函数不好，可能会导致散列冲突的增加，进而影响散列表的性能。
• 散列冲突（Hash collision）：由于散列表的大小有限，即使使用一个非常好的哈希函数，也无法为每个可能的键都分配一个唯一的存储桶。比如：有一个大小为10的散列表，用来存储0到99之间的整数。散列冲突不可避免。
• 散列表的空间占用：由于散列表需要预留一定的空间用于解决散列冲突，因此当散列表中元素较少时，空间占用会比较浪费。

如何选择 Hash

选择合适的 Hash 需要考虑的点：

• 散列速度（Hashing speed）：哈希函数需要尽可能快地计算出哈希值，以便在散列表中快速地进行查找和插入操作。
• 均匀性（Uniformity）：哈希函数需要尽可能将输入值的所有位都纳入计算，以产生尽可能随机的哈希值，从而使哈希值在哈希表中分布均匀，减少冲突的可能性。
• 冲突率（Collision Resistance）：哈希函数需要避免输入值的哈希值冲突，即不同的输入值产生相同的哈希值。因为哈希表中存储的键值对是以哈希值为索引的，如果哈希值冲突，则会导致键值对的丢失或者覆盖。
• 实现难度（Implementation complexity）：哈希函数的实现需要足够简单，便于实现和调试。
• 存储空间（Storage requirements）：哈希函数产生的哈希值需要足够短小，以便于存储在散列表的索引中，减少空间的浪费。
• 安全性（Security）：在涉及敏感数据、加密、数字签名等安全领域的应用

如果只是散列表的实现主要考虑 散列速度，均匀性，冲突率。

常见的哈希算法

安全哈希算法：

• SHA-3 (Keccak)
• BLAKE2
• SHA-2 (包括SHA-256、SHA-384和SHA-512)
• Whirlpool
• RIPEMD-160
• MD5：已经不安全

非安全哈希算法：

1. MurmurHash：是一种快速的非加密哈希函数，被广泛应用于哈希表、分布式系统等场景。MurmurHash 分为 MurmurHash1、MurmurHash2、MurmurHash3 等不同版本，其中 MurmurHash2 是应用最广泛的版本。
2. SipHash：是一种针对哈希碰撞攻击的哈希函数，主要应用于密码哈希等场景。SipHash 基于 ChaCha 加密算法实现，具有较高的安全性和快速的计算速度。
3. CityHash：是 Google 开发的一种哈希函数，主要应用于内存、磁盘等场景。CityHash 具有较好的哈希性能和抗碰撞能力。
4. Jenkins Hash：是一种简单快速的哈希函数，主要应用于低延迟、高并发的场景。Jenkins Hash 的计算速度非常快，但哈希值的随机性相对较弱。
5. FNV Hash：是一种基于乘法和异或的哈希函数，主要应用于高速缓存、路由表等场景。FNV Hash 的计算速度快，但哈希值的随机性相对较弱。

散列冲突的解决方式

链表法（Separate chaining）

链表是一种处理散列表哈希冲突的常用方法，即将冲突的元素放在同一个链表中。然而，当冲突元素过多时，这个链表可能会变得非常长，导致访问效率下降。为了解决这个问题，可以将链表转换为红黑树。这样，原来时间复杂度为$O(n)$的链表操作就变成了$O(log_2{n})$的红黑树操作。

开放寻址法（Open addressing）

开放寻址法（Open addressing）是一种解决散列冲突的方法。当发生冲突时，它会在散列表中寻找下一个空闲位置来存储键值对。常用的开放寻址法有线性探测、二次探测和双重散列。

线性探测（Linear Probing）

当发生冲突时，线性探测会顺序检查散列表中的下一个位置，直到找到一个空闲位置为止。例如，如果哈希函数将键映射到索引i上，但该位置已经被占用，则线性探测会检查索引i+1、i+2、i+3等位置，直到找到一个空闲位置为止。

二次探测（Quadratic probing）

与线性探测类似，二次探测也是在发生冲突时顺序检查散列表中的下一个位置。但不同的是，它会按照二次方的增长速度来检查索引。例如，如果哈希函数将键映射到索引i上，但该位置已经被占用，则二次探测会检查索引i+1²、i+2²、i+3²等位置。

双重散列（Double hashing）

双重散列使用两个哈希函数来计算键的存储位置。当发生冲突时，它会使用第二个哈希函数来计算下一个存储位置。例如，如果第一个哈希函数将键映射到索引i上，但该位置已经被占用，则双重散列会使用第二个哈希函数计算出下一个存储位置。

如何选择冲突解决方法

• 当数据量较小、负载因子小的时候，适合采用开放寻址法。

• 基于链表的散列冲突处理方法则更适合存储大对象、大数据量的散列表，因为它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

负载因子（Load factor）

无论使用哪种探测方法，当散列表中的空闲位置变少时，散列冲突的概率都会显著增加。为了最大限度地保证散列表操作的效率，我们通常会尽量保持散列表中有一定比例的空闲槽位。我们用“装载因子”（load factor）来衡量空位的数量。

1

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

负载因子过大会动态扩容

通过分批完成扩容操作的方式来解决一次性扩容耗时过多的问题。

在插入数据时，当装载因子触达阈值后，我们只申请新空间，并将新数据插入新散列表中，同时从老的散列表中拿出一个数据放入新散列表。

每次插入一个数据，都重复上述过程，直到老的散列表中的数据全部搬移到新散列表中。这样，没有了一次性数据搬移，插入操作就变得很快了，时间复杂度为 O(1)。

对于查询操作，先从新散列表中查找，如果没有找到，再去老的散列表中查找，以兼容新老散列表中的数据。

通过这种均摊的方法，将一次性扩容的代价，均摊到多次插入操作中，解决了一次性扩容耗时过多的问题。

使用场景

• 程序语言

  • Go语言中的 map 就是散列表的一种实现，它使用了哈希算法来实现键值对的快速查找和插入。
  • Python语言中的 dict 也是散列表的一种实现，同样使用哈希算法来实现键值对的快速操作。
  • C++语言中的 unordered_map 和 unordered_set 也是散列表的一种实现，同样使用哈希算法来实现元素的快速查找和插入。
  • Java语言中的 HashMap 和 HashSet 也是散列表的一种实现，同样使用哈希算法来实现键值对或元素的快速操作。

• 数据库索引：散列表可以用于加速数据库的查询操作，通过将索引键映射到哈希表中的位置，快速查找对应的数据。

• 缓存：Redis 的 sorted sets。

• 路由表：散列表可以用于实现路由表，通过将路由地址映射到哈希表中的位置，快速查找对应的路由路径。

• 加密算法：散列表可以用于实现加密算法，通过将明文映射到哈希表中的位置，并对哈希结果进行加密，从而实现数据的安全存储和传输。

Java 8系列之重新认识HashMap

Go源码学习之map