Hash 算法


这个很简单,主要就是将 key 映射到一个定长的 hash地址,相同的key得到相同的 hash地址。

常见的 hash 算法有:

  • MD4, 输出为 16 字节,128 bit
  • MD5, 输出为 16 字节,128 bit
  • SHA-1, 输出为 20 字节,160 bit
  • SHA-256, 输出为 32 字节,256 bit

静态散列


hash 表


hash 表把 key 映射到一块连续内存的下标,然后把 value 数据存储在下标位置。从而实现查找时 O(1)的时间复杂度。

Hash表的容量

Hash 表中将一块连续内存分为 0 ~ n个 ,这个 n 则为hash表的容量。桶分为很多的槽,用来存储数据,通常情况下槽的数量为1.

Hash 表的负载因子则为: 存储的数据量 / hash表的容量

存储过程

设 HashTable 的容量为 n,则存储 <key, value> 的过程为:

通过hash函数 f(x) 计算 f(key) 到一个值,然后通过模运算获取存储在hash表中的下标:f(key) % n。然后将数据(包含key和value)存储到对应的位置。

当然,由于不同的 key 有可能计算得到的 f(key) 是相同的,因此需要做一定的冲突处理。

hash 表处理冲突的方法


处理冲突的方法大体上可以分为这三类。

开放定址法

开放定址法原理上是通过 (f(key) + i) % n 实现的,即当 f(key) % n 位置已经存在数据了,则通过添加一个 i 的偏移来从附近位置寻找空的桶并存储数据。

通过设置不同的 i 可以得到更多版本的开放定址法

  • (f(key) + s(i)) % n 随机探测法

s(i) 是一个随机函数,能随机的产生 0 ~ n 之间的数字。

再散列法

预先设定一系列散列函数(f1、f2、f3 ~ fn)。

若在 f1(key) 发生了冲突,则依次继续使用后续的散列函数找空桶。

链地址法

大部分实现都采用链地址法。

每个桶都有一个链表,若冲突了则 按照一定规则 把数据插入在链表的后面。

溢出空间法

将冲突的数据统一放在一个地方,后续查找时,若没法在 hash表中找到数据则统一在这个位置查找。

Hash表扩容


hash 表扩容类似于 C++ vector的扩容,会重新分配一块更大的连续内存(如:原来的两倍),然后通过 策略(比如一次完成转移,或多次完成转移) 将原 hash表中的数据转移到新表中。

转移过程中需要重新计算hash,计算在表中的下标位置。

标签: hash

添加新评论