Map (映射) 实现

Map 的数据结构

『Map 是一种抽象的数据结构，它包含着类似于（键，值）的有序对。』这是维基百科上的解释。

具体实现一般用 HashTable 或者 Search Tree。很多编程语言或者存储软件都内置了 map 这个基本数据类型。

Hash Table 原理

哈希表提供了 O(1) 的读写性能和键值之间的映射关系。但实现一个哈希表还需要解决两个关键问题：哈希函数和冲突解决。

哈希函数

实现哈希表的关键点在于哈希函数的选择，哈希函数很大程度上决定哈希表的读写性能。在理想情况下，通过分布均匀哈希函数对一个键的访问，能够在 O(1) 的时间内被定位。Go 语言里如果 CPU 支持 aes 算法就用 aes 否则用 memhash 。Redis 里哈希函数用的 DJB 。Java 对象内置了 hashCode 方法。

冲突解决

开放地址法（open addressing）

其中，hash(key) 为哈希函数， m 为 哈希表长，$d_i$ 为增量序列，i 为已发生冲突的次数。增量序列有下列取法：

$d_i=1,2,3...(m-1)$ 称为线性探测（Linear Probing）；即 $d_i=i$, 或者为其他线性函数。相当于逐个探测，直到找到索引不为空的单元，将地址放入。

$d_i=\pm 1^2,\pm 2^2,\pm 3^2...\pm 1^k(k\le m/2)$称为平方探测（Quadratic Probing）。

$d_i=i\ast has{h}_2(key)$, 此时 $has{h}_i=\frac{has{h}_1(key)+i\ast has{h}_2(key)}{m}$, 称为双重哈希（Double hashing）；

拉链法

拉链法常见的实现是用双向链表数组。相同 index 的 key 会存在这个 index 对应的双向链表中。

写入和读取一般都要通过计算哈希 h = hash(key)、定位桶 index = h/m、遍历链表三个步骤。

装载因子

load fator = $\frac{n}{k}$, n 哈希表实际元素个数，k 桶的数量。

无论开发地址法还是拉链法，装载因子越大，哈希的读写性能越差。一般拉链放装载因子不会超过 1。

动态扩容

当负载因子超过哈希表设定阀值时，一般就会出发哈希表动态扩容，这个过程常叫做 rehashing。

触发 rehash 的过程在实现时会有多个因素。Rehashing 一般包含两个步骤：增加哈希表的大小，重新映射现有的元素到新的桶里。

为了避免内存浪费，工程实践上 rehash 并不一定会申请更大的内存空间。但发生频繁删除大部分元素时，大部分实现里哈希表 buckets 数量不会自动缩容，这部分内存占用通常相比 key、value 的占用要少的多。

在哈希表扩容完以后，就会进行元素的迁移。这个一般都会选择渐进式 rehash。

Go map 实现

Redis hashDict 实现

Java hashTable 实现

Search Tree 实现