重學 HashTable

In 未分類 on 2020年12月31日 by TAT.vorshen view: 4,076

重學 HashTable

HashTable，又稱散列表，一說到這個，可能很多人第一反應就是時間復雜度 O(1)！那是不是時間復雜度永遠都是 O(1) 呢？別人說所得 hash 碰撞又是什么呢？
其實 HashTable 還是有很多細節的，這片文章就帶大家梳理一下 HashTable 的細節，最后一起拜讀一下 v8 和 redis 的 HashTable 相關源碼。

HashTable 原理

先看一段代碼

map<string, string> yori;

yori["interest"] = "drink";

cout << yori["interest"] << endl;

這段代碼基本上入門的程序員也能看得懂，但是仔細思考了一下，有兩個問題

這里 drink 常量真正存到哪里去了
為什么繼續通過 interest 可以獲取到剛剛存起來的 value

如果這兩個問題你很明確答案，那么可以直接跳到下一節，節省時間，互聯網講究敏捷。針對剛剛這兩個問題，我們換個思路，我們用數組這種更底層的數據結構來實現上面代碼的效果

int keyToIndex(const string& key) {

if (key === "yori") {

return 0;

}

// other...

}

vector<string> yori;

yori[keyToIndex("interest")] = "dirnk";

cout << yori[keyToIndex("interest")]) << endl;

針對問題 1，我們是將 drink 存到了一個數組里面去，索引是 0
針對問題 2，我們用一個函數，保證了 key 到數組索引是唯一的，所以第二次取的時候，也能找到索引 0

這也就是 HashTable 的核心，可以用如下圖來解釋

這里我們定義了幾個名詞概念，后文中可能提到

key，用戶傳入的 key，理論上可以是任意類型，常用的比如數組索引
hashKey，將用戶的 key 進行了 hash 處理，size_t 類型
fixedArray，HashTable 內部真正存放數據的部分，是一個連續的數組
entry，將 hashKey 轉換到對應的 fixedArray 索引位置上

我們來分析一下時間復雜度
在這里無論是 hash 函數，還是取余計算，乃至最后的數組尋址，都是時間復雜度為 1，綜合時間復雜度 O(1)，直接起飛???

HashTable 問題與解決

如果 HashTable 如此的簡單，我也不會寫這篇文章了。通過上一節，敏感的同學，心里可能有幾個疑問，這里可能需要討論的點有如下幾個

任何類型都能進行 hash 計算么？
沖突了怎么辦？

Q: 任何類型都能進行 hash 計算么？
A: 如果你想用某個類型作為 HashTable 的 key，那么它必須默認支持或者自定義支持 hash 函數

以 C++ 的 unordered_map 為例，如果我們有一個自定義的數據結構，希望可以成為 hash 的 key，有如下辦法

class Yori {

public:

Yori(const string& liquor): liquor_(liquor) {};

inline string liquor() const {

return liquor_;

}

private:

string liquor_;

};

// 方案1 用一個類實現一個對應的 operator

class YoriHash {

public:

std::size_t operator()(const Yori& yori) const {

return std::hash<string>{}(yori.liquor());

}

};

// 方案2 偏特化 std::hash 函數

namespace std {

template<>

struct hash<Yori> {

size_t operator()(const Yori& yori) const noexcept {

return std::hash<string>{}(yori.liquor());

}

};

} // std

int main(int argc, char* argv[]) {

unordered_map<Yori, int, YoriHash> m2; // 使用方案1

unordered_map<Yori, int> m1; // 使用方案2

return 0;

}

這里本質上，對 Yori 求 hash，變成了對 Yori 下的 liquor 這個屬性求 hash，那么 string 類型為什么能直接到 size_t 類型呢？
這是因為 gcc 等編譯器已經將這些標準庫類型提前做好偏特化了，截取部分代碼如下

// basic_string.h

#if __cplusplus >= 201103L

#include <bits/functional_hash.h>

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

// DR 1182.

#ifndef _GLIBCXX_COMPATIBILITY_CXX0X

/// std::hash specialization for string.

template<>

struct hash<string>

: public __hash_base<size_t, string>

{

size_t

operator()(const string& __s) const noexcept

{ return std::_Hash_impl::hash(__s.data(), __s.length()); } // 通用 hash 計算，感興趣可以自行了解

};

// ......

小伙伴可能會有疑問，javascript，在 ES6 中，有 Map 的這樣新的數據結構，是支持任何類型作為 key 的。因為 v8 已經支持好了數字、string、symbol、地址這些 hash 計算了，可謂是代碼放心飛，v8 永相隨。

// The Name abstract class captures anything that can be used as a property

// name, i.e., strings and symbols. All names store a hash value.

