【Java】字典是如何实现的？Rehash 了解吗？（约272字）

字典是如何实现的？Rehash 了解吗？

字典是 Redis 服务器中出现最为频繁的复合型数据结构。除了 hash 结构的数据会用到字典外，整个 Redis 数据库的所有 key 和 value 也组成了一个 全局字典，还有带过期时间的 key 也是一个字典。(存储在 RedisDb 数据结构中)

字典结构是什么样的呢？

Redis 中的字典相当于 Java 中的 HashMap，内部实现也差不多类似，采用哈希与运算计算下标位置；通过 "数组 + 链表" 的链地址法 来解决哈希冲突，同时这样的结构也吸收了两种不同数据结构的优点。

字典是怎么扩容的？

字典结构内部包含 两个 hashtable，通常情况下只有一个哈希表 ht[0] 有值，在扩容的时候，把 ht[0]里的值 rehash 到 ht[1]，然后进行 渐进式 rehash ——所谓渐进式 rehash，指的是这个 rehash 的动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

待搬迁结束后，h[1]就取代 h[0]存储字典的元素。