為什么80%的碼農(nóng)都做不了架構(gòu)師？>>> ??

公司有個項目用到hash，同事從redis的代碼里摳了hashTable的源碼出來，最近抽空看了一下，設(shè)計還是很精妙的。 現(xiàn)在把閱讀的結(jié)果寫寫，以備后面復(fù)習(xí)可用（記得之前看過一次，后來長時間沒看了就忘記了，這次再看基本要從頭開始）

源碼位置

• dict.h
• dict.c

圖示

(摘自redis設(shè)計與實現(xiàn)) 參考這里

設(shè)計思路

• 這個hash(字典)他包含了兩個table，為什么有兩個呢？那是因為他要實現(xiàn)自動擴展，每次要add新元素的時候都要 判斷一下是否需要擴展(expand)
• 兩個table再掛上2的倍數(shù)(size) 的桶，每個桶都是一個鏈表。
• 當達到條件需要擴展的時候，一般是元素的個數(shù)和桶的比例差不多是1：1， 那就將第一個table生成第一個的size *2 為什么要是2的倍數(shù)呢？有幾個好處：1.分布更均勻 2.碰撞幾率更小 但是還有一個更重要的原因是： a%b可以替換成了a&(b-1) ，當hashtable的長度是2的冪的情況下。這樣運算速度可以提高很多，具體可以參考這里
• 當新的table生成后，桶數(shù)擴大了一倍，這樣就大大地減少了碰撞，但是就帶來了一個原來的數(shù)據(jù)是rehash的問題
• 當rehash開始后，如果有增，刪，查的操作，每次都搬一個桶到新的table上，如果已經(jīng)開始rehash,那么，新增的元素就直接插到新的桶上
• 當rehash全部完成后，舊talbe釋放掉，新table接替舊table成為主力工作。
• 還給hash設(shè)置了迭代器(iterators), 當有迭代器存在的時候，為了安全就不進行rehash的步驟。

參考資料

• 為啥要用位運算代替取模呢
• 圖解redis之數(shù)據(jù)結(jié)構(gòu)篇

轉(zhuǎn)載于:https://my.oschina.net/mawx/blog/893393

總結(jié)

以上是生活随笔為你收集整理的redis源码阅读--hashTable的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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