class Name : public TorqueGeneratedName<Name, PrimitiveHeapObject> {

v8 下 name.h 的注釋，可以看到 All names store a hash value.。

這樣我們第一個問題基本解決清楚了，更深的細節比如 gcc 提供的通用 hash 能力、如何盡可能避免 hash 碰撞等，可以自行了解。

Q: 沖突了怎么辦
從之前的流程可以看到，存在兩個階段可以沖突
沖突的兩個階段

對于第一階段，因為 hash 的過程是將一個無限的空間映射到一個有限的空間里，比如我們熟知的 md5 算法，在網上搜索也會有碰撞的??。
不過總的來說，這種幾率還是較小的，用戶在正常使用中，一般還是較難遇到碰撞的情況。

對于第二階段，取余的沖突可能性就太大了，當數組長度過小時概率不要太大。我們也不能無腦將數組長度設置的很大，很可能會造成空間浪費的情況。

這里有個名詞叫做 loadFactor(裝載因子) 來表示沖突的情況

1	loadFactor = 當前元素數量 / 數組長度

裝載因子越大，意味著沖突概率越大，那么當裝載因子是 1 的時候，是不是必沖突呢？如果你能清晰明確的給出答案，那可以直接跳到第三節。

那遇到碰撞了應該怎么辦呢？
A: 對于沖突的情況，已經有了成熟的解決方案，主要方案有如下兩種

開放尋址法
鏈表法

開放尋址法

我們用下面這個圖來講解開放尋址法插入元素的過程

1?? A 元素計算出 entry=1，對應位空，插入到數組中
2?? B 元素計算出 entry=2，對應位空，插入到數組中
3?? C 元素計算出 entry=1，對應位存在，無法插入，往后尋找
4?? 往后尋找到 entry=2，對應位存在，無法插入，繼續往后尋找
5??往后尋找到 entry=3，對應位空，插入到數組中

查找的過程也是類似的，以查找 C 元素為例
開放尋址法查找元素

1?? 計算出 entry=1，不匹配，往后尋找
2?? 往后尋找到 entry=2，不匹配，繼續往后尋找
3?? 往后尋找到 entry=3，匹配，返回

總結一下
插入時就是 entry 位已經有元素了，那我就往后找 (last->next=first)，找到第一個空的，放進去。
查找時也是循環查找，找到完全匹配的。

這里有幾個問題

數組長度不夠了怎么辦
當裝載因子變成 1 的時候，無論怎么尋址，對應位非空，空間已經不夠用了。那時候我們就得重新申請更長的數組長度，這個過程一般稱為 rehash。
一直查找不到的情況下，會不會死循環
插入類型，必須要保證空間足夠
查找類型不會死循環，當尋找到空位置或者原點的時候，就認為不在表中。
如何確保不會取錯
因為 entry 甚至 hashKey 都可能存在沖突，所以切記不能只存一個 value。key(原始 key，因為 hashKey 可能已經沖突了) 也需要存，比對的時候需要比對 key。
刪除導致的空，會影響尋址的地址，這里用個圖舉例

首先插入 C，但是發現 entry=1 存在，所以真實放到了 entry=2
插入C

刪除了 B，如果就直接將 entry=1 清空
刪除B

此時再查找 C，hash 之后發現 entry=1 為空，那就認為 C 不在表中，打出 GG
查找C

所以對于開放尋址法，刪除導致的空和真正的空是要區分的。

// HashTable is a subclass of FixedArray that implements a hash table

// that uses open addressing and quadratic probing.

// In order for the quadratic probing to work, elements that have not

// yet been used and elements that have been deleted are

// distinguished. Probing continues when deleted elements are

// encountered and stops when unused elements are encountered.

// - Elements with key == undefined have not been used yet.

// - Elements with key == the_hole have been deleted.

v8 的 HashTable 的開頭注釋也特地說明了這一點。

鏈表法

先用圖來講解下鏈表法插入元素
鏈表法查找元素
0? 首先這里增加了一個桶 (bucket) 的概念，數組里面每一位是一個桶 (鏈表)，不再直接存 key-value
1?? A 元素計算出 entry=1，將其放入到對應的桶中
2?? B 元素計算出 entry=2，將其放入到對應的桶中
3?? C 元素計算出 entry=1，繼續將其放入到對應的桶中 (鏈表長度為 2)

查找的過程就不畫圖了，一句話概括就是：先查找數組索引，再遍歷鏈表

我們對比一下開放尋址法，似乎鏈表法更優勢，因為它不存在「數組長度不夠」的問題。
但是，rehash 仍然會進行！因為用 HashTable 是為了它迷人的 O(1) 時間復雜度。
當裝載因子大于 1，越來越大時，雖然鏈表法下不一定沖突，但是后續的插入、查找操作都有大概率變成在鏈表上進行，時間復雜度降為 O(n)，這和我們初衷背道而馳了。

redis 中就是采取的鏈表法，v8 中也有部分采用了，后面細說。

還有一些其他的解決沖突的方案這里就不展開了，感興趣的同學可以自行了解。

v8 中的 HashTable

剛剛提到了，v8 中的 HashTable 有使用開放尋址法的，也有使用鏈表法的，我們先講一下開放尋址法相關的使用。

v8 中的開放尋址法

因為平時在寫 js 的過程中，大部分開發很少關注 v8 內部的實現，所以如果直接切入 v8，可能會有點懵逼，所以我們還是先用 js 來引入一個問題，先看如下這段代碼：

1 2	const yori = new Array(1000); const yussica = new Array(1001);

上面代碼就是定義了兩個空數組，長度分別是 1000 和 1001，此時我們看一下內存的情況
yori 內存
yussica 內存

可以看到 length 多的那個數組 (yussica) 多了 4b，我 length 多點，占用多點空間沒毛病。
然鵝，當數組長度大到一定大小之后就不生效了??！

1 2	const yori = new Array(33554432); const yussica = new Array(33554433);

內存結構變成了這樣
yori 內存
yussica 內存
可以看到 yori 數組還是很大，基本上還是滿足剛剛的規律的。
但是！yussica 數組占用空間變得很小了，不過對于開發使用起來并沒有感覺到什么差異，這是為什么呢？

因為當數組長度超過 32 1024 1024 時，JSArray 的內部實現，會由 FastElement 模式（FixedArray 實現），變成 SlowElement 模式（HashTable 實現）
下面是 v8 對 JSArray 的注釋

// The JSArray describes JavaScript Arrays

// Such an array can be in one of two modes:

// - fast, backing storage is a FixedArray and length <= elements.length();

// Please note: push and pop can be used to grow and shrink the array.

// - slow, backing storage is a HashTable with numbers as keys.

FastElement 模式我們不討論，主要看 SlowElement 模式。
我在 v8 中增加了一些關鍵節點的 log，然后我們執行一段 js 代碼，看一下 v8 干了什么

console.log('Start');

const yussica = [];

yussica.length = 111111111; // 整個大數組，命中 SlowElement 模式

yussica[0] = 0;

yussica[1] = 1;

yussica[2] = 2;

console.log('End');

代碼很簡單，肯定看的懂，下面看 log 情況

Start

[v8][JSArray::SetLength], prepare, new_length: 111111111

[v8][JSArray::SetLengthWouldNormalize], 當前 FastElement, 判斷是否需要轉換為 SlowElement

[v8][JSArray::SetLengthWouldNormalize], new_length(111111111) > kMaxFastArrayLength(33554432)

[v8][ShouldConvertToSlowElements], old_capacity: 0, new_capacity: 0

[v8][JSArray::SetLength], 轉換成 FastElement, Capacity: 4

[v8][JSArray::SetLength], done

[v8][JSObject::AddDataElement], index: 0

[v8][DictionaryElementsAccessor::AddImpl], 使用了 DictionaryElementsAccessor 添加元素

[v8][Dictionary::Add], 計算出 hash: 993088831

[v8][HashTable::EnsureCapacity], 空間足夠

[v8][Dictionary::Add], 計算出 entry: 3

[v8][JSObject::AddDataElement], index: 1

[v8][DictionaryElementsAccessor::AddImpl], 使用了 DictionaryElementsAccessor 添加元素

[v8][Dictionary::Add], 計算出 hash: 732518952

[v8][HashTable::EnsureCapacity], 空間足夠

[v8][Dictionary::Add], 計算出 entry: 0

[v8][JSObject::AddDataElement], index: 2

[v8][DictionaryElementsAccessor::AddImpl], 使用了 DictionaryElementsAccessor 添加元素

[v8][Dictionary::Add], 計算出 hash: 742761112

[v8][HashTable::EnsureCapacity], 空間足夠

[v8][Dictionary::Add], 計算出 entry: 1

End

這里標注出了內部的方法名，方便感興趣看源碼的同學可以自行查閱

因為 v8 繼承非常的多，代碼跳躍性太強，從上面可以看到又是 JSObject、又是 Dictionary、又是 HashTable 的。如果想把這里完全講清楚，一篇文章遠遠不夠，所以這里給一個縮減版的 UML 圖，只涉及到數組的一個 push 操作所用到的。
縮減版 UML

本身調用的入口在 JSObject 這個基類上，而 JSObject 可能是多種類型，所以這里通過 Kind 找到了對應的 Accessor(DictionaryElementsAccessor)，再去走到 NumberDictionary 去 Add。 NumberDictionary 就是 HashTable 的派生類之一。

然后關于 HashTable 內部的內存分布這里也給一下，直接看代碼容易繞暈，對照著圖看就會清晰一下。
HashTable 內存分布

v8 因為代碼太多太復雜，本文只從宏觀的層面去講解 (redis 會細致一點)
通過上面的內存分布圖，其實大家也能還原出來一個結構，v8 具體實現的代碼就不貼了，因為太多了，而且繼承層次很深。

其實理清了類之間的關系（或者只關心流程，不要在乎具體函數調用），這里添加元素的流程和之前說的一致

傳入 key-value，這里 key 就是數組索引，分別對應 0、1、2
計算 hashKey，結果分別是 993088831、732518952、742761112
計算 entry，結果分別是 3、0、1
這里注意了！在 Capacity 為 4 的情況下，直接 Mask 與運算得到的結果是如下的

所以 index:742761112 最終到 entry:1 就是開放尋址法起到了作用，核心具體代碼如下：

template <typename Derived, typename Shape>

InternalIndex HashTable<Derived, Shape>::FindInsertionEntry(IsolateRoot isolate,

ReadOnlyRoots roots,

uint32_t hash) {

uint32_t capacity = Capacity();

uint32_t count = 1;

// EnsureCapacity will guarantee the hash table is never full.

for (InternalIndex entry = FirstProbe(hash, capacity);;

entry = NextProbe(entry, count++, capacity)) {

if (!IsKey(roots, KeyAt(isolate, entry))) return entry;

}

不要管模版和其他，只關注 for 循環，這里有兩次查詢

inline static InternalIndex FirstProbe(uint32_t hash, uint32_t size) {

return InternalIndex(hash & (size - 1));

}

inline static InternalIndex NextProbe(InternalIndex last, uint32_t number,

uint32_t size) {

return InternalIndex((last.as_uint32() + number) & (size - 1));

}

其中 FirstProbe 很好理解，找到第一次 entry 可能的位置，如果發現位置已經有 key 了，那么就循環執行 NextProbe。
前面我們相當于通過 ++ 來執行 NextProbe 的，v8 這里步長會增大。

v8 絲毫不擔心出現死循環，因為這一行注釋說的很清楚
// EnsureCapacity will guarantee the hash table is never full.

EnsureCapacity 就是通過 rehash 來保證的，具體怎么做的我們研究一下，再回到 js 代碼

console.log('Start');

const yussica = [];

yussica.length = 111111111;

yussica[0] = 0;

yussica[1] = 1;

yussica[2] = 2;

yussica[3] = 3; // 新增一行

console.log('End');

我們新增了一行，會發生什么呢？

……略

[v8][JSObject::AddDataElement], index: 3

[v8][DictionaryElementsAccessor::AddImpl], 使用了 DictionaryElementsAccessor 添加元素

[v8][Dictionary::Add], 計算出 hash: 509378648

[v8][HashTable::EnsureCapacity], 空間不夠

[v8][HashTable::EnsureCapacity], new Capacity: 8

[v8][HashTable::Rehash], 進行 Rehash

[v8][HashTable::Rehash], old_entry(0), new_entry(1)

[v8][HashTable::Rehash], old_entry(1), new_entry(3)

[v8][HashTable::Rehash], old_entry(3), new_entry(4)

[v8][Dictionary::Add], 計算出 entry: 6

前面一些 log 我省略了，主要就是看一下空間不夠的時候 v8 的處理。
很清晰，capacity=4 不夠的時候，按 2 的倍數擴張，變成 8，然后 rehash?？梢钥吹街?entry 的位置發生了變化，從之前 0-3 的空間變化到了 0-7 的空間。

具體代碼

template <typename Derived, typename Shape>

void HashTable<Derived, Shape>::Rehash(IsolateRoot isolate, Derived new_table) {

DisallowGarbageCollection no_gc;

WriteBarrierMode mode = new_table.GetWriteBarrierMode(no_gc);

DCHECK_LT(NumberOfElements(), new_table.Capacity());

// Copy prefix to new array.

for (int i = kPrefixStartIndex; i < kElementsStartIndex; i++) {

new_table.set(i, get(isolate, i), mode); // (1)

}

// Rehash the elements.

ReadOnlyRoots roots = GetReadOnlyRoots(isolate);

for (InternalIndex i : this->IterateEntries()) {

uint32_t from_index = EntryToIndex(i);

Object k = this->get(isolate, from_index);

if (!IsKey(roots, k)) continue;

uint32_t hash = Shape::HashForObject(roots, k);

uint32_t insertion_index =

EntryToIndex(new_table.FindInsertionEntry(isolate, roots, hash));

new_table.set_key(insertion_index, get(isolate, from_index), mode); // (2)

for (int j = 1; j < Shape::kEntrySize; j++) {

new_table.set(insertion_index + j, get(isolate, from_index + j), mode); // (3)

}

new_table.SetNumberOfElements(NumberOfElements());

new_table.SetNumberOfDeletedElements(0);

}

看這段代碼，核心重點就是標注出來的三個 set，可以結合之前發的 HashTable 內存結構圖對照查看。
1?? 拷貝前綴大小
2?? 拷貝 shape 中的 key
3?? 拷貝 shape 中的 value(按字節拷貝)

v8 中的鏈表法

之前通過 js 超大數組，v8 將其轉成了 NumberDictionary。NumberDictionary 底層是用開放尋址法實現的 HashTable，那什么是用鏈表法實現的 HashTable 呢？

我們不賣關子了，ES6 中的 Set 和 Map 就是用鏈表法實現的 HashTable，內部類是 OrderedHashTable?；蛟S你已經對 Ordered 關鍵字開始疑惑了，不過不用擔心，讓我們一步一步分析。

很多語言都有 Map，比如 C++11 標準庫就提供了 map 和 unordered_map，區別就是有無序。

int main(int argc, char* argv[]) {

unordered_map<char, int> m1;

m1.insert({'a', 1});

m1.insert({'c', 3});

m1.insert({'b', 2});

for (auto t : m1) {

cout << t.first << endl;

}

cout << "-----" << endl;

map<char, int> m2;

m2.insert({'a', 1});

m2.insert({'c', 3});

m2.insert({'b', 2});

for (auto t : m2) {

cout << t.first << endl;

}

return 0;

}

結果如圖
排序結果
可以看到是按字典序排序的

那 js 中的 Map 有序么？在控制臺執行發現很神奇的現象是有序的，但是和 C++ 中的 map 又不太一樣，它不是按照字典序，而是按照插入的順序
運算結果

是不是很神奇，v8 在這里底層用的是 OrderedHashTable，這里先給一下 OrderedHashTable 的內存分布圖
OrderedHashTable 內存分布圖
這里主要講一下 bucket 和 shape

buckets 其實就是 HashTable(類比文中 fixedArray 概念)，buckets 的數量就是 hashkey 到 entry 的影響因素
后面的 shapes 數組是存放元素的。將多鏈表放進了用連續的內存中去，避免內存碎片。所以 shape 有三個部分組成了，多了一個 link，這個會鏈到前一個相同的 entry 的 shape
這樣一來，從前往后按順序添加，遍歷的順序就是插入時的順序，同時也是滿足了 HashTable 碰撞時鏈表法的模型

我同樣是加了一些 log，執行一段 js 看看

console.log('Start');

const yori = new Map();

yori.set('drinkA', '青島');

yori.set('drinkB', '百威');

yori.set('drinkC', '科羅娜');

yori.set('drinkD', '烏蘇');

console.log('End');

Start

[v8] Set Map, key(68194992), hash(1065593762), entry(0), capacity(2)

[v8] Set Map, key(68195010), hash(290311991), entry(1), capacity(2)

[v8] Set Map, key(68195028), hash(453829301), entry(1), capacity(2)

[v8] Set Map, key(68195048), hash(749864448), entry(0), capacity(2)

End

先給一個噩耗，v8 目前這里對 Map、Set 的接口相關有點亂。感興趣看源碼的同學可以直接看 js-collection.h，看數據結構清晰很多。不建議直接跟執行流程，如果硬要跟，看 builtins-collections-gen.cc

有了之前的經驗，這個應該很好理解了，核心也是三部曲，key->hashKey->entry。
特別一點的就是這里默認的 bucket 數量是 2。
bucket 的數量是 capacity(初始值 4) / 極限裝載因子 (2)。這里不像開放尋址法，entry 完全可以相同。

最核心的代碼就是如下

void CollectionsBuiltinsAssembler::StoreOrderedHashMapNewEntry(

const TNode<OrderedHashMap> table, const TNode<Object> key,

const TNode<Object> value, const TNode<IntPtrT> hash,

const TNode<IntPtrT> number_of_buckets, const TNode<IntPtrT> occupancy) {

const TNode<IntPtrT> bucket = // (1)

WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));

TNode<Smi> bucket_entry = CAST(UnsafeLoadFixedArrayElement( // (2)

table, bucket, OrderedHashMap::HashTableStartIndex() * kTaggedSize));

// Store the entry elements.

const TNode<IntPtrT> entry_start = IntPtrAdd( // (3)

IntPtrMul(occupancy, IntPtrConstant(OrderedHashMap::kEntrySize)),

number_of_buckets);

UnsafeStoreFixedArrayElement(

table, entry_start, key, UPDATE_WRITE_BARRIER,

kTaggedSize * OrderedHashMap::HashTableStartIndex());

UnsafeStoreFixedArrayElement(

table, entry_start, value, UPDATE_WRITE_BARRIER,

kTaggedSize * (OrderedHashMap::HashTableStartIndex() +

OrderedHashMap::kValueOffset));

UnsafeStoreFixedArrayElement( // (4)

table, entry_start, bucket_entry,

kTaggedSize * (OrderedHashMap::HashTableStartIndex() +

OrderedHashMap::kChainOffset));

// Update the bucket head.

UnsafeStoreFixedArrayElement( // (5)

table, bucket, SmiTag(occupancy),

OrderedHashMap::HashTableStartIndex() * kTaggedSize);

// Bump the elements count.

const TNode<Smi> number_of_elements =

CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset()));

