一、寫在前面

現代編程語言一般都提供了hash表的容器, 比如c++的std::hash_map, golang的map底層都使用了hash table, 是什麼魔法讓hash table在編程中佔有一席之地，下面的內容會慢慢揭曉這個答案。

二、hash表的組成

在聊hash表的實現，先問一個問題。對於數組的訪問可以使用索引，array[0]， 就可以取得0索引的值， 取值的效率是O(1)， 如果對於字符串類型如果也能實現類似的訪問， 那不是很完美，先字符串轉數字， 再變成array[0]取值，那效率也是O(1)。

上圖中神秘黑魔法就是hash函數，那麼hash函數這麼牛逼，有沒有什麼問題? hash函數最大的問題就是hash衝突，如下圖， 面對不同的字符串對映射到同一個槽位。

在工程實踐中， 一般使用掛鏈的方式， 就是每個hash table裏面的槽位都是鏈表，衝突之後就是把新節點加到鏈表的表尾。

三、redis是如何實現雙hash表的

3.1 衝突掛鏈的效率優化

在一般hash table的實現中，聊到了使用掛鏈表的方式解決hash衝突。那有一個問題，隨着數據越來越多, 衝突的概率也是越來越大。一個槽位裏面掛1000個節點，還有啥效率可言。既然衝突不可避免, 那當槽位裏面掛的節點超過一定比例, 就擴容一個新的hash table, 這個新舊同時存在的狀態定為rehashing，更大的hash table，可以讓衝突槽位的鏈表長度降低，從而提升效率。假如這個點可行， 後面無非是工程問題。

3.2 擴容流程

上面已經想到用雙hash表的方式提升數據擴容之後的訪問效率，那現在討論insert流程，訪問的過程是先訪問舊的hash table，然後再訪問新的hash table，刪除同理。

注意：

這裏面有個優化點， 為了儘量避免rehashing對業務造成影響，需要平均操作的影響，每次get delete set操作，都遷移一些數據到新hash表中，這也是redis hashtable裏面的實現。

來個流程圖説明下。

3.3 收縮流程

收縮流程可以在hash table內部做，也可以在外部做。
hash table一般實現是指針數據，假如對一個hash table存入100w元素，再刪除掉。

説明：

不支持內部自動收縮的hash table，一般會浪費7.6MB的空間(64位機器) 8 * 1000000 / 1024/1024.0 = 7.62890625，這裏的8是64位機器一個指針的字節數，除以一個1024單位是KB，再除以一個1024就是MB。浪費空間也不大，現代手機都動不動8GB以上RAM。

如果還是極在意這個點，可以提供一個收縮函數給外部調用。

四、核心代碼

如下為golang移值redis雙hash表的核心代碼，供參考。

// 元素
type entry[K comparable, V any] struct {
    key  K
    val  V
    next *entry[K, V]
}

type config struct {
    hashFunc func(str string) uint64
    cap      int
}

// hash 表頭
type HashMap[K comparable, V any] struct {
    // 大多數情況, table[0]裏就存在hash表元素的數據
    // 大小一塵不變hash隨着數據的增強效率會降低, rhashmap的實現是超過某閾值時
    // table[1] 會先放新申請的hash表元素, 當table[0]都移動到table[1]時, table[1]賦值給table[0], 完成一次hash擴容
    // 移動的操作都分攤到Get, Set, Delete操作中, 每次移動一個槽位, 或者跳運100個空桶(TODO修改代碼, 需要修改這邊的註釋)
    table   [2][]*entry[K, V] //hash table
    used    [2]uint64         // 記錄每個table裏面存在的元素個數
    sizeExp [2]int8           //記錄exp

    rehashidx int // rehashid目前的槽位
    keySize   int //key的長度
    config
    isKeyStr bool //是string類型的key, 或者不是
    init     bool
}

// 返回索引值和entry
func (h *HashMap[K, V]) findIndexAndEntry(key K) (i uint64, e *entry[K, V], err error) {
    if err := h.expand(); err != nil {
        return 0, nil, err
    }

    hashCode := h.calHash(key)
    idx := uint64(0)
    for table := 0; table < 2; table++ {
        idx = hashCode & sizeMask(h.sizeExp[table])
        head := h.table[table][idx]
        for head != nil {
            if key == head.key {
                return idx, head, nil
            }

            head = head.next
        }

        if !h.isRehashing() {
            break
        }
    }

    return idx, nil, nil
}

// 設置, 這裏可以看下insert的流程
func (h *HashMap[K, V]) Set(k K, v V) error {
    h.lazyinit()
    if h.isRehashing() {
        h.rehash(1)
    }

    index, e, err := h.findIndexAndEntry(k)
    if err != nil {
        return err
    }

    idx := 0
    if h.isRehashing() {
    //如果在rehasing過程中, 如果這個key是第一次存入到hash table, 優先寫入到新hash table中
        idx = 1 
    }

  // element存在, 這裏是替換
    if e != nil {
        //e.key = k
        e.val = v
        return nil
    }

    e = &entry[K, V]{key: k, val: v}
    e.next = h.table[idx][index]
    h.table[idx][index] = e
    h.used[idx]++
    return nil
}

五、性能壓測

如下為性能壓測數據：

• 讀取速度比標準庫快一倍
• 寫入速度較標準庫每次慢0.018ns

goos: darwin
goarch: amd64
pkg: github.com/guonaihong/gstl/rhashmap
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
BenchmarkGet-8       1000000000          0.4066 ns/op
BenchmarkGetStd-8    1000000000          0.8333 ns/op
PASS
ok   github.com/guonaihong/gstl/rhashmap 130.007s.
比標準庫快一倍.

goos: darwin
goarch: amd64
pkg: github.com/guonaihong/gstl/rhashmap
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
BenchmarkSet-8          1000000000             0.1690 ns/op
BenchmarkSetStd-8       1000000000             0.1470 ns/op
PASS
ok      github.com/guonaihong/gstl/rhashmap    3.970s

五百萬數據的Get操作時間

六、完整代碼

如果對其餘部分也感興趣， 可以查看如下網址， 包含Get、 Set、 Delete完整的實現。
https://github.com/guonaihong...