Redis的字典渐进式扩容与ConcurrentHashMap的扩容策略⽐
redis支持的数据结构较
本⽂介绍Redis的字典(是种Map)与ConcurrentHashMap的扩容策略，并⽐较它们的优缺点。
(不讨论它们的实现细节)
dict是Redis的hash数据结构，所有类型的元素都可以依据key值计算hashkey，然后将元素插⼊到dict的某个hash链上（采⽤拉链法解决hash冲突）。其中，dict的中的hashtable(dictht)的扩容是dict很重要的部分。Redis的“管家”函数serverCron会依据⼀定的算法（dict中的used与size的⽐值）判定是否开始进⾏hashtable的扩容。dict中的ht[1]是作为扩容的临时数据，扩容之
后，hashtalbe的长度将变长，那么hashtalbe的sizemask(哈希表⼤⼩掩码，⽤于计算索引值，总是到等于size-1)与原来的sizemask就不同了，那么计算出的hashkey也将不同。所以就需要Rehash对ht[0]中的元素重新计算hashkey。
在Rehash阶段，⾸先将原来的ht[0]中的元素重新rehash到ht[1]中，故⽽要耗费⼤量的⼒⽓从新计算原来的ht[0]表中元素的在ht[1]表总的hashkey，并将元素转移到ht[1]的表中。由于这样Rehash会耗费⼤量的系统资源，如果⼀次性完成⼀个dict的Rehash⼯作，那么将会对系统中的其他任务造成延迟？
⾸先Redis的字典采⽤的是⼀种‘’单线程渐进式rehash‘’，这⾥的单线程是指只有⼀个线程在扩容，
⽽在扩容的同时其他的线程可以并发的进⾏读写。
Redis系统后台会定时给予扩容的那个线程⾜够的运⾏时间，这样不会导致它饿死。
⼤致过程是这样的：
ht[0]，是存放数据的table，作为⾮扩容时容器。
ht[1]，只有正在进⾏扩容时才会使⽤，它也是存放数据的table，长度为ht[0]的两倍。
扩容时，单线程A负责把数据从ht[0] copy到ht[1] 中。如果这时有其他线程
进⾏读操作：会先去ht[0]中，不到再去ht[1]中。
进⾏写操作：直接写在ht[1]中。
进⾏删除操作：与读类似。
当然这过程中会设计到⼀系列的锁来保证同步性，不过这并不是本⽂的重点。
⽽ConcurrentHashMap采⽤的扩容策略为： “多线程协同式rehash“。
这⾥的多线程指的是，有多个线程并发的把数据从旧的容器搬运到新的容器中。
扩容时⼤致过程如下：
线程A在扩容把数据从oldTable搬到到newTable，这时其他线程
进⾏get操作：这个线程知道数据存放在oldTable或是newTable中，直接取即可。
进⾏写操作：如果要写的桶位，已经被线程A搬运到了newTable。
那么这个线程知道正在扩容，它也⼀起帮着扩容，扩容完成后才进⾏put操作。
进⾏删除操作：与写⼀致。
两者对⽐：
1.扩容所花费的时间对⽐：
⼀个单线程渐进扩容，⼀个多线程协同扩容。在平均的情况下，是ConcurrentHashMap快。这也意味着，扩容时所需要
花费的空间能够更快的进⾏释放。
2.读操作，两者的性能相差不多。
3.写操作，Redis的字典返回更快些，因为它不像ConcurrentHashMap那样去帮着扩容(当要写的桶位已经搬到了newTable时)，等扩容完才能进⾏操作。
4.删除操作，与写⼀样。
所以是选择单线程渐进式扩容还是选择多线程协同式扩容，这个就具体问题具体分析了。
1.如果内存资源吃紧，希望能够进⾏快速的扩容⽅便释放扩容时需要的辅助空间，且那么选择后者。
2.如果对于写和删除操作要求迅速，那么可以选择前者。
个⼈觉得ConcurrentHashMap的扩容策略更让⼈惊艳，效果也不错。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。