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。

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

1. zipmapNew();
2. zipmapSet(key1,value1);
3. zipmapSet(key2,value2);
4. zipmapSet(key1,value3);
5. zipmapDel(key2);
6. zipmapSet(key1,value4);