StoreObjectFieldNoWriteBarrier(table,

OrderedHashMap::NumberOfElementsOffset(),

SmiAdd(number_of_elements, SmiConstant(1)));

}

重點的說一下
1?? 這個就是找到 entry
2?? 理解為生成新的 shape 節點
3?? 找到 shape 具體的位置 (對照內存結構圖)
4?? 設置 link(前面分別是設置 key 和 value)
5??更新 entry 上 bucket 最新的引用為新加進來的元素

rehash 的處理和 HashTable 區別不大，這里就不展開了。

redis 中的 HashTable

redis 以快著稱，它內部的 dict 類就是使用 HashTable 實現的。
因為 redis 負責的事情更純粹，所以代碼也較好理解易讀很多，我們就以源碼解讀的方式為主。

需要注意的是：redis 對外暴露的接口有一個就是 Hash，但是 Hash 內部實現是 ziplist + dict，數據量不大的時候使用 ziplist，數據量大了就采用 dict。所以下面我們看代碼，直接用 Set 來講解方便點（然鵝 Set 內部實現是 intSet + dict，所以跑 demo 的時候需要用 string，不能是 int）

首先是 redis 中和 dict 相關的幾個比較重要的數據結構

dickType —— 通過自定義的方式，讓 dict 可以支持任何數據結構的 key 和 value

