数据结构之哈希表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,直到找到目标记录,或者找到一个未使用的数组槽,这表明表中没有这样的键。名称“开放寻址”指的是项目的位置(“地址”)不是由它的散列值决定的。(这种方法也称为闭哈希;它不应该与通常表示单独链接的“开放哈希”或“封闭寻址”相混淆。)

每日科技资讯 | 20200803
如何解决NGINX超时– Http 499个客户端关闭请求