Linux 核心的 hash table 實作

本頁由 Uduru0522, qwe661234, SmallHanley, hankluo6, jserv 貢獻

概況

Linux 核心如同其他複雜的資訊系統，也提供 hash table 的實作，但其原始程式碼中卻藏有間接指標 (可參見你所不知道的 C 語言: linked list 和非連續記憶體) 的巧妙和數學奧秘。

間接指標的應用

Linux 核心的 hash table 實作中，用以處理 hash 數值碰撞的 hlist_node:

struct hlist_node {
    struct hlist_node *next, **pprev;
};

示意圖如下：

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:

struct dll_node { 
    struct dll_node *next, *prev;
}

dll 是雙向鏈結串列的簡稱

於是資料結構會展現如下圖:

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():

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:

struct hlist_node { 
    struct hlist_node *next, **pprev;
}

則會形成以下的結構：

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()：

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)

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)

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 」

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

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 的註解:

/*
 * 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 核心開發者關注記憶體存取的效率。

雜湊函數

hash function 的功能是用來將 key 值轉換成對應的 index

若將 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。

雜湊函數考慮因素

計算所需的時間複雜度要低
希望雜湊運算的時間複雜度為 \(O(1)\)。
減少碰撞
碰撞 (collision) 是指不同的 key 對應到相同的 index，碰撞越少，則越接近 perfect function。
避免 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 contant \(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 簡介)

K: key value
A: a constant, 且 0 < A < 1
m: bucket 數量, 且 m = \(2^p\)

Linux 核心的雜湊函數

Linux 核心的 hash.h 中，雜湊函數的設計是使用上面所提到的 Multiplication Method，但上面提到的雜湊函數本是形如 \(h(K) = \lfloor m \times (KA - \lfloor KA \rfloor) \rfloor\)，但在 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 浮點數表示

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 個位元

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"]
}

最後做下高斯只留下整數部分

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)\) 個位元。

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 個位元

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 型態，因此只會留下整數部分。

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

#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 在數學上為 \(\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〉的第 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) 被視為最神聖的比例。達文奇在《繪畫論》一書指出:

「美感完全建立在各部分之間神聖比例的關係上，各特徵必須同時作用，才能產生使觀眾往往如醉如痴的和諧比例」

黃金分割在數學、美學、人體、藝術、自然等領域，啟發人們去認識世界和改造世界，因此 16 世紀威尼斯數學家 Luca Pacioli (有時也寫為 Paccioli 或 Paciolo) 將黃金分割稱為「神賜的比例」。

至於 A 為什麼使用 golden ratio，也就是 A = \(\dfrac{\sqrt{5} - 1}{2}\) = 0.6180339887…呢？該數值是由 Donald Knuth 建議，Hashing and Hash Tables 課程講義提出實驗結果如下圖，其中當 A = golden ratio 時, 此雜湊函數稱為 Fibonacci hashing，且 key 經此函數轉換得到的 index 相當分散, 意即碰撞很少。

比較 golden ratio 與非 golden ratio

以下挑選 4 個不同的數字作為 \(A \times 2^{32}\)，並紀錄對 key: 0 ~ 1500 做 hash_32(key value, 10) 的結果

0x61C88647
0x80000000
0x12345678
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 可發現一個巨集 GOLDEN_RATIO_PRIME，

/*
 * 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 後改成以下：

/*
 * 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

註解中的 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》(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 推導。)

{\(n \theta\)} 代表 \(n \theta\) 的小數部分。

之所以要取小數部分，原理是該分割問題可轉化為 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：

#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)：

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.