hashmap 是如何炼成的

hashmap 是程序员日常使用频率比较高的数据结构之一，是一种 key-value 结构，它最大的特点是查找的时间复杂度为 O(1)。那么它的底层原理是如何实现的呢？今天我们通过这篇文章来了解下





hash 映射



hash 映射就是通过 hash 函数确定 key 与 index 的映射关系。一般采用取模法，同时取模法最好理解，如下



index = key % len(buckets)



hash 冲突



通过 hash 映射函数，我们确定了 key 与 index 的映射关系，然后这就会带来 hash 冲突的问题，所谓的 hash 冲突即是指多个 key 通过 hash 计算后得到相同的 index，那么此时就需要有策略去应对这种情况。常见的 hash 冲突解决方法有



• 链地址法

• 开放地址法



链地址法比较好理解，当发生冲突时，使用链表来进行存储，直接看图





当然单纯使用链表是有问题的，如果冲突太多那么就可能导致链表过长，遍历起来就比较耗时，时间复杂度为 O(n)。一般的改进方法为如果链表长度达到某个阈值后就改为用红黑树。这其实也是 JDK 1.8 HashMap 的实现方式





开放地址法，如果 key 通过 hash 计算后发现冲突，那么就向后寻找下一个空的 bucket，如下





如果向下查找的步长为 1 的话，那遍历时间就太长了，一般情况下我们会增大步长，同时对 buckets 的大小也是有要求的，必须为质数。假设 buckets 长度为 11，步长为 5，那么遍历结果为



0, 5, 10, 4, 9, 3, 8, 2, 7, 1, 6, 0, 5, 10, ...



稍微比较下两者，开放地址法容易产生堆积问题，既是大量元素通过 hash 计算后堆积在 buckets 的某一处。同时插入元素时容易产生多次冲突，可以说开放地址法比较适合小数据量的场景，所以我们可以看到大多数编程语言的 hashmap 实现使用的是链地址法



初始容量与扩容



像初始容量应该默认设置多少合适，扩容负载因子 (load factor=size/capacity) 应该设置多少合适等等这些其实都没标准答案，我们只能见仁见智。这里我们以 Java 为例



• 初始容量默认为 16

• 扩容的负载因子为 0.75，扩容比为 2，设置合理的话，可以有效的降低冲突比例

• 缩容，有扩容自然就有缩容，但是一般不会进行缩容的，很大原因是为了避免频繁进行扩容与缩容



rehash



当 hashmap 的容量达到负载因子时，也就意味着需要进行扩容，那么就需要对现有的 key 重新计算一次 hash 值，这一过程称为 rehashing。一般情况下 rehash 是没有问题的，但是如果是在并发场景下，可能会出现多个线程同时进行 rehash，导致 Infinite Loop。这也就需要我们去考虑如何保证 hashmap 并发安全



并发安全



要想 hashmap 并发安全，最简单的方法是加一把锁 (可以是互斥锁，也可以是读写锁)，操作前加锁，操作后释放锁。这里以 go 来举例



type Map struct {
    sync.Mutex
    data map[string]interface{}
}
func (m *Map) Set(key string, value interface{}) {
    m.Lock()
    m.data[key] = value
    m.Unlock()
}
func (m *Map) Get(key string) (value interface{}) {
    m.Lock()
    value = m.data[key]
    m.Unlock()
    return
}



不过这种直接对 hashmap 加锁，锁的粒度太大了，必然不是最优解。所以我们需要考虑如何去降低锁的粒度，比如我们可以采用分段加锁的方法来降低锁的粒度





可以看到需要进行两轮 hash 计算，第一轮是找到对应的 segment，第二轮是找到对应的 bucket 进行存储，这其实就是 JDK 1.7 ConcurrentHashMap 的实现方式。通过这种方式确实降低锁的粒度，但是由于进行了两轮 hash 计算，必然是会降低性能的，所以除非是并发场景，不然不推荐使用这种 hashmap