Valkey（Redis 的一个分支）分享了一种构建哈希表的现代方法，侧重于性能和内存优化。这是一篇快速阅读的文章，展示了重新设计的设计如何提高效率并减少日常使用中的冲突。
很多程序的运行速度都被数据存储拖慢了。如果能用更少的内存存更多数据，你就能缩小服务器集群的规模。
在Valkey中，键值对都存放在叫"哈希表"的结构里。哈希表的工作原理是：把键打散成一串看似随机的比特位，这些比特位会转换成内存地址，直接指向数值存放的位置。这种方法不用挨个扫描所有键，就能闪电般跳转到正确内存位置。
在8.1版本开发时，我们重点研究了如何提升性能、节省内存，让用户能用更少内存存更多数据。这项工作催生了全新哈希表的设计，不过先来看看Valkey目前使用的旧版哈希表。
【旧哈希表dict】
目前Valkey使用的哈希表叫"dict"，内存结构如下：
这个dict包含两个表格（table 0和table 1）。通常只用其中一个，但在渐进式重哈希过程中会同时使用两个。
它采用链式结构——当多个键被哈希到同一个槽位时，这些键值条目会形成链表。这就是dictEntry里"next"指针的作用。
比如查找键"FOO"获取值"BAR"时，Valkey仍需进行四次内存读取。若发生哈希冲突，每多一次冲突就要多追踪两个指针，意味着再多两次内存读取（读取键和next指针）。
【减少内存访问】
查找键值对时最耗时的操作之一就是读取主内存。关键要确保尽可能减少内存访问次数。理想情况下，要访问的内存最好已加载在CPU缓存里——这是CPU自带的小容量超高速内存。
为优化内存使用，我们还要尽量减少内存分配次数和指针数量。因为在64位系统中，每个指针要占8字节。如果能给每个键值对省下一个指针，那么1亿个键就能省下近1GB内存。
CPU从主内存加载数据到缓存时，会按固定大小的块（称为缓存行）读取。现代硬件缓存行大小基本都是64字节。Swiss tables等新型哈希表就专门优化了单缓存行内的数据存储与访问。如果因哈希冲突第一次没找到目标键，理想情况下应该能在同一缓存行内找到。一旦缓存行加载到CPU缓存，二次查找就会极快。
【必要特性】
为什么不直接用Swiss tables这类开源尖端哈希表？因为除了基础的增删改查，我们还需要这些特殊功能：
- 渐进式重哈希：哈希表满了也不暂停服务，边扩容边迁移
- 扫描遍历：即便哈希表在遍历过程中扩容，也能继续迭代（支持SCAN命令的关键）
- 随机抽样：实现RANDOMKEY等命令
【新版设计】
Valkey 8.1的新哈希表中，每个桶(bucket)正好是64字节（一个缓存行），最多存7个元素。映射到同桶的键都存放在同个桶内。桶还包含标记为"m"的元数据区（下文详解）。
我们取消了dictEntry，直接把键值嵌入serverObject（键的其他数据也存放在此）。
假设哈希表结构已在CPU缓存中，现在查找键值只需两次内存访问：访问桶和serverObject。即使发生哈希冲突，目标对象大概率也在同个桶内，无需额外内存访问。
当桶存满时，最后一个元素槽位会替换成指向子桶的指针。子桶结构与常规桶相同，但属于独立内存分配。只要哈希函数分布均匀，长链桶极为罕见，多数键都存在顶层桶。
同桶或同桶链中的元素无需排序。插入新条目时，任意空闲槽位都可使用。
如前所述，每个桶包含8字节元数据：1个比特标记是否存在子桶，7个比特分别标记7个槽位是否占用，剩余7字节存储每个元素的8位次级哈希值。
次级哈希由查找桶时未使用的哈希位组成。64位哈希中最多用56位定位桶，剩下8位作次级哈希。这样在查找时能快速排除不匹配的键，无需逐个比对键值（否则每个条目都要多一次内存访问）。次级哈希不匹配可直接跳过，误判率仅1/256，能过滤99.6%的错误匹配。
【成果】通过更换哈希表实现，每个键值对平均节省约20字节内存。
某些场景下（如存储极小对象或大量使用管道时），延迟和CPU占用也有改善。不过多数场景下改善不明显，核心优势还是内存节省。
【集合类型】
当哈希(Hash)、集合(Set)和有序集合(Sorted Set)元素较多时，它们内部也会使用新哈希表。这些类型的每个元素可节省10-20字节内存。