02.全局哈希表

使用全局哈希表存储所有键值对

• 哈希表的优点：
  • 用 O(1) 的时间复杂度来快速查找到键值对
  • 只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素

如何解决冲突问题（链表法、开放地址法、再哈希）

• redis使用链表法：

• 防止单个hash桶元素过多，当哈希冲突链过长时（负载因子），还使用了渐进式rehash

• redis默认有两个全局hash表：dictht[0]、dictht[1]

• 哈希表扩容：

  1. 给哈希表2 dictht[1] 分配更大的空间，例如是当前哈希表1 dictht[0]大小的两倍；
  2. 把哈希表1 dictht[0] 中的数据重新映射并拷贝到哈希表2 dictht[1] 中，此过程是渐进式的；
     • 具体操作：每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries）
  3. 释放哈希表 1 的空间