一、關(guān)于斐波那契

斐波那契的歷史

斐波那契數(shù)列出現(xiàn)在印度數(shù)學(xué)中，與梵文韻律有關(guān)。在梵語詩(shī)歌傳統(tǒng)中，人們對(duì)列舉所有持續(xù)時(shí)間為 2 單位的長(zhǎng) (L) 音節(jié)與 1 單位持續(xù)時(shí)間的短 (S) 音節(jié)并列的模式很感興趣。用給定的總持續(xù)時(shí)間計(jì)算連續(xù) L 和 S 的不同模式會(huì)產(chǎn)生斐波那契數(shù)：持續(xù)時(shí)間m單位的模式數(shù)量是F(m + 1)。

斐波那契數(shù)列可以由遞歸關(guān)系定義

F0 = 0，F(xiàn)1 = 1，F(xiàn)n = Fn-1 + Fn-2

• 從 F2 開始任意一位都是前兩位之和。
• 從 F2 開始任意一位與前一位相比的比值，都無限趨近于 (√5 - 1)/2 = 0.618 因此基于黃金分割的計(jì)算應(yīng)用，也被稱為斐波那契應(yīng)用。

那這個(gè)就是斐波那契的基本定義和特性，并且基于這樣的特性在計(jì)算機(jī)科學(xué)中，斐波那契常用于；偽隨機(jī)數(shù)生成、AVL二叉樹、最大公約數(shù)、合并排序算法等。

而大部分程序員???????包括小傅哥最開始意識(shí)到斐波那契的應(yīng)用則來自于，Java 源碼 ThreadLocal 中 HASH_INCREMENT = 0x61c88647? 這樣一個(gè)常量的定義。因?yàn)檫@用作數(shù)據(jù)散列的特殊值 0x61c88647? 就是基于黃金分割點(diǎn)計(jì)算得來的，公式： (1L << 32) - (long) ((1L << 32) * (Math.sqrt(5) - 1))/2 。

那么既然 ThreadLocal 是基于斐波那契散列計(jì)算的下標(biāo)索引，那為啥數(shù)據(jù)庫(kù)路由算法不能使用同樣的方式計(jì)算散列索引呢？因?yàn)橥ㄟ^驗(yàn)證可以得知，斐波那契散列并不滿足嚴(yán)格的雪崩標(biāo)準(zhǔn)（SAC）。接下來小傅哥就帶著大家一起來使用數(shù)據(jù)驗(yàn)證下。

二、斐波那契計(jì)算

斐波那契數(shù)列可以通過循環(huán)、遞歸以及封閉式表達(dá)式（比奈公式） 的方式進(jìn)行計(jì)算。讀者可在單元測(cè)試中驗(yàn)證：https://github.com/fuzhengwei/java-algorithms

1. 循環(huán)計(jì)算

