概念

HashTable(哈希表)是一种数据结构,它是一个无序的 key/value 对的集合,其中 key 不重复。大部分语言都有其实现,比如:Golang 中的 map,PHP 中的 array 等。

如果需要我们自己设计一个 HashTable,应该怎么做呢?

设计思路

粗暴解决

假设我们有足够的内存,也不在乎 HashTable 的查找效率。

我们使用无序数组做底层存储,原始 key 作为 key。查找复杂度为 O(n),慢是慢了点,不过解决了问题。

可现实要求我们 HashTable 要尽可能的快,最好是 O(1)。

Hash 函数

我们使用 hash 函数计算出 key 的 hashcode,对 hashcode取模定位到数组位置。

对于 hash 冲突,使用拉链法解决。

流程:

  1. 将 key 使用 hash 函数算出 hash 值,比如:hash(“H”) -> 84696407。
  2. hashcode % len(arr) hash 值和数组取模,获取hash在数组中的位置。
  3. 对于取模相同发送碰撞的 hash,使用拉链法即放入单链表中(k,v),从链表头开始依次对比 key 得到精确的 key。

图示:

将字符 {“H”, “A”, “S”, “H”, “T”, “A”, “B”, “L”, “E”} 进行 hash 存入长度为 4 的 HashTable 中。

HashTable

实现

目标:

  1. 可对字符串类型 key 进行 hash
  2. 根据 key 获取值,Get 方法
  3. 根据 key 设置值,Set 方法

这里俺使用 Golang 实现了简单 Demo。

完整代码见:https://github.com/mangoim/blog-code/tree/master/hashtable

Reference