typedef struct dictType {

uint64_t (*hashFunction)(const void *key);

void *(*keyDup)(void *privdata, const void *key);

void *(*valDup)(void *privdata, const void *obj);

int (*keyCompare)(void *privdata, const void *key1, const void *key2);

void (*keyDestructor)(void *privdata, void *key);

void (*valDestructor)(void *privdata, void *obj);

int (*expandAllowed)(size_t moreMem, double usedRatio);

} dictType;

hashFunction 看名字+出入參應該就知道作用了
keyDup、valDup 發生拷貝操作時可以執行（一般是深拷貝），如果是 nullptr 就地址拷貝。具體可見 dict.h 中 dictSetKey、dictSetVal
keyCompare 用來比較兩個 key，如果是 nullptr 就是直接地址比較。具體可見 dict.h 中 dictCompareKeys
keyDestructor、valDestructor 是定義了 key 、value 的析構函數。具體可見 dict.h 中 dictFreeKey、dictFreeVal
expandAllowed 當 dict 需要擴大時，是否允許，如果是 nullptr，默認允許。具體可見 dict.c 中 dictTypeExpandAllowed

可以看到，通過 dictType，可以實現自定義的 key、value 組合，下面就是一個??

/* Keylist hash table type has unencoded redis objects as keys and

* lists as values. It's used for blocking operations (BLPOP) and to

* map swapped keys to a list of clients waiting for this keys to be loaded. */