public double fibonacci(int{
    double currentVal = 1;
    double previousVal = 0;
    if (n == 1) return 1;
    int iterationsCounter = n - 1;
    while (iterationsCounter > 0) {
        currentVal += previousVal;
        previousVal = currentVal - previousVal;
        iterationsCounter -= 1;
    }
    return currentVal;
}

2. 遞歸計(jì)算

public int fibonacciRecursion(int{
    if (n == 1 || n == 2) {
        return 1;
    } else {
        return (fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2));
    }
}

3. 比奈公式

public double fibonacciClosedForm(long{
    int maxPosition = 75;
    if (position < 1 || position > maxPosition) {
        throw new RuntimeException("Can't handle position smaller than 1 or greater than 75");
    }
    double sqrt = Math.sqrt(5);
    double phi = (1 + sqrt) / 2;
    return Math.floor((Math.pow(phi, position)) / sqrt + 0.5);
}

封閉式表達(dá)式：與由具有常數(shù)系數(shù)的線性遞歸定義的每個(gè)序列一樣，斐波那契數(shù)具有封閉形式的表達(dá)式。它被稱為比奈公式，以法國(guó)數(shù)學(xué)家雅克·菲利普·瑪麗·比內(nèi)命名，盡管亞伯拉罕·德·莫弗和丹尼爾·伯努利已經(jīng)知道它。

三、散列函數(shù)分類

散列函數(shù)（英語：Hash function）又稱散列算法、哈希函數(shù)，是一種將任意大小的數(shù)據(jù)映射到固定大小值的計(jì)算方式。散列函數(shù)計(jì)算結(jié)果被稱為散列值、散列碼，也就是對(duì)應(yīng)的 HashMap 中哈希桶的索引以及數(shù)據(jù)庫(kù)中庫(kù)表的路由信息。

例如在 Java 中對(duì)數(shù)據(jù)的散列算法：HashMap 用到的是一次擾動(dòng)函數(shù)下的哈希散列、ThreadLocal 用到的斐波那契散列。而通常數(shù)據(jù)庫(kù)路由組件用到的是整數(shù)模除法散列，這也是實(shí)踐中最簡(jiǎn)單和最常用的方法之一。

接下來就給大家介紹這幾種常用的散列算法，其他更多散列可以參考 HashFunction

1. 除法散列

在用來設(shè)計(jì)散列函數(shù)的除法散列法中，通過取 K 除以 M 的余數(shù)，將關(guān)鍵字 K 映射到 M 個(gè)槽中的某一個(gè)位置上，即散列函數(shù)為：h(K) = K mod M 表格大小通常是 2 的冪。

另外除法散列的一個(gè)顯著缺點(diǎn)是除法在大多數(shù)現(xiàn)代架構(gòu)（包括 x86）上都是微編程的，并且可能比乘法慢 10 倍。

2. 乘法散列

乘法散列法整體包含兩步：

• 用關(guān)鍵字k乘上常數(shù)A(0<A<1)，并去除kA的小數(shù)部分
• 用m乘以這個(gè)值，再取結(jié)果的底floor?公式：h(K)=Math.floor[m(aK mod 1)]

步驟：

• 假設(shè)某計(jì)算機(jī)的字長(zhǎng)為 ww 位，而 kk 正好可容于一個(gè)字中(k<2wk<2w)
• 現(xiàn)在選取范圍[0，2w]?內(nèi)的任意數(shù)值 ss，k×sk×s 即可用R1·2w+R0R1·2w+R0來表示
• 因此(k·A)mod1=k·s/2w(k·A)mod1=k·s/2w?就是將k×sk×s整體向右平移 ww 位，此時(shí)R0R0即為小數(shù)部分
• 再乘以 2m2m 相當(dāng)于左移 mm 位，散列值 h(k)h(k) 為 R0R0 的前 m 位。

乘法散列只需要單個(gè)整數(shù)乘法和右移，使其成為計(jì)算速度最快的哈希函數(shù)之一。但乘法散列可能會(huì)在變更計(jì)算因子后，較高值的輸入位不會(huì)影響較低值的輸出位，問題體現(xiàn)在元素分散不均，不滿足嚴(yán)格的雪崩標(biāo)準(zhǔn)。所以通常在會(huì)進(jìn)行異或操作

乘法散列容易受到導(dǎo)致擴(kuò)散不良的“常見錯(cuò)誤”的影響——較高值的輸入位不會(huì)影響較低值的輸出位。在乘法步驟對(duì)此進(jìn)行校正之前，輸入上的變換將保留的最高位的跨度向下移動(dòng)，并將它們異或或加到鍵上。所以在輸入上的變換將保留的最高位的跨度向下移動(dòng)，并將它們異或操作或者加到鍵上。例如 HashMap 的擾動(dòng)函數(shù)。

3. 斐波那契散列

其實(shí)斐波那契散列是一種特殊形式的乘法散列，只不過它的乘法因子選擇的是一個(gè)黃金分割比例值，所以叫做斐波那契散列。

斐波那契散列的特性在于將“大數(shù)映射到小數(shù)”的計(jì)算結(jié)果在表空間上是均勻分布的，且計(jì)算滿足乘法散列效率高。那為什么并不能使用它作為數(shù)據(jù)庫(kù)路由算法呢？

四、雪崩標(biāo)準(zhǔn)測(cè)試

在數(shù)據(jù)庫(kù)路由實(shí)現(xiàn)方面，通常我們都是使用整數(shù)模除法散列求模的方式進(jìn)行元素的索引計(jì)算。那既然乘法散列效率高，斐波那契散列分散均勻，為什么不使用這樣的方式處理數(shù)據(jù)庫(kù)路由算法呢？

在檢索的資料中并沒有一個(gè)專門的文章來說明這一事項(xiàng)，這也倒置很多在學(xué)習(xí)過 HashMap、ThreadLocal 源碼的研發(fā)人員嘗試把這兩種源碼中的乘法散列算法搬到數(shù)據(jù)庫(kù)路由算法中使用。在保證每次擴(kuò)容數(shù)據(jù)庫(kù)表都是2的次冪的情況下，并沒有出現(xiàn)什么樣的問題。那么對(duì)于這樣情況下，是否隱藏著什么潛在的風(fēng)險(xiǎn)呢？

那么為了證實(shí)斐波那契散列是否可以用在數(shù)據(jù)庫(kù)路由散列算法中，我們可以嘗試使用嚴(yán)格雪崩標(biāo)準(zhǔn)(SAC)進(jìn)行驗(yàn)證測(cè)試。

那么什么是嚴(yán)格雪崩標(biāo)準(zhǔn)( SAC )  ，在密碼學(xué)中，雪崩效應(yīng)是密碼算法的理想屬性，通常是分組密碼和密碼散列函數(shù)，其中如果輸入發(fā)生輕微變化（例如，翻轉(zhuǎn)單個(gè)位），輸出會(huì)發(fā)生顯著變化（例如，50%輸出位翻轉(zhuǎn)）

SAC 建立在完整性和雪崩的概念之上，由 Webster 和 Tavares 于 1985 年引入。SAC 的高階概括涉及多個(gè)輸入位。滿足最高階 SAC 的最大非線性函數(shù)，也稱為“完全非線性”函數(shù)。

簡(jiǎn)單來說，當(dāng)我們對(duì)數(shù)據(jù)庫(kù)從8庫(kù)32表擴(kuò)容到16庫(kù)32表的時(shí)候，每一個(gè)表中的數(shù)據(jù)總量都應(yīng)該以50%的數(shù)量進(jìn)行減少。這樣才是合理的。

好，那么接下來我們就來做下雪崩測(cè)試；

• 準(zhǔn)備10萬個(gè)單詞用作樣本數(shù)據(jù)。
• 對(duì)比測(cè)試除法散列、乘法散列、斐波那契散列。
• 基于條件1、2，對(duì)數(shù)據(jù)通過不同的散列算法分兩次路由到8庫(kù)32表和16庫(kù)32表中，驗(yàn)證每個(gè)區(qū)間內(nèi)數(shù)據(jù)的變化數(shù)量，是否在50%左右。
• 準(zhǔn)備一個(gè) excel 表，來做數(shù)據(jù)的統(tǒng)計(jì)計(jì)算。

測(cè)試代碼

public Map<Integer, Map<Integer, Integer>> hashFunction(int dbCount, int tbCount, Long hashIncrementVal, int hashType) {
    int size = dbCount * tbCount;
    System.out.print("庫(kù)數(shù)：" + dbCount + " 表數(shù)：" + tbCount + " 總值：" + size + " 冪值：" + Math.log(size) / Math.log(2));
  
    int HASH_INCREMENT = (int) ((null == hashIncrementVal ? size : hashIncrementVal) * (Math.sqrt(5) - 1) / 2);
    System.out.print(" 黃金分割：" + HASH_INCREMENT + "/" + size + " = " + (double) HASH_INCREMENT / size);
  
    Map<Integer, Map<Integer, Integer>> map = new ConcurrentHashMap<>();
    Set<String> words = FileUtil.readWordList("/Users/fuzhengwei/1024/github/java-algorithms/logic/src/main/java/math/fibonacci/103976個(gè)英語單詞庫(kù).txt");
    System.out.println(" 單詞總數(shù)：" + words.size() + "\r\n");
  
    for (String word : words) {
        int idx = 0;
        switch (hashType) {
            // 散列：斐波那契散列  int idx = (size - 1) & (word.hashCode() * HASH_INCREMENT + HASH_INCREMENT);
            case 0:
                idx = (word.hashCode() * HASH_INCREMENT) & (size - 1);
                break;
            // 散列：哈希散列 + 擾動(dòng)函數(shù)
            case 1:
                idx = (size - 1) & (word.hashCode() ^ (word.hashCode() >>> 16));
                break;
            // 散列：哈希散列
            case 2:
                idx = (size - 1) & (word.hashCode()/* ^ (word.hashCode() >>> 16)*/);
                break;
            // 散列：整數(shù)求模
            case 3:
                idx = Math.abs(word.hashCode()) % size;
                break;
        }
      
        // 計(jì)算路由索引
        int dbIdx = idx / tbCount + 1;
        int tbIdx = idx - tbCount * (dbIdx - 1);
      
        // 保存路由結(jié)果
        if (map.containsKey(dbIdx)) {
            Map<Integer, Integer> dbCountMap = map.get(dbIdx);
            if (dbCountMap.containsKey(tbIdx)) {
                dbCountMap.put(tbIdx, dbCountMap.get(tbIdx) + 1);
            } else {
                dbCountMap.put(tbIdx, 1);
            }
        } else {
            Map<Integer, Integer> dbCountMap = new HashMap<>();
            dbCountMap.put(tbIdx, 1);
            map.put(dbIdx, dbCountMap);
        }
    }
    return map;
}

整個(gè)方法的目的在于得出不同的哈希算法，對(duì)10萬個(gè)單詞散列到指定的分庫(kù)分表中，所體現(xiàn)的結(jié)果。

1. 斐波那契散列

1.1 最小黃金分割

斐波那契散列也是乘法散列的一種體現(xiàn)形式，只不過它選擇了一個(gè)黃金分割點(diǎn)作為乘積因子。例如 ThreadLocal 中的 0x61c88647。但如果說我們只是按照一個(gè)指定范圍長(zhǎng)度內(nèi)做黃金分割計(jì)算，并拿這個(gè)結(jié)果當(dāng)成乘法散列的因子，那么10萬單詞將不會(huì)均勻的散列到8個(gè)庫(kù)，32張表內(nèi)。如圖：

@Test
public void test_hashFunction_0_hash_null(){
    Map<Integer, Map<Integer, Integer>> map = fibonacci.hashFunction(8, 32, null, 0);
    Set<Integer> keys = map.keySet();
    for (Integer key : keys) {
        Collection<Integer> values = map.get(key).values();
        for (Integer v : values) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

庫(kù)數(shù)：8 表數(shù)：32 總值：256 冪值：8.0 黃金分割：2147483647/256 = 8388607.99609375 單詞總數(shù)：103976

如果你的斐波那契散列值是根據(jù)庫(kù)表的值進(jìn)行黃金切割的，那么在最初的庫(kù)表范圍較小的階段，將有部分區(qū)域無法使用。這是因?yàn)榈玫降狞S金分割點(diǎn)的二進(jìn)制值沒法覆蓋整個(gè)區(qū)域，也就做不到合適的乘法散列計(jì)算。參考：https://bugstack.cn/md/algorithm/logic/math/2022-10-30-bits.html - 《程序員數(shù)學(xué)：位運(yùn)算》

1.2 最小黃金分割

基于最小黃金分割的計(jì)算，是沒法做到均勻散列的。所以你看到的 ThreadLocal 默認(rèn)就給你一個(gè) 0x61c88647 而不是隨著擴(kuò)容長(zhǎng)度實(shí)時(shí)計(jì)算的切割值。好那么我們接下來也使用這個(gè)值來做計(jì)算，看看8庫(kù)到16庫(kù)后，數(shù)據(jù)的雪崩結(jié)果。

@Test
public void test_hashFunction_0(){
    Map<Integer, Map<Integer, Integer>> map = fibonacci.hashFunction(8, 32, 1L << 32, 0);
    Set<Integer> keys = map.keySet();
    for (Integer key : keys) {
        Collection<Integer> values = map.get(key).values();
        for (Integer v : values) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

分別測(cè)試 dbCount = 8、dbCount = 16

庫(kù)數(shù)：8 表數(shù)：32 總值：512 冪值：9.0 黃金分割：2147483647/512 = 4194303.998046875 單詞總數(shù)：103976

庫(kù)數(shù)：16 表數(shù)：32 總值：512 冪值：9.0 黃金分割：2147483647/512 = 4194303.998046875 單詞總數(shù)：103976

從8庫(kù)擴(kuò)到16庫(kù)以后，滿足50%數(shù)據(jù)變化的，只有2庫(kù)2表和3庫(kù)20表。其他數(shù)據(jù)變化都不滿足嚴(yán)格的雪崩測(cè)試。

1.3 任意擴(kuò)容庫(kù)表

通常情況下做分庫(kù)分表會(huì)考慮到以后的擴(kuò)容操作，那如果說按照2的次冪擴(kuò)容第一次是8庫(kù)32表，之后是16庫(kù)32表，在之后32庫(kù)32表。那么這樣擴(kuò)容下去，其實(shí)是扛不住的。所以大多數(shù)時(shí)候希望是從8庫(kù)擴(kuò)到9庫(kù)，而不是一下翻倍。那我們來測(cè)試下9庫(kù)32表，斐波那契散列的分散效果。

    Map<Integer, Map<Integer, Integer>> map = fibonacci.hashFunction(9, 32, 1L << 32, 0);
    Set<Integer> keys = map.keySet();
    for (Integer key : keys) {
        Collection<Integer> values = map.get(key).values();
        for (Integer v : values) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

庫(kù)數(shù)：9 表數(shù)：32 總值：512 冪值：9.0 黃金分割：2147483647/512 = 4194303.998046875 單詞總數(shù)：103976

因?yàn)?庫(kù)不滿足2的次冪，也就沒法直接乘法散列。所以相當(dāng)于斐波那契散列失效了。這如果是線上的生產(chǎn)環(huán)境，將發(fā)生災(zāi)難性的事故。

2. 整數(shù)求模散列

2.1 基礎(chǔ)散列計(jì)算

整數(shù)求模以數(shù)據(jù)庫(kù)表總數(shù)為除數(shù)，與哈希值的絕對(duì)值進(jìn)行除法散列計(jì)算。一般在數(shù)據(jù)庫(kù)路由中非常常用。另外如果根據(jù)用戶ID做散列路由，但由于ID長(zhǎng)度波動(dòng)范圍較大，則可以按照指定長(zhǎng)度統(tǒng)一切割后使用。

@Test
public void test_hashFunction_3(){
    Map<Integer, Map<Integer, Integer>> map = fibonacci.hashFunction(8, 32, null, 3);
    Set<Integer> keys = map.keySet();
    for (Integer key : keys) {
        Collection<Integer> values = map.get(key).values();
        for (Integer v : values) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

分別測(cè)試 dbCount = 8、dbCount = 16

庫(kù)數(shù)：8 表數(shù)：32 總值：512 冪值：9.0 黃金分割：2147483647/512 = 4194303.998046875 單詞總數(shù)：103976

庫(kù)數(shù)：16 表數(shù)：32 總值：512 冪值：9.0 黃金分割：2147483647/512 = 4194303.998046875 單詞總數(shù)：103976

在使用除法散列方式后，滿足50%數(shù)據(jù)變化的有5個(gè)表。看著并不多，但這相當(dāng)于是斐波那契散列下的3倍。同時(shí)其他表數(shù)據(jù)接近50%的也要大于斐波那契散列。

2.2 任意擴(kuò)容計(jì)算

接下來我們?nèi)我鈴?庫(kù)擴(kuò)容到9庫(kù)，看看數(shù)據(jù)的變化。

@Test
public void test_hashFunction_3(){
    Map<Integer, Map<Integer, Integer>> map = fibonacci.hashFunction(9, 32, null, 3);
    Set<Integer> keys = map.keySet();
    for (Integer key : keys) {
        Collection<Integer> values = map.get(key).values();
        for (Integer v : values) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

庫(kù)數(shù)：9 表數(shù)：32 總值：512 冪值：9.0 黃金分割：2147483647/512 = 4194303.998046875 單詞總數(shù)：103976

103976 / (9 * 32) ≈ 361，那么也就說擴(kuò)容后的數(shù)據(jù)，基本在361范圍波動(dòng)，就滿足了均勻散列的目的。所以在數(shù)據(jù)庫(kù)散列算法中，除法散列是較靠譜且穩(wěn)定的。

五、常見面試題

• 散列算法有哪些種？
• HashMap、ThreadLocal、數(shù)據(jù)庫(kù)路由都是用了什么散列算法？
• 乘法散列為什么要用2的冪值作為每次的擴(kuò)容條件？
• 你有了解過0x61c88647 是怎么計(jì)算的嗎？
• 斐波那契散列的使用場(chǎng)景是什么？
• The Fibonacci Association：https://en.wikipedia.org/wiki/The_Fibonacci_Association
• 哈希函數(shù)：https://en.wikipedia.org/wiki/Hash_function
• 斐波那契數(shù)：https://en.wikipedia.org/wiki/Fibonacci_number#Mathematics
• 散列函數(shù)：https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8
• 雪崩效應(yīng)：https://en.wikipedia.org/wiki/Avalanche_effect
• Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo)：https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/斐波那契數(shù)：https://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratioC++ 中具有面向?qū)ο笤O(shè)計(jì)模式的數(shù)據(jù)結(jié)構(gòu)和算法：https://book.huihoo.com/data-structures-and-algorithms-with-object-oriented-design-patterns-in-c++/html/page214.html