---
tags: LINUX KERNEL
---
# Linux 核心的 hash table 實作
> 本頁由 [Uduru0522](https://github.com/Uduru0522), [qwe661234](https://github.com/qwe661234), [SmallHanley](https://github.com/SmallHanley), [hankluo6](https://github.com/hankluo6), [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) 貢獻
## 概況
Linux 核心如同其他複雜的資訊系統，也提供 [hash table](https://en.wikipedia.org/wiki/Hash_table) 的實作，但其原始程式碼中卻藏有間接指標 (可參見[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)) 的巧妙和數學奧秘。
## 間接指標的應用
Linux 核心的 hash table 實作中，用以處理 hash 數值碰撞的 `hlist_node`:
```cpp
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
示意圖如下：
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 3"
}
map:ht1 -> hn1
hn1:next -> hn2
hn2:next -> null1
hn2:prev:s -> hn1:next:s
map:ht5 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
}
```
**其中 `pprev` 為何要宣告為==指標的指標==？**
以下探討針對典型雙向鏈結串列進行節點移去時，會產生的問題。
考慮我們使用典型的 doubly-linked list:
```c
struct dll_node {
struct dll_node *next, *prev;
}
```
> `dll` 是雙向鏈結串列的簡稱
於是資料結構會展現如下圖:
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>dll_node_1 | {<p>prev | <n>next}", group = list];
node_2[label = "<m>dll_node_2 | {<p>prev | <n>next}", group = list];
node_3[label = "<m>dll_node_3 | {<p>prev | <n>next}", group = list];
NULL_1, NULL_2[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head NULL_1}
list_head -> node_1:m;
node_1:p -> NULL_1
node_1:n -> node_2:m;
node_2:p -> node_1:m;
node_2:n -> node_3:m;
node_3:p -> node_2:m;
node_3:n -> NULL_2;
}
```
注意：
+ 除了末端，第一個節點的 `prev` 指標內容也是 `NULL`。
+ `prev` 及 `next` 皆指向相鄰的**節點本身**。
嘗試撰寫 `delete_node():`
```c
void dll_delete_node(struct list_head *l, struct dll_node *n)
{
struct dll_node *prev = n->prev,
*next = n->next;
if (next)
next->prev = prev;
// Delete and update where list_head points to,
// which requires the list_head to be passed in.
if (!prev) {
l->first = next;
} else {
prev->next = next;
}
}
```
可發現當我們要移除第一個節點時，必須做出額外的操作來更新 `list_head` 指向的節點，於是除了移除的目標之外，還必須傳入 `list_head`。
當我們用指標的指標改寫上述程式碼，將原本的 `struct dll_node *prev` 變更為 `struct dll_node **pprev`:
```c
struct hlist_node {
struct hlist_node *next, **pprev;
}
```
則會形成以下的結構：
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list];
node_3[label = "<m>hlist_node_3 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 -> node_2 -> node_3[
weight = 10, style = invis
]
list_head:n -> node_1:m;
node_1:p -> list_head:n;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> NULL;
}
```
注意：
+ 僅有末端指標內容是 `NULL`。
+ `next` 指向相鄰的**節點本身**，而 `pprev` 指向**指著自身節點的指標**。
則我們便可藉由下方程式碼來撰寫 `delete_node()`：
```c
void hlist_delete_node(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
// Since there is always a pointer which points to node n,
// no special case is needed to deal with.
*pprev = next;
if (next)
next->pprev = pprev;
}
```
跟典型雙向鏈結串列的實作做比較，由於該實作的 `prev` 指標必須指向 `struct dll_node` 型別，導致第一個節點會出現指向 `NULL` 的狀況；而將其替換成指標的指標後，便可順利消除這個特例。
至此，我們理解到，`hlist` (即 hash list) 是針對雜湊表特製的鏈結串列，儘管雙向鏈結串列亦可實作雜湊表，但由於後者開頭和結尾需要各用 2 個指標，當 bucket 很大時，會增加記憶體開銷。
相較於 `list_head` 的兩個指標，`hlist_head` 僅需要保存一個指標，`hlist_node` 的 `next` 指向下個節點，但 `pprev`（指標的指標) 並不指向上個節點，而是指向上個節點的 `next` 指標，這樣設計的好處是，當要刪除的節點是首個節點，即可藉由 `*pprev = next` 直接修改指標的指向。
延伸閱讀:
* [核心基礎設施: `hlist_head`/`hlist_node` 結構解析](http://linux.laoqinren.net/kernel/hlist/)
* [hlist 資料結構圖示說明](https://zhuanlan.zhihu.com/p/82375193)
## 雜湊函數
[hash function](https://en.wikipedia.org/wiki/Hash_function) 的功能是用來將 key 值轉換成對應的 index
:::info
若將 hash function 翻譯為「哈希函數」，看似是 hash (音標:[hæʃ]) 對應到相近發音的漢語，但後者實際更接近 harsh (音標: [hɑːrʃ])的讀法，且 harsh function (在嚴苛環境得以發揮的功能) 是自動化工程的描述，與電腦科學無關。要不保留原文，要不採取意譯「雜湊」
:::
### **Perfect function**
當所有的 key 經過雜湊函數轉換後，得到 index 都不一樣時，我們稱此雜湊函數為 **perfect function**。 **Perfect function** 可以做到完美的 1-to-1，也就是一組 key 對應到一組 index。若雜湊函數的時間複雜度是 $O(1)$，這樣我們僅僅只需要時間複雜度 $O(1)$ 的時間就可以查找到 hash table 中的資料。
但實際上 **perfect function** 很難做到，我們不知道 key value 的 range 有多大，所以不知道 bucket 的數量要多少才能滿足 1-to-1，若 hash table size 很大，但其中有很多空間都沒有使用到也會造成不必要的浪費。由於多個 key value 可能對應到同一個 index，所以一個 index 會對應到一個可以存數筆 data 的 bucket。
綜合以上，我們只能透過設計雜湊函數，使其盡可能接近 **perfect function**。
### 雜湊函數考慮因素
1. 計算所需的時間複雜度要低
希望雜湊運算的時間複雜度為 $O(1)$。
2. 減少碰撞
碰撞 (collision) 是指不同的 key 對應到相同的 index，碰撞越少，則越接近 **perfect function**。
3. 避免 Clustering 現象
Clustering 是指某些 bucket 存放很多筆資料，而某些 bucket 存放的很少，應該盡量讓 bucket 存放的資料筆數平衡，否則容易造成 `Overflow`，這樣會造成存取效率變差。
`Overflow` 是指 bucket 的記憶體空間滿了，需要刪除一筆資料才能存入新的資料，`Overflow` 發生時，決定哪一筆資料要被刪除也是重要的議題。
### 常見雜湊函數作法
- [ ] Division method
h(k) = $k \% N$
以 mod 運算後的餘數作為 index，由於 key 值得範圍無法得知，所以如何挑選適合的 $N$ 很關鍵。
- [ ] Mid-square
h(k) = $bits_{i,i + r - 1}(k^2)$
將 k 值 (即 `key`) 平方後，取其第 $i$ ~ $i + r - 1$ 位元，得到的數字範圍會是 0 ~ $2^r - 1$，所以 bucket 數量為 $2^r$ 即可。
例如:
key = 6，$6^2 = 36$，假設 i = 2, r = 3，所以取其第 2 ~ 4 位元，又 $36_{10}$ = $100100_2$，取第 2 ~ 4 位元得 $010_2$，所以 index = $2_{10}$。
- [ ] Folding addition
先將 key 切割成片段後相加，亦可以對相加後的結果做其他運算。
例如:
key = 3823749374，將此值每三個數字分成一段
```
382 | 374 | 937 | 4
```
再將這四個數字相加
index = 382 + 374 + 937 + 4 = 1697
可以進一步對 1697 進行其他運算例如: mod, 反轉...
- [ ] Multiplication Method
由於大部分的情況下，我們不知道 key 的範圍以及分佈情形，這樣的情形適用 `Multiplication Method`，步驟如下:
key 乘上 constant A $\to$ 取小數點部分 $\to$ 再乘上 m $\to$ 再取整數部分的一系列步驟讓雜湊函數得以儘量把更多的 key 中的 bit 納入考慮而增加隨機性。 (原因可見 [Hash Table：Intro(簡介)](http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html#dm))
* K: key value
* A: a constant, 且 0 < A < 1
* m: bucket 數量, 且 m = $2^p$
## Linux 核心的雜湊函數
Linux 核心的 [hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 中，雜湊函數的設計是使用上面所提到的 Multiplication Method，但上面提到的雜湊函數本是形如 $h(K) = \lfloor m \times (KA - \lfloor KA \rfloor) \rfloor$，但在 [hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 中卻用到 bit-shifting 的方式，這是由於上述的 funciton 與 $h(K) = K \times 2^w \times A >> (w - p)$ 是等價的, 而且 bit-shifting 的效率較好, 所以以這種方式來實作。
* K: key value
* A: a constant, 且 0 < A < 1
* m: bucket 數量, 且 m = $2^p$
* $w$: 一個 word 有幾個 bit
### 為何這二個函數等價？
假設一個 word 是 8 個 bit，將 KA 的結果以 8 bit 整數配上 8 bit 浮點數表示
```graphviz
graph structs {
node[shape=record];
struct1 [label="0|0|0|0|0|1|0|1"]
node[shape=point]
dot
node[shape=record];
struct2 [label="1|1|1|0|1|0|0|0"]
}
```
根據 $h(K) = \lfloor m * (KA - \lfloor KA \rfloor) \rfloor$，我們只需要 KA 的浮點數部分，也就是後面的 8 個位元，再假設 m 是 8 = $2^3$，再乘上 $m$，於是以上步驟等同於清除前 8 個位元再左移 3 個位元
```graphviz
graph structs {
node[shape=record];
struct1 [label="0|0|0|0|0|1|1|1"]
node[shape=point]
dot
node[shape=record];
struct2 [label="0|1|0|0|0|0|0|0"]
}
```
最後做下高斯只留下整數部分
```graphviz
graph structs {
node[shape=record];
struct1 [label="0|0|0|0|0|1|1|1"]
node[shape=point]
}
```
而這樣的操作等同於 KA 的結果先左移 8 個位元，這樣前面 8 個位元即為 KA 結果的浮點數部分，依照前面的操作，我們可知浮點數部分其實只要留下前 p 個位元，所以要右移 $(w - p)$ 個位元。
KA
```graphviz
graph structs {
node[shape=record];
struct1 [label="0|0|0|0|0|1|0|1"]
node[shape=point]
dot
node[shape=record];
struct2 [label="1|1|1|0|1|0|0|0"]
}
```
$K \times 2^w \times A$，乘上 $2^w$ 等同於左移 8 個位元
```graphviz
graph structs {
node[shape=record];
struct1 [label="1|1|1|0|1|0|0|0"]
node[shape=point]
dot
node[shape=record];
struct2 [label="0|0|0|0|0|0|0|0"]
}
```
接著右移 $(w - p)$，也就是 $8 - 3 = 5$ 個位元，因為在 Linux 實際用 `uint` 型態，因此只會留下整數部分。
```graphviz
graph structs {
node[shape=record];
struct1 [label="0|0|0|0|0|1|1|1"]
node[shape=point]
}
```
### Linux 原始程式碼
以下針對 32 位元的雜湊函數來說明。
> 64 位元的雜湊函數邏輯相同，只是 word size 為 64
> [include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h)
```c
#define GOLDEN_RATIO_32 0x61C88647
#ifndef HAVE_ARCH__HASH_32
#define __hash_32 __hash_32_generic
#endif
static inline u32 __hash_32_generic(u32 val)
{
return val * GOLDEN_RATIO_32;
}
static inline u32 hash_32(u32 val, unsigned int bits)
{
/* High bits are more random, so use them. */
return __hash_32(val) >> (32 - bits);
}
```
* `GOLDEN_RATIO_32`: $A \times 2^{32}$ 後的結果
* `__hash_32_generic` (u32 型態)
* val: key $K$
* 該函式計算 $K \times 2^w \times A$ 的結果
* `hash_32` (u32 型態)
* val: key $K$
* bits: 其實就是 p, $2^{bits}$ = bucket 數量
* 這個函式將 `__hash_32_generic(u32 val)` 算出的結果 $K \times 2^w \times A$ 右移 `(32 - p)` 個位元
[golden ratio](https://en.wikipedia.org/wiki/Golden_ratio) 在數學上為 $\varphi=(\sqrt{5}+1)/2\approx 1.618033989$，我們可計算出其倒數 $\varphi^{-1}= (\sqrt{5}-1)/2\approx 0.618033989$ 恰好是原本的小數部份。〈[Linux Kernel Hash Table Behavior: Analysis and Improvements](http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf)〉的第 5.1 節給出
> $(\sqrt{5} - 1 ) / 2 = 0.618033989$
$2654435761 / 4294967296 = 0.618033987$
這個 $4294967296$ 顯然是 32 位元無號數的最大值加 1 ，亦即 $2^{32}$ 。
這代表我們將輸入的 `val` 乘上 $\varphi^{-1}$ 幾乎等同於乘上 2654435761 並右移 32 ，然後我們需要左移 `bits` 個位元以充分利用 hash table 的空間。
因此, `val * GOLDEN_RATIO_32 >> (32 - bits)` $\equiv$ $K \times A \times 2^w >> (w - p)$
### GOLDEN_RATIO
文藝復興時期，黃金分割 ([golden ratio](https://en.wikipedia.org/wiki/Golden_ratio)) 被視為最神聖的比例。達文奇在 《[繪畫論](https://en.wikipedia.org/wiki/A_Treatise_on_Painting)》一書指出:
> 「美感完全建立在各部分之間神聖比例的關係上，各特徵必須同時作用，才能產生使觀眾往往如醉如痴的和諧比例」
黃金分割在數學、美學、人體、藝術、自然等領域，啟發人們去認識世界和改造世界，因此 16 世紀威尼斯數學家 Luca Pacioli (有時也寫為 Paccioli 或 Paciolo) 將黃金分割稱為「神賜的比例」。
至於 A 為什麼使用 [golden ratio](https://en.wikipedia.org/wiki/Golden_ratio)，也就是 A = $\dfrac{\sqrt{5} - 1}{2}$ = 0.6180339887...呢？該數值是由 [Donald Knuth](https://en.wikipedia.org/wiki/Donald_Knuth) 建議，[Hashing and Hash Tables 課程講義](http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter05.pdf) 提出實驗結果如下圖，其中當 A = [golden ratio](https://en.wikipedia.org/wiki/Golden_ratio) 時, 此雜湊函數稱為 Fibonacci hashing，且 key 經此函數轉換得到的 index 相當分散, 意即碰撞很少。
### 比較 golden ratio 與非 golden ratio
以下挑選 4 個不同的數字作為 $A \times 2^{32}$，並紀錄對 key: 0 ~ 1500 做 `hash_32(key value, 10)` 的結果
1. `0x61C88647`
2. `0x80000000`
3. `0x12345678`
4. `0x54061094`
圖的 x 軸是 key，y 軸是 `hash_32(key value, 10)` 計算出的值
由實驗個果圖可發現, golden ratio 作為 A 結果最均勻分散，另外結果也說明 A 值的選擇對於碰撞有很大的影響, 例如 $A \times 2^{32}$ = 0x80000000 時，0 ~ 1500 只有 2 種可能，不僅每兩個數值就發生一次碰撞，由於資料只會存放於兩個 bucket，因此 Cluster 程度相當嚴重。
在 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 可發現一個巨集 `GOLDEN_RATIO_PRIME`，
```c
/*
* Knuth recommends primes in approximately golden ratio to the maximum
* integer representable by a machine word for multiplicative hashing.
* Chuck Lever verified the effectiveness of this technique:
* http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
*
* These primes are chosen to be bit-sparse, that is operations on
* them can use shifts and additions instead of multiplications for
* machines where multiplications are slow.
*/
#if BITS_PER_LONG == 32
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME 0x9e370001UL
#elif BITS_PER_LONG == 64
/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
#else
#error Define GOLDEN_RATIO_PRIME for your wordsize.
#endif
```
在 [commit 689de1d](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/include/linux/hash.h?id=689de1d6ca95b3b5bd8ee446863bf81a4883ea25) 後改成以下：
```c
/*
* This hash multiplies the input by a large odd number and takes the
* high bits. Since multiplication propagates changes to the most
* significant end only, it is essential that the high bits of the
* product be used for the hash value.
*
* Chuck Lever verified the effectiveness of this technique:
* http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
*
* Although a random odd number will do, it turns out that the golden
* ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
* properties. (See Knuth vol 3, section 6.4, exercise 9.)
*
* These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2,
* which is very slightly easier to multiply by and makes no
* difference to the hash distribution.
*/
#define GOLDEN_RATIO_32 0x61C88647
#define GOLDEN_RATIO_64 0x61C8864680B583EBull
```
:::info
註解中的 `phi = (sqrt(5)-1)/2` 指的是 $\phi^{-1}$，為 golden ratio 的倒數。
:::
* $\text{0x61C88647}=\text{1640531527}\approx2^{32}\times\phi^{-2}=2^{32}\times\frac{3-\sqrt{5}}{2}$
* $\text{0x61C8864680B583EB}=\text{7046029254386353131}\approx2^{64}\times\phi^{-2}=2^{64}\times\frac{3-\sqrt{5}}{2}$
任意數乘上這兩個數再取其高位元，可呈現好的數值分布。在連續的數值中，利用這種 Fibonacci Hashing 方法可將 hash 後對應的值分散到其他 hash value 的值之間 (將最大區間以 golden ratio 分割的點)。
而現實生活上的 keys 值分布常常會有某種數值分布，類似 $\{K, K+d, K+2d, ..., K+td\}$，例如字串集合 $\{"PART1", "PART2", "PART3"\}$，這種情況利用此種 hash function 的行為就如同計算 $h(0), h(1), h(2)$，便能將 key 值映射到沒有使用過的 value，減少碰撞的機率。
假設 $\theta$ 為一無理數，要將 $\{\theta, 2\theta, 3\theta, ..., n\theta\}$ 的小數部分放到 $[0, 1]$ 之間，則會發現 $(n+1)\theta$ 放置的位置會在由前面的點分割成的線段中最長的線段，而當 $\theta$ 過大或過小時 (接近 0 或 1)，產生的分布區間便會由小而大，並不是均勻分布。
其中討論到有關 `GOLDEN_RATIO_PRIME` 的實作考量，出自於《[The Art of Computer Programming](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)》(Knuth vol 3, section 6.4, exercise 9) 這本書，證明能產生較好的分布的數值為 $\phi^{-1}$ 及 $\phi^{-2}$以下取自這本書的片段。
**Theorem S.** Let $\theta$ be any irrational number. When the points {$\theta$}, {$2\theta$}, ..., {$n\theta$} are placed in the line segment [0 ... 1], then $n + 1$ line segments formed have at most three different lengths. Moreover, the next point {$(n + 1)\theta$} will fall in one of the largest existing segments.
(用 Three-gap theorem 推導。)
:::info
{$n \theta$} 代表 $n \theta$ 的小數部分。
:::
之所以要取小數部分，原理是該分割問題可轉化為 [Three-gap theorem](https://en.wikipedia.org/wiki/Three-gap_theorem)。line segment [0 … 1] 對應到 Three-gap theorem 中周長為 1 的圓，$n \theta$ 的整數部分相當於繞了圓多少圈 (即在 line segment 循環多少次)，而小數部分相當於新的點坐落於圓上的哪一個位置 (即 line segment 中新分割點的位置)。
有關 **Theorem S** 的證明在 exercise 8
實際的雜湊函數 (以 32 位元為例) 定義於 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h#L57-L69)：
```c
#ifndef HAVE_ARCH__HASH_32
#define __hash_32 __hash_32_generic
#endif
static inline u32 __hash_32_generic(u32 val)
{
return val * GOLDEN_RATIO_32;
}
static inline u32 hash_32(u32 val, unsigned int bits)
{
/* High bits are more random, so use them. */
return __hash_32(val) >> (32 - bits);
}
```
上述程式碼以 32 位元無號整數來表達介於 0 到 1 之間的浮點數，其中 `__hash_32_generic` 將欲進行 hash 的數值 `val` 乘上 `GOLDEN_RATIO_32` ，而 `hash_32` 則取最高的 `bits` 個位元。對應上述 Fibonacci Hashing，`val` 對應到 $n$，`GOLDEN_RATIO_32` 為 $\phi^{-1}$ 以 32 位元無號整數表示，兩者相乘，因為會產生溢位 (一次溢位相當於 Three-gap theorem 中繞了圓一圈)，相乘的結果為 {$n \phi^{-1}$} 以 32 位元無號整數表示，取其高位元，則相當於取小數前幾位數。
對比前後版本的 `GOLDEN_RATIO_PRIME` 實作，新的實作可讓雜湊函數結果的分佈更為均勻。以下分別測試 0 到 1000、10000 映射到 hash table 不同 locations 的次數，hash table 的大小為 1024 (10 bits)：
### Reference:
* [Hashing 基礎介紹](https://meteorv.dev/Data-Structure/hashing/)
* [Hash Table 簡介](http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html)
* [Hash Functions](https://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html)
* [Data Structures: Hashing II](http://www.cs.nthu.edu.tw/~wkhon/ds/ds12/lecture/lecture18.pdf)
* [Hashing and Hash Tables](http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter05.pdf)
Sign in with Wallet
Connect another wallet