dictType keylistDictType = {

dictObjHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictObjKeyCompare, /* key compare */

dictObjectDestructor, /* key destructor */

dictListDestructor, /* val destructor */

NULL /* allow to expand */

};

這里的官方注釋就已經寫的很清楚了

dict

typedef struct dict {

dictType *type;

void *privdata;

dictht ht[2];

long rehashidx; /* rehashing not in progress if rehashidx == -1 */

unsigned long iterators; /* number of iterators currently running */

} dict;

type 剛剛說過了
privdata 直譯是私有數據，創建 dict 時傳入，然后在調用上面說的那些 keyDup、valDup 等函數會傳回
dictht 重點！dict hashTable，也是 dict 實現的核心，注意，可以看到這里是個數組，長度為 2，這是為了更優雅的增量 rehash，待會會看到精妙所在
rehashidx 目前 rehash 的進度
iterators 迭代器，略

dictht —— dict 使用的 HashTable

1
2
3
4
5
6

typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
- table 之前說過 redis 的 hashTable 采取的是鏈表法，dictEntry 就是鏈表結構
- size table 的長度
- sizemask 計算 hashkey 到 entry 用的，恒等于 size-1。和上面說的 v8 做法一致
- used 目前 hashTable 中已有的元素數量，可以與 size 計算出來 loadFactor

