Golang 实现简单 HashTable

概念

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 中。

实现

目标：

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

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

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

Reference

• HashTable 的实现 (Golang/Redis)