Linux 核心的 hash table 實作

--- 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`: ```c 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 | {prev | <n>next}", group = list]; node_2[label = "<m>dll_node_2 | {prev | <n>next}", group = list]; node_3[label = "<m>dll_node_3 | {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 | {pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_2 | {pprev | <n>next}", group = list]; node_3[label = "<m>hlist_node_3 | {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; // Step 1 struct hlist_node **pprev = n->pprev; // Step 2 // Since there is always a pointer which points to node n, // no special case is needed to deal with. *pprev = next; // Step 3 if (next) next->pprev = pprev; // Step 4 } ``` 跟典型雙向鏈結串列的實作做比較，由於該實作的 `prev` 指標必須指向 `struct dll_node` 型別，導致第一個節點會出現指向 `NULL` 的狀況；而將其替換成指標的指標後，便可順利消除這個特例。以下圖解逐行探討上述 `hlist_delete_node` 實作 (對應到 Linux 核心的 `__hlist_del` 程式碼)。 - [ ] Step 1 `next` 指向 `entry->next` (亦即 `entry_next`) ```graphviz digraph hash_list { node [shape=record]; rankdir=LR; table [label = "<f0>ht[0]|<f1>ht[1]|<f2>...|<fn>ht[size - 1]"] hash_key1 [label = "<name>entry|{<pp>pprev|<n>next}"] hash_key2 [label = "<name>entry_next|{<pp>pprev|<n>next}"] null [shape=plaintext label="NULL"] table:f1->first first->hash_key1:name hash_key1:pp->first hash_key1:n->hash_key2:name hash_key2:pp->hash_key1:n hash_key2:n->null next->hash_key2:s[color=red] } ``` - [ ] Step 2 `pprev` 指向 `entry->pprev` (亦即 `&ht[1]->first`) ```graphviz digraph hash_list { node [shape=record]; rankdir=LR; table [label = "<f0>ht[0]|<f1>ht[1]|<f2>...|<fn>ht[size - 1]"] hash_key1 [label = "<name>entry|{<pp>pprev|<n>next}"] hash_key2 [label = "<name>entry_next|{<pp>pprev|<n>next}"] null [shape=plaintext label="NULL"] table:f1->first first->hash_key1:name hash_key1:pp->first hash_key1:n->hash_key2:name hash_key2:pp->hash_key1 hash_key2:n->null next->hash_key2:s[color=red] pprev->first:s[color=red] } ``` - [ ] Step 3 `*pprev` (即 `&ht[1]->first`) 指向「 `next` 指向的 `entry_next` 」 ```graphviz digraph hash_list { node [shape=record]; rankdir=LR; table [label = "<f0>ht[0]|<f1>ht[1]|<f2>...|<fn>ht[size - 1]"] hash_key1 [label = "<name>entry|{<pp>pprev|<n>next}"] hash_key2 [label = "<name>entry_next|{<pp>pprev|<next>next}"] null [shape=plaintext label="NULL"] table:f1->first first->hash_key2:name[color=red] hash_key2:pp->hash_key1:n hash_key2:n->null next->hash_key2:s[color=red] pprev->first:s[color=red] } ``` - [ ] Step 4 當 `next` 指向的位址不為 `NULL` 則 `next->pprev` 指向 `entry_next->pprev` ```graphviz digraph hash_list { node [shape=record]; rankdir=LR; table [label = "<f0>ht[0]|<f1>ht[1]|<f2>...|<fn>ht[size - 1]"] hash_key1 [label = "<name>entry|{<pp>pprev|<n>next}"] hash_key2 [label = "<name>entry_next|{<pp>pprev|<next>next}"] null [shape=plaintext label="NULL"] table:f1->first first->hash_key2:name[color=red] hash_key2:pp->hash_key1:n[color=none] hash_key2:pp->first[color=red] hash_key2:n->null next->hash_key2:s[color=red] pprev->first:s[color=red] } ``` 至此，我們理解到，`hlist` (即 hash list) 是針對雜湊表特製的鏈結串列，儘管尋常的雙向鏈結串列亦可實作雜湊表，但由於後者開頭和結尾需要各用 2 個指標，當 bucket 很大時，會增加記憶體開銷。相較於 `list_head` 的兩個指標，`hlist_head` 僅需要保存一個指標，`hlist_node` 的 `next` 指向下個節點，但 `pprev`（指標的指標) 並不指向上個節點，而是指向上個節點的 `next` 指標，這樣設計的好處是，當要刪除的節點是首個節點，即可藉由 `*pprev = next` 直接修改指標的指向。這時，對照看 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/v6.13/include/linux/list.h#L924-L929) 的註解: ```c /* * Double linked lists with a single pointer list head. * Mostly useful for hash tables where the two pointer list head is * too wasteful. * You lose the ability to access the tail in O(1). */ ``` 微言大義，Linux 核心開發者關注記憶體存取的效率。延伸閱讀: * [核心基礎設施: `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`，步驟如下: | Strategy | Example | | :------------------------------- | :-------- | | 0. Key: $K$, size of Table: $m=2^p$ | 0. K=21, m=8=$2^p$, p=3 | | 1. Choose constant $A$, where $0 \lt A \lt 1$ | 1. Choose $A=\frac{13}{32}$ | | 2. Multiply $K$ by $A$, get $KA$ | 2. $KA=21\times\frac{13}{32}=\frac{273}{32}=8+\frac{17}{32}$ | | 3. Extract the fractional part of $KA$, $f=KA-\lfloor KA \rfloor$ | 3. $f=\frac{17}{32}$ | | 4. Multiply $f$ by $m$, get $mf$ | 4. $mf=8\times\frac{17}{32}=\frac{17}{4}=4+\frac{1}{4}$ | | 5. h(Key)=$\lfloor mf \rfloor=\lfloor m(KA - \lfloor KA \rfloor)\rfloor$ | 5. h(21)=$\lfloor mf \rfloor = 4$ | key 乘上 constant A $\to$ 取小數點部分 $\to$ 再乘上 m $\to$ 再取整數部分的一系列步驟讓雜湊函數得以儘量把更多的 key 中的 bit 納入考慮而增加隨機性。 (原因可見 [Hash Table 簡介](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 的方式，這是由於上述的 function 與 $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 ![](https://hackmd.io/_uploads/HJqiOClCi.png) 文藝復興時期，黃金分割 ([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 相當分散, 意即碰撞很少。 ![](https://hackmd.io/_uploads/H1f3Yax0i.png) ### 比較 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)` 計算出的值 ![](https://hackmd.io/_uploads/H15TYpxRi.png =50%x)![](https://hackmd.io/_uploads/ByS15aeRj.png =50%x) ![](https://hackmd.io/_uploads/H1bZqpgAs.png =50%x)![](https://hackmd.io/_uploads/S1-M96xAj.png =50%x) 由實驗結果圖可發現, 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 分割的點)。 ![](https://hackmd.io/_uploads/SkU0fmW0o.png) 而現實生活上的 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 ![](https://hackmd.io/_uploads/r1SZjagCi.png) ![](https://hackmd.io/_uploads/HJ-Gsag0i.png) 實際的雜湊函數 (以 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)： ![](https://hackmd.io/_uploads/rJW4iaeRs.png) ![](https://hackmd.io/_uploads/B1WSs6gRs.png) ### 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)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.