dictEntry —— 鏈表中每個節點的數據結構 (redis 不像 v8，并沒有把鏈表放到連續內存中去)

typedef struct dictEntry {

void *key;

union {

void *val;

uint64_t u64;

int64_t s64;

double d;

} v;

struct dictEntry *next;

} dictEntry;

key 略
v value，這里使用了 union 來優化存儲
next 略

數據結構看下來，其實還是挺簡單的，至少對比 v8 的清晰明了太多。下面重點來說說 redis 的增量 rehash，這也是 redis 追求極致性能的一種體現

從前面 v8 分析中我們已經知道了 rehash 的目的是為了降低 loadFactor，讓 hash 碰撞盡可能少。但是，一次 rehash 的成本可不低：

重新申請內存大小
遷移數據 —— 拷貝/移動成本、對所有 key 進行 hash 重算

redis 作為 server 端服務，追求的快速的響應時間，越快越好，但如果某次請求，命中了 rehash，那意味著會增大單個請求響應時間，這是不能接受的。
所以 redis 的做法，是將可能的單次較長的 rehash 時間，打散開，平均到每個請求中去，下面看具體的實現。

實戰開始，我們如下的方式操作 redis
操作步驟

然后可以得到這樣的結果，我整理了一下

SADD yori a

[redis] saddCommand

