数据结构之哈希表hashtable

在计算机中，哈希表(哈希映射)是一种实现关联数组抽象数据类型的数据结构，这种结构可以将键映射到值。哈希表使用哈希函数来计算一个索引(也称为哈希代码)到一个bucket或slot数组中，从中可以找到所需的值。在查找过程中，对键进行散列，结果散列指示对应值存储的位置。

理想情况下，哈希函数将把每个键分配给一个惟一的bucket，但是大多数哈希表设计采用了不完美的哈希函数，当哈希函数为多个键生成相同的索引时，可能会导致哈希冲突。这种冲突总是以某种方式加以适应的。

在维度良好的哈希表中，每次查找的平均成本(指令数)与表中存储的元素数无关。许多哈希表设计还允许键值对的任意插入和删除，每个操作的平均开销为常数。

在许多情况下，哈希表的平均效率比搜索树或任何其他表查找结构都要高。因此，它们被广泛应用于各种计算机软件中，特别是用于关联数组、数据库索引、缓存和集合。

哈希

哈希的思想是将条目(键/值对)分布在一个bucket数组中。给定一个键，该算法计算一个索引，该索引显示条目的位置:

index = f(key, array_size)

通常可以分两步来完成:

hash = hashfunc(key)
index = hash % array_size

关键数据

哈希表的一个关键数据是负载因子，定义为

其中：

• k是可以插入的数据总量
• n是已经插入的数据数量

随着负载系数的增大，哈希表变得更慢，甚至可能无法工作(取决于使用的方法)。哈希表的期望常数时间属性假设负载因子保持在某个界限以下。对于固定数量的桶，查找时间会随着条目数量的增加而增加，因此无法实现所需的常量时间。在某些实现中，解决方案是在达到负载因子界限时自动增加表的大小(通常是两倍)，从而强制重新散列所有条目。作为一个真实的示例，Java 10中的HashMap的默认加载因子是0.75，这“在时间和空间成本之间提供了很好的平衡”

低负载系数并不是特别有利。当负载因子接近0时，哈希表中未使用区域的比例会增加，但搜索成本不一定会降低。这会导致内存浪费。

哈希冲突

当对一大堆可能键的随机子集进行哈希时，哈希冲突实际上是不可避免的。例如，如果2450个键被散列到100万个存储中，即使是完全均匀的随机分布，根据birthday问题，大约有95%的几率至少有两个键被散列到同一个槽中。

解决哈希冲突的方法一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法。

链地址法

在称为独立链接的方法中，每个bucket是独立的，并且具有某种具有相同索引的条目列表。哈希表操作的时间是找到bucket的时间(是常数)加上列表操作的时间。

在一个好的哈希表中，每个bucket有0个或1个条目，有时有2个或3个，但很少超过这个数。因此，对于这些情况，在时间和空间上有效的结构是首选的。对于每个bucket中相当多的条目有效的结构是不需要或不希望的。如果这些情况经常发生，哈希函数需要修复。

开放定址法

在另一种策略中，称为开放寻址，所有的条目记录都存储在bucket数组中。当必须插入一个新条目时，将检查bucket，从hashad -to槽开始，以某种探查序列进行，直到找到一个未占用的槽。当搜索一个条目时，将按照相同的顺序扫描bucket，直到找到目标记录，或者找到一个未使用的数组槽，这表明表中没有这样的键。名称“开放寻址”指的是项目的位置(“地址”)不是由它的散列值决定的。(这种方法也称为闭哈希;它不应该与通常表示单独链接的“开放哈希”或“封闭寻址”相混淆。)