Horner法則，MurMurHash

項目github位址：bitcarmanlee easy-algorithm-interview-and-practice

歡迎大家star，留言，一起學習進步

1.Horner法則

假設有一個n次多項式需要計算。

f ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 f(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 f(x)=an​xn+an−1​xn−1+⋯+a1​x+a0​

如果直接進行計算，需要 n ( n + 1 ) 2 \frac{n(n+1)}{2} 2n(n+1)​次乘法與 n n n次加法。而乘法的代價是比較大的，是以效率會比較低。

将上面的多項式改寫一下

f ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 = ( a n x n − 1 + a n − 1 x n − 2 + ⋯ + a 2 x + a 1 ) x + a 0 = ( ( ( a n x + a n − 1 ) x + a n − 2 ) x + ⋯ + a 1 ) x + a 0 \begin{aligned} f(x) & = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 \\ & = (a_nx^{n-1} + a_{n-1}x^{n-2} + \cdots + a_2x + a_1)x + a_0 \\ & = (((a_nx + a_{n-1})x + a_{n-2})x + \cdots + a_1)x + a_0\\ \end{aligned} f(x)​=an​xn+an−1​xn−1+⋯+a1​x+a0​=(an​xn−1+an−1​xn−2+⋯+a2​x+a1​)x+a0​=(((an​x+an−1​)x+an−2​)x+⋯+a1​)x+a0​​

求上面的值的時候，很明顯可以從括号裡由内到位一次計算，最後的計算複雜度為n次乘法與n次加法。

2.java String中的HashCode

看看String類裡hashCode的源碼。

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
           

根據源碼不難看出，其計算方式就是

s [ 0 ] ∗ 3 1 ( n − 1 ) + s [ 1 ] ∗ 3 1 ( n − 2 ) + . . . + s [ n − 2 ] ∗ 31 + s [ n − 1 ] s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-2] * 31 + s[n-1] s[0]∗31(n−1)+s[1]∗31(n−2)+...+s[n−2]∗31+s[n−1]

3.MurMurHash

上面的hashCode方法有個不好的地方就是變化不夠激烈。比如我們看一下的例子

@Test
    public void test2() {
        String s1 = "abcdefg";
        String s2 = "abcdeff";
        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());
    }
           

上面代碼運作的結果為

-1206291356
-1206291357
           

兩個相似的字元串，得到的hash值也很相似。

MurmurHash 是一種非加密型哈希函數，适用于一般的哈希檢索操作。由Austin Appleby 在2008年發明，并出現了多個變種，都已經釋出到了公有領域。與其它流行的哈希函數相比，對于規律性較強的key，MurmurHash的随機分布特征表現更良好，現在在libstdc++，hadoop和nginx等很多著名開源項目中使用。