[redis] 不在進行 rehash

[redis] value: a

[redis] 開始進行 Rehash

[redis] hashKey: 13728588299047492245

[redis] entry: 1

[redis] dict added, ht[0].size: 4, ht[0].used: 1

[redis] dict added, ht[1].size: 0, ht[1].used: 0

SADD yori b

[redis] saddCommand

[redis] 不在進行 rehash

[redis] value: b

[redis] hashKey: 12257755146001261976

[redis] entry: 0

[redis] dict added, ht[0].size: 4, ht[0].used: 2

[redis] dict added, ht[1].size: 0, ht[1].used: 0

SADD yori c

[redis] saddCommand

[redis] 不在進行 rehash

[redis] value: c

[redis] hashKey: 17574597941439108991

[redis] entry: 3

[redis] dict added, ht[0].size: 4, ht[0].used: 3

[redis] dict added, ht[1].size: 0, ht[1].used: 0

SADD yori d

[redis] saddCommand

[redis] 不在進行 rehash

[redis] value: d

[redis] hashKey: 36062017759904132

[redis] entry: 0

[redis] dict added, ht[0].size: 4, ht[0].used: 4

[redis] dict added, ht[1].size: 0, ht[1].used: 0

SADD yori e

[redis] saddCommand

[redis] 不在進行 rehash

[redis] value: e

[redis] 開始進行 Rehash

[redis] hashKey: 3942771329094170746

[redis] entry: 2

[redis] dict added, ht[0].size: 4, ht[0].used: 4

[redis] dict added, ht[1].size: 8, ht[1].used: 1

SADD yori f

[redis] saddCommand

[redis] 正在進行 rehash

[redis] value: f

[redis] hashKey: 15142165025344743775

[redis] entry: 7

[redis] dict added, ht[0].size: 4, ht[0].used: 2

[redis] dict added, ht[1].size: 8, ht[1].used: 4

SADD yori g

[redis] saddCommand

[redis] 正在進行 rehash

[redis] value: g

[redis] hashKey: 1768894350167553498

[redis] entry: 2

[redis] dict added, ht[0].size: 4, ht[0].used: 1

[redis] dict added, ht[1].size: 8, ht[1].used: 6

SADD yori h

[redis] saddCommand

[redis] 正在進行 rehash

[redis] value: h

[redis] hashKey: 5506351120338565809

[redis] entry: 1

[redis] dict added, ht[0].size: 8, ht[0].used: 8

[redis] dict added, ht[1].size: 0, ht[1].used: 0

我依然在源碼中將關鍵節點的信息打了出來，然后先文字分析，再畫圖總結一下
前面 a,b,c,d 的設置沒有什么好說的，還是之前的流程:
key(這里直接用 value) -> hashKey -> entry?？梢钥吹?12257755146001261976 & 3 = 0，36062017759904132 & 3 = 0，這里出現了兩個相同的 entry，不過沒關系，因為采用的是鏈表法。

