Hash table 1 - wyc902/redis GitHub Wiki

Redis 作为一个kv存储，hash表应该是其中最重要的底层数据结构。看了源码实现以后，想起了自己以前实习面试的时候也被问到过hash-table的实现。当时的想法是，hash桶的个数是2的n次幂，hash函数就简单的取模运算，应为hash表长度是2的n次幂，所以直接&2的n次幂减一，就是存储位置，hash冲突了，就用链表解决。面试官对hash冲突的解决方法不满，问有没有改进的方法。我给出的方法是，如果冲突了，就在冲突的位置存储一个hash表的地址，指向一张新的表，新的表长度是第一个对冲突的两个key不同余的2的n次幂。当时因为面试时间有限，写了代码以后面试官也就没深问。后来想了下，这个解法处在很多不足。

1. 申请内存的次数会较多
2. 空间存在浪费。
3. clear操作会很麻烦

看了redis源码之后，才发现这才是hash表的优美实现。