聲明：本篇博客內容來自《Redis深度歷險》一書，略有改動 字典的結構 在 Redis 中所有的 key 都存儲在一個很大的字典中，這個字典的結構和 Java 中的 HashMap 一樣，是一維數(shù)組 + 二維鏈表結構，如下圖，第一維數(shù)組的大小總是 2^n(n>=0)，擴容一 次數(shù)組大小空間加倍，也就是 n++ scan 指令返回的游標就是第一維數(shù)組的位置索引，我們將這個位置索引稱為槽 (slot)。 如果不考慮字典的擴容縮容，直接按數(shù)組下標挨個遍歷就行了。limit 參數(shù)就表示需要遍歷的槽位數(shù)，之所以返回的結果可能多可能少，是因為不是所有的槽位上都會掛接鏈表，有些槽位可能是空的，還有些槽位上掛接的鏈表上的元素可能會有多個。每一次遍歷都會將 limit 數(shù)量的槽位上掛接的所有鏈表元素進行模式匹配過濾后，一次性返回給客戶端 scan 遍歷順序 scan 的遍歷順序非常特別。它不是從第一維數(shù)組的第 0 位一直遍歷到末尾，而是采用了高位進位加法來遍歷。之所以使用這樣特殊的方式進行遍歷，是考慮到字典的擴容和縮容時避免槽位的遍歷重復和遺漏 普通加法和高位進位加法的區(qū)別 高位進位法從左邊加，進位往右邊移動，同普通加法正好相反。但是最終它們都會遍歷所有的槽位并且沒有重復 字典擴容 Java 中的 HashMap 有擴容的概念，當 loadFactor 達到閾值時，需要重新分配一個新的2 倍大小的數(shù)組，然后將所有的元素全部 rehash 掛到新的數(shù)組下面。rehash 就是將元素的hash 值對數(shù)組長度進行取模運算，因為長度變了，所以每個元素掛接的槽位可能也發(fā)生了變 化。又因為數(shù)組的長度是 2^n 次方，所以取模運算等價于位與操作 a mod 8 = a & (8-1) = a & 7 a mod 16 = a & (16-1) = a & 15 a mod 32 = a & (32-1) = a & 31 這里的 7, 15, 31 稱之為字典的 mask 值，mask 的作用就是保留 hash 值的低位，高位都被設置為0，接下來我們看看 rehash 前后元素槽位的變化 假設當前的字典的數(shù)組長度由 8 位擴容到 16 位，那么 3 號槽位 011 將會被 rehash 到 3 號槽位和 11 號槽位，也就是說該槽位鏈表中大約有一半的元素還是 3 號槽位，其它的元素會放到 11 號槽位，11 這個數(shù)字的二進制是 1011，就是對 3 的二進制 011 增加了 一個高位 1，如下圖 抽象一點說，假設開始槽位的二進制數(shù)是 xxx，那么該槽位中的元素將被 rehash 到 0xxx 和 1xxx(xxx+8) 中。 如果字典長度由 16 位擴容到 32 位，那么對于二進制槽位 xxxx 中的元素將被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中 對比擴容縮容前后的遍歷順序 ，如下圖 觀察這張圖，我們發(fā)現(xiàn)采用高位進位加法的遍歷順序，無論是擴容還是縮容，rehash 后的槽位在遍歷順序上是相鄰的 假設當前要即將遍歷 110 這個位置 (橙色) 擴容后，當前槽位上所有的元素對應的新槽位是 0110 和 1110(深綠色)，也就是在槽位的二進制數(shù)增加一個高位 0 或 1。這時我們可以直接從 0110 這個槽位開始往后繼續(xù)遍歷，而0110 槽位之前的所有槽位都是已經(jīng)遍歷過的，這樣就可以避免擴容后對已經(jīng)遍歷過的槽位進行重復遍歷 假設當前要即將遍歷 110 這個位置 (橙色) 縮容后，當前槽位所有的元素對應的新槽位是 10(深綠色)，也就是去掉槽位二進制最高位。這時我們可以直接從 10 這個槽位繼續(xù)往后遍歷，10 槽位之前的所有槽位都是已經(jīng)遍歷過的，這樣就可以避免縮容的重復遍歷。不過縮容還是不太一樣，它會對圖中 010 這個槽位上的元素進行重復遍歷，因為縮融后 10 槽位的元素是 010 和 110 上掛接的元素的融合，注意：這也是為什么scan命令可能會返回重復key的根本原因！ 漸進式 rehash Java 的 HashMap 在擴容時會一次性將舊數(shù)組下掛接的元素全部轉移到新數(shù)組下面。如果 HashMap 中元素特別多，線程就會出現(xiàn)卡頓現(xiàn)象 Redis 為了解決這個問題，它采用漸進式 rehash。它會同時保留舊數(shù)組和新數(shù)組，然后在定時任務中以及后續(xù)對 hash 的指令操作中漸漸地將舊數(shù)組中掛接的元素遷移到新數(shù)組上。這意味著要操作處于 rehash 中的字典，需要同時訪問新舊兩個數(shù)組結構。如果在舊數(shù)組下面找不到元素，還需要去新數(shù)組下面去尋找。scan也需要考慮這個問題，對與 rehash 中的字典，它需要同時掃描新舊槽位，然后將結果融合后返回給客戶端。 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的redis之rehash原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。