hashtable内部实现的细节

?

Redis中hashtable内部实现的细节

?

?针对上图，对于四个知识点进行讲解，本文参考了其他博客的文章，有的知识点需要看详细的博客，我会列出博客的链接。上面四个知识点应该涵盖redis涉及到的所有细节，如何还有，请大家多多提出，一起探讨。。。

博客链接：http://www.hoterran.info/redis_dict

?

一、hashtable的内存结构

?

总结就是：两个数组链表的数据结构，请看网友画的图：

?

问题提出：

1、dict 包含了2个dictht hashtable ht[0], ht[1]，为什么要包含两个hashtable？

?

这是做的目的扩容即rehash所带来的性能问题，采取了平稳的扩容机制，而不像java中的hashmap扩容是一次性的rehash，这样带来了很大的性能问题

?

2、为什么第二个hashtable是第一个hashtable的两倍呢？

?

3、为什么要rehash？

?

随着key不断的添加，bucket下的单链表越来越长，查找、删除效率越来越低，需要对ht进行expand，增加bucket个数，让链表的长度减少。bucket数量的增多，原有bucket的key需要迁移到新的bucket上，于是有了rehash的这个过程

?

4、什么时候rehash？

?

对于数据是如何添加、修改、删除、查找请看第四部分

?

二、zipmap

?

问题：

?

1、为什么使用zipmap？

?

保证在hashtable刚创建以及元素较少时，用更少的内存来存储，同时对查询的效率也不会受太大的影响，

而当hashtable元素不超过254个元素就使用，zipmap存储否则就转向hashtable存储。

?

先来看一下zipmap提供的和存储相关的3个API：

zipmapNew：创建一个zipmap字符串。zipmap创建时只有2个字节，后面会随着set和delete操作动态扩展和收缩。zipmapSet： 加入新的key/value或者修改zipmap中已有key对应的value。zipmapDel：从zipmap中删除key/value。

下面给出一段伪代码并分析其内存布局的变化，如下图：

zipmapNew();zipmapSet(key1,value1);zipmapSet(key2,value2);zipmapSet(key1,value3);zipmapDel(key2);zipmapSet(key1,value4);

?

?