腾讯面试官：说说Redis的Hashtable是怎么扩容的？面试官：什么？呃...，（一头雾水！）这个我也还没看懂，尴尬...不过我理解了java中HashMap的扩展。我觉得里面应该有一些类似的原理。然后讲了HashMap的扩展机制balabla...Redis使用哈希表作为底层实现，是一种数据结构，叫做字典，也叫符号表，关联数组，映射。它是一种包含键值对的抽象数据结构。如果你对JavaHashMap有所了解，那么Redis哈希表类似于Java中的HashMap。由于Redis是用C语言编写的，如果想了解C的相关实现原理和查看源码，就必须对C语言有一定的了解。目录1.哈希表结构哈希表实例2.字典数据结构字典实例3.解决哈希冲突4.扩容/缩容——rehash4.1。字典哈希表的重新哈希步骤4.2。看hashonceTablerehash展开过程5、progressiverehash5.1、progressiverehashstep5.2、看下完整的progressiverehash展开过程6、总结01hashtable结构hashtable是由dictht结构定义的，table是一个Array，数组中的每个元素都是指向dictEntry结构的指针。dictEntry是哈希表的一个节点，每个节点保存一个键值对key，value，value可以是指针，也可以是unit64_t或int64_t整数。next属性是指向另一个哈希表节点的指针，组成一个链表，主要是为了解决哈希冲突问题。哈希表示例具有相同索引值的空哈希表使用链表连接。02字典数据结构其实说到哈希表，顺便要了解一下字典的数据结构。毕竟它的底层是哈希表。要实现，您可以了解扩展和收缩。type：指向dictType的指针，它存储了用于操作特定类型的键值对的函数。Redis为不同用途的字典设置了不同类型特定的函数。privdata：保存需要传递给不同具体函数的可选参数。ht[2]：两个哈希表，字典使用的哈希表是ht[0]，ht[1]在rehashht[0]哈希表时使用。trehashidx：记录当前的rehash进度，如果没有进行rehash则为-1。字典示例Dictionary03正常状态解决哈希冲突向字典中添加一个键值对时，需要计算它的哈希值和索引值，然后根据指数值。计算哈希值：hash=dict->type->hashFunction(key)计算索引值：hash&dict->ht[x].sizemask键冲突：当两个或多个键被哈希时，索引值相同，也也就是说，如果两个节点放在同一个桶中，此时可能存在覆盖（冲突），所以必须解决这个冲突。Redis解决键冲突的方法：分离链-拉链法，假设你已经了解了JavaHashMap的原理，链地址法的原理这里不再赘述。插一句题外话（也是笔者遇到过的一道面试题）：hash冲突的解决方法是什么？答：①重新散列法；②链地址法；③打开地址法；④建立公共溢流区。（每个方法自己可以简单理解）04Expansion/shrinkage——rehash首先我们要知道为什么要扩容或者缩容？扩容的原因：当hashtable中存储的元素过多时，可能会因为碰撞过多，导致有一天链表非常长，最终导致查找和插入的时间复杂度很大。因此，当元素过多时，需要对其进行扩容。收缩的原因：当元素数量比较少的时候，需要收缩来节省不必要的内存。为了使哈希表的负载因子保持在一个合理的范围内，使用rehash（重新散列）操作对哈希表进行相应的扩展或收缩。负载因子的计算公式：哈希表保存的节点数/哈希表的大小load_factor=ht[0].used/ht[0].size扩容条件：（满足任意一个即可）1）Redis服务器当前没有正在执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。2）Redis服务器当前正在执行BGSAVE或者BGREWRITEAOF命令，并且负载hashtable的factor大于等于5。（为什么这里的loadfactor不一样？）缩容的条件：hashtable的loadfactor小于0.1。4.1.rehash字典的哈希表Step1)为ht[1]分配空间进行扩展操作，则ht[1]的大小为大于等于ht[0].used*的第n次方收缩2操作，则ht[1]的大小为大于等于ht[0]的2的1次方。used2）将ht[0]中的数据传输到ht[1]，在传输过程中，重新计算键的哈希值和索引值，然后将键值对放在ht[1]的指定位置。3）当ht[0]的所有key-value对迁移到ht[1]时（ht[0]变成空表），释放ht[0]，然后将ht[1]设置为ht[0]，并最终为ht[1]分配一个空白哈希表：4.2、查看一次哈希表的rehash扩展过程1）在开始rehash之前2）为ht[1]分配空间，即ht[0]的当前值。used为4，8恰好是大于等于4的2的N次方，所以ht[1]哈希表的大小当前设置为8。3）重新hashht[的所有键值对[0]到ht[1]ht[0]键值对已经迁移到ht[1]4）释放ht[0]，设置ht[1]为ht[0]，然后设置ht[1]为一个空的hashtablerehashexpansion为什么无论是执行BGSAVE还是BGREWRITEAOF命令，Redis服务器hashtable扩容所需的负载因子（1或5）都不一样？因为当执行BGSAVE或BGREWRITEAOF命令时，Redis需要创建一个server进程的子进程，运行系统使用COW，即copy-on-write技术来优化子进程的效率。因此，当有子进程存在时，服务器会增加扩容所需的负载因子，从而尽可能避免子进程存在期间的扩容，避免不必要的内存写操作，最大程度地节省内存。05Progressiverehash为什么需要progressiverehash？当元素个数很少的时候，rehash会非常快，但是当元素个数达到几百甚至上亿的时候，rehash就会是一个非常耗时的操作。如果一次性将几千万个元素的key-value对rehash到ht[1]，巨大的计算量可能会导致服务器停止服务一段时间，非常危险！所以rehash这个动作不能一下子做完。集中完成，分多次逐步完成。5.1.Progressiverehash步骤：1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。2）在字典中维护一个索引计数器变量rehashidx，并将其值设置为0，表示rehash工作正式开始。3）rehash过程中，每次对字典进行CRUD操作：增删改查，程序不仅会执行指定的操作，还会添加ht[0]哈希表的所有keyrehashidx索引上的值对rehash到ht[1]。当rehash工作完成后，程序会rehashidx+1（表示下次对下一个bucket进行rehash）。4）随着字典操作的不断执行，在某个时间点，ht[0]的所有键值对都会被rehash到ht[1]。此时程序将rehashidx属性的值设置为-1，表示rehash完成。progressiverehash的优点是采用了分而治之的方法，将rehash键值对所需的计算工作平均分配到每次对字典的增删改查操作中，从而避免了庞大的集中重新散列的数量。计算。5.2.看下一个完整的progressiverehash扩容过程1)Prepareforprogressiverehashprepareforrehash2)此时rehashidx=0，即index为0的key-valuepair会迁移到on上的key-valuepairrehashindex03）接下来，rehashidx继续增加。如果最后迁移索引3，则如下：最后一次rehash，迁移索引3上的键值对4)Gradualrehash结束。复述结束。了解了原理和流程，那么你可能会有以下疑问：迁移过程中，会不会导致读取的数据变少？不会，因为在迁移的时候，数据会先从ht[0]读取，如果ht[0]读取不到，就会去ht[1]读取。迁移过程中，新增的数据会存储在哪个ht中？迁移过程中，新增的数据只会存储在ht[1]中，不会存储在ht[0]中。将被添加。06总结1）字典被Redis广泛用于各种功能，例如数据库和哈希键。2）Redis字典的底层是通过哈希表实现的。每个字典包含两个哈希表ht[0]和ht[1]。ht[1]仅在重新散列时有用。3）哈希表采用链地址法解决哈希冲突，将分配给同一索引的键值对连接成一个单向链表。4）哈希表的rehash不是一次完成，而是分多次逐步完成。5）哈希表rehash的条件：扩容：（满足任意一个）a）Redis服务器当前没有执行BGSAVE或BGREWRITEAOF命令，且哈希表的负载因子大于等于1。b）Redis服务器当前正在执行BGSAVE或BGREWRITEAOF命令，哈希表的负载因子大于等于5。缩放：哈希表的负载因子小于0.1。6）无论是执行BGSAVE还是BGREWRITEAOF命令，Redis服务器哈希表进行扩容所需的负载因子是不同的。因为此时子进程使用了??copyonwrite，需要占用一定的内存，所以需要增加扩容所需的loadfactor，避免子进程存在期间扩容到可能，并避免不必要的内存写操作，最大限度地节省内存。知道了Redis字典哈希表的扩展，你知道JavaConcurrentHashMap(1.8)扩展的区别吗？也就是说得出这个问题：Redis的字典增量扩容和ConcurrentHashMap的扩容策略？那么他们在扩展，CRUD有什么区别呢？1）扩容所花费的时间是对比单线程渐进式扩容和多线程协同扩容。平均而言，ConcurrentHashMap更快。这也意味着可以更快地释放扩展所需的空间。2）对于读操作，两者的性能差不多。3）对于写操作，Redis字典返回更快，因为它不像ConcurrentHashMap那样有助于扩容（当要写入的bucket已经移动到newTable中），扩容完成后才能进行操作，而redis是直接。新添加的元素被添加到ht[1]。4）删除操作同写。最后，我们应该选择单线程增量扩展还是多线程协同扩展？具体问题具体分析：1）如果内存资源紧张，希望能够快速扩容释放扩容所需的辅助空间，那么选择后者。2）如果要求写入和删除操作速度快，那么可以选择前者。参考：#1《redis设计与实现》#2https://blog.csdn.net/jiji1995/article/details/64127460#3https://blog.csdn.net/u010710458/article/details/80604740#4源码分析:https://www.jianshu.com/p/a57a6e389a03