核心代碼如下

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)

{

long index;

dictEntry *entry;

dictht *ht;

if (dictIsRehashing(d)) _dictRehashStep(d);

/* Get the index of the new element, or -1 if

* the element already exists. */

if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) // (1)

return NULL;

/* Allocate the memory and store the new entry.

* Insert the element in top, with the assumption that in a database

* system it is more likely that recently added entries are accessed

* more frequently. */

ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // (2)

entry = zmalloc(sizeof(*entry)); // (3)

entry->next = ht->table[index]; // (4)

ht->table[index] = entry; // (5)

ht->used++;

/* Set the hash entry fields. */

dictSetKey(d, entry, key); // (6)

return entry;

}

這里代碼并不復雜，但是由于變量命名和我們前文中概念有點沖突，所以看起來可能有點亂
1?? 找到了一個 index(文中 entry 概念)，數組的位置 (位置里每一個元素是一個鏈表 dictEntry)
2?? 找到對應的 HashTable，我們不在 Rehash 中，所以就是 ht[0]
3?? 生成一個新的鏈表節點
4??、5??將新的鏈表節點添加到鏈表的首位
6??將 key 保存到鏈表節點上

可以結合下面的圖來看一下插入 d 時結構的變化

之所以添加到表頭，也是 redis 認為最近添加的元素，被訪問到的幾率大一些

a,b,c,d 的設置講清楚了，再看下面 e,f,g,h 的設置，這里涉及到增量 rehash 了，稍微復雜一些。
我們先繼續看圖片流程，理解了流程，看代碼就清晰了。

再貼一下 rehash 的核心代碼

int dictRehash(dict *d, int n) {

int empty_visits = n*10; /* Max number of empty buckets to visit. */

if (!dictIsRehashing(d)) return 0;

while(n-- && d->ht[0].used != 0) { // (1)

dictEntry *de, *nextde;

/* Note that rehashidx can't overflow as we are sure there are more

* elements because ht[0].used != 0 */

assert(d->ht[0].size > (unsigned long)d->rehashidx);

while(d->ht[0].table[d->rehashidx] == NULL) { // (2)

d->rehashidx++;

if (--empty_visits == 0) return 1;

}

de = d->ht[0].table[d->rehashidx];

/* Move all the keys in this bucket from the old to the new hash HT */

while(de) { // (3)

uint64_t h;

nextde = de->next;

/* Get the index in the new hash table */

h = dictHashKey(d, de->key) & d->ht[1].sizemask;

de->next = d->ht[1].table[h];

d->ht[1].table[h] = de;

d->ht[0].used--;

d->ht[1].used++;

de = nextde;

}

d->ht[0].table[d->rehashidx] = NULL;

d->rehashidx++;

}

/* Check if we already rehashed the whole table... */

if (d->ht[0].used == 0) { // (4)

zfree(d->ht[0].table);

d->ht[0] = d->ht[1];

_dictReset(&d->ht[1]);

d->rehashidx = -1;

return 0;

}

/* More to rehash... */

return 1;

}

這代碼非常清晰，稍微說一下就行
1?? n 就是這次 rehash 推動的步數，默認是 1
2?? 遇到空桶 (空鏈表)，就往后遞增
3?? rehash，舊的桶轉移到新的桶，跑完整個鏈表
4?? 檢測 table[0] 是不是 rehash 結束了，如果結束了，就將 table[1] 賦給 table[0]

注意：不僅僅是插入，當在 rehash 狀態時，任何的操作，比如是 SISMEMBER 這種讀操作，也會推動 rehash 的進度，感興趣的同學，可以自己再看看 dict 中其他接口的實現，都比較清晰，主要歸功于 dict 內部所用的 HashTable 簡單明了。

總結

我們從 HashTable 的原理入手，了解掌握了實現一個 HashTable 中的難題，最后一起看了一下 v8 和 redis 中 HashTable 相關的代碼?？偟膩碚f redis 的代碼簡單易懂一些，推薦入門同學先看 redis，當然直接啃 v8 也是可以滴。

時間倉促，一些細節可能會有偏差，如果有錯歡迎斧正～
其他有問題的同學可以留言討論～

原創文章轉載請注明：

轉載自AlloyTeam：http://www.ecomenagepro.com/2020/12/15164/

分享到:

AlloyTeam

AlloyTeam

重學 HashTable

目錄

HashTable 原理

HashTable 問題與解決

v8 中的 HashTable

redis 中的 HashTable

HashTable 原理

HashTable 問題與解決

開放尋址法

鏈表法

v8 中的 HashTable

v8 中的開放尋址法

v8 中的鏈表法

redis 中的 HashTable

總結

發表評論