前言

假設(shè)現(xiàn)在有一篇很長的文檔，如果希望統(tǒng)計(jì)文檔中每個(gè)單詞在文檔中出現(xiàn)了多少次，應(yīng)該怎么做呢？

很簡單！

我們可以建一個(gè)HashMap，以String類型為Key，Int類型為Value；

• 遍歷文檔中的每個(gè)單詞 word ，找到鍵值對中key為 word 的項(xiàng)，并對相關(guān)的value進(jìn)行自增操作。
• 如果該key= word 的項(xiàng)在 HashMap中不存在，我們就插入一個(gè)(word,1)的項(xiàng)表示新增。
• 這樣每組鍵值對表示的就是某個(gè)單詞對應(yīng)的數(shù)量，等整個(gè)文檔遍歷完成，我們就可以得到每個(gè)單詞的數(shù)量了。

簡單實(shí)現(xiàn)下，代碼示例如下：

import java.util.HashMap;
import java.util.Map;
public class Test {
    public static void main(String[] args) {
        Map map = new HashMap<>();
        String doc = "yue ban fei yu";
        String[] words = doc.split(" ");
        for (String s : words) {
            if (!map.containsKey(s)) {
                map.put(s, 1);
            } else {
                map.put(s, map.get(s) + 1);
            }
        }
        System.out.println(map);
    }
}

那HashMap是怎么做到高效統(tǒng)計(jì)單詞對應(yīng)數(shù)量的？我們下面會(huì)逐步來研究一下！

首先我們先來看看如果只統(tǒng)計(jì)某一個(gè)單詞的數(shù)量？

只需要開一個(gè)變量，同樣遍歷所有單詞，遇到和目標(biāo)單詞一樣的，才對這個(gè)變量進(jìn)行自增操作；

• 等遍歷完成，我們就可以得到該單詞的數(shù)量了。
• 我們可以把所有可能出現(xiàn)的單詞都列出來，每個(gè)單詞，單獨(dú)用一個(gè)變量去統(tǒng)計(jì)它出現(xiàn)的數(shù)量，遍歷所有單詞，判斷當(dāng)前單詞應(yīng)該被累計(jì)到哪個(gè)變量中。

import java.util.HashMap;
import java.util.Map;
public class Main {
    public static void main(String[] args) {
        int[] cnt = new int[20000];
        String doc = "a b c d";
        String[] words = doc.split(" ");
        int a = 0;
        int b = 0;
        int c = 0;
        int d = 0;
        
        for (String s : words) {
           if (s == "a") a++;
           if (s == "b") b++;
           if (s == "c") c++;
           if (s == "d") d++;   
        }
    }
}

注意：這樣的代碼顯然有兩個(gè)很大的問題：

1. 對單詞和計(jì)數(shù)器的映射關(guān)系是通過一堆if-else寫死的，維護(hù)性很差；
2. 必須已知所有可能出現(xiàn)的單詞，如果遇到一個(gè)新的單詞，就沒有辦法處理它了。

優(yōu)化1

我們可以開一個(gè)數(shù)組去維護(hù)計(jì)數(shù)器。

具體做法就是，給每個(gè)單詞編個(gè)號(hào)，直接用編號(hào)對應(yīng)下標(biāo)的數(shù)組元素作為它的計(jì)數(shù)器就好啦。

我們可以建立兩個(gè)數(shù)組：

• 第一個(gè)數(shù)組用于存放所有單詞，數(shù)組下標(biāo)就是單詞編號(hào)了，我們稱之為字典數(shù)組；
• 第二個(gè)數(shù)組用于存放每個(gè)單詞對應(yīng)的計(jì)數(shù)器，我們稱之為計(jì)數(shù)數(shù)組。

每遇到一個(gè)新的單詞，都遍歷一遍字典數(shù)組，如果沒有出現(xiàn)過，我們就將當(dāng)前單詞插入到字典數(shù)組結(jié)尾。

這樣做，整體的時(shí)間復(fù)雜度較高，還是不行。

優(yōu)化2

優(yōu)化方式：

• 一種是我們維護(hù)一個(gè)有序的數(shù)據(jù)結(jié)構(gòu)，讓比較和插入的過程更加高效，而不是需要遍歷每一個(gè)元素判斷逐一判斷。
• 另一種思路就是我們是否能尋找到一種直接基于字符串快速計(jì)算出編號(hào)的方式，并將這個(gè)編號(hào)映射到一個(gè)可以在O(1)時(shí)間內(nèi)基于下標(biāo)訪問的數(shù)組中。

以單詞為例，英文單詞的每個(gè)字母只可能是 a-z。

我們用0表示a、1表示b，以此類推，用25表示z，然后將一個(gè)單詞看成一個(gè)26進(jìn)制的數(shù)字即可。

import java.util.HashMap;
import java.util.Map;
public class Main {
    public static void main(String[] args) {
        int[] cnt = new int[20000];
        String doc = "a b c d";
        String[] words = doc.split(" ");
        for (String s : words) {
            int tmp = 0;
            for (char c: s.toCharArray()) {
                tmp *= 26;
                tmp += (c - 'a');
            }
            cnt[tmp]++;
        }
        String target = "a";
        int hash = 0;
        for (char c: target.toCharArray()) {
            hash *= 26;
            hash += c - 'a';
        }
        System.out.println(cnt[hash]);
    }
}

這樣我們統(tǒng)計(jì)N個(gè)單詞出現(xiàn)數(shù)量的時(shí)候，整體只需要O(N)的復(fù)雜度，相比于原來的需要遍歷字典的做法就明顯高效的多。

這其實(shí)就是散列的思想了。

優(yōu)化3

使用散列！

散列函數(shù)的本質(zhì)，就是將一個(gè)更大且可能不連續(xù)空間（比如所有的單詞），映射到一個(gè)空間有限的數(shù)組里，從而借用數(shù)組基于下標(biāo)O(1)快速隨機(jī)訪問數(shù)組元素的能力。

但設(shè)計(jì)一個(gè)合理的散列函數(shù)是一個(gè)非常難的事情。

• 比如對26進(jìn)制的哈希值再進(jìn)行一次對大質(zhì)數(shù)取mod的運(yùn)算，只有這樣才能用比較有限的計(jì)數(shù)數(shù)組空間去表示整個(gè)哈希表。

取了mod之后，我們很快就會(huì)發(fā)現(xiàn)，現(xiàn)在可能出現(xiàn)一種情況，把兩個(gè)不同的單詞用26進(jìn)制表示并取模之后，得到的值很可能是一樣的。

這個(gè)問題被稱之為哈希碰撞。

如何實(shí)現(xiàn)

最后我們考慮一下散列函數(shù)到底需要怎么設(shè)計(jì)。

以JDK（JDK14）的HashMap為例：

• 主要實(shí)現(xiàn)在 ??java.util?? 下的 ??HashMap?? 中，這是一個(gè)最簡單的不考慮并發(fā)的、基于散列的Map實(shí)現(xiàn)。

找到其中用于計(jì)算哈希值的hash方法：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

可以發(fā)現(xiàn)就是對??key.hashCode()??進(jìn)行了一次特別的位運(yùn)算。

hashcode方法

在Java中每個(gè)對象生成時(shí)都會(huì)產(chǎn)生一個(gè)對應(yīng)的hashcode。

• 當(dāng)然數(shù)據(jù)類型不同，hashcode的計(jì)算方式是不一樣的，但一定會(huì)保證的是兩個(gè)一樣的對象，對應(yīng)的hashcode也是一樣的；

所以在比較兩個(gè)對象是否相等時(shí)，我們可以先比較hashcode是否一致，如果不一致，就不需要繼續(xù)調(diào)用equals，大大降低了比較對象相等的代價(jià)。

我們就一起來看看JDK中對String類型的hashcode是怎么計(jì)算的，我們進(jìn)入 ??java.lang?? 包查看String類型的實(shí)現(xiàn)：

public int hashCode() {
    // The hash or hashIsZero fields are subject to a benign data race,
    // making it crucial to ensure that any observable result of the
    // calculation in this method stays correct under any possible read of
    // these fields. Necessary restrictions to allow this to be correct
    // without explicit memory fences or similar concurrency primitives is
    // that we can ever only write to one of these two fields for a given
    // String instance, and that the computation is idempotent and derived
    // from immutable state
    int h = hash;
    if (h == 0 && !hashIsZero) {
        h = isLatin1() ? StringLatin1.hashCode(value)
                       : StringUTF16.hashCode(value);
        if (h == 0) {
            hashIsZero = true;
        } else {
            hash = h;
        }
    }
    return h;
}

Latin和UTF16是兩種字符串的編碼格式，實(shí)現(xiàn)思路其實(shí)差不多，我們來看看??StringUTF16??中hashcode的實(shí)現(xiàn)：

public static int hashCode(byte[] value) {
    int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
        h = 31 * h + getChar(value, i);
    }
    return h;
}

其實(shí)就是對字符串逐位按照下面的方式進(jìn)行計(jì)算，和展開成26進(jìn)制的想法本質(zhì)上是相似的。

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

為什么選擇了31？

首先在各種哈希計(jì)算中，我們比較傾向使用奇素?cái)?shù)進(jìn)行乘法運(yùn)算，而不是用偶數(shù)。

因?yàn)橛门紨?shù)，尤其是2的冪次，進(jìn)行乘法，相當(dāng)于直接對原來的數(shù)據(jù)進(jìn)行移位運(yùn)算；這樣溢出的時(shí)候，部分位的信息就完全丟失了，可能增加哈希沖突的概率。

為什么選擇了31這個(gè)奇怪的數(shù)，這是因?yàn)橛?jì)算機(jī)在進(jìn)行移位運(yùn)算要比普通乘法運(yùn)算快得多，而??31*i??可以直接轉(zhuǎn)化為??(i << 5)- i?? ，這是一個(gè)性能比較好的乘法計(jì)算方式，現(xiàn)代的編譯器都可以推理并自動(dòng)完成相關(guān)的優(yōu)化。

具體可以參考《Effective Java》中的相關(guān)章節(jié)。

h>>>16

我們現(xiàn)在來看 ??^ h >>> 16?? 又是一個(gè)什么樣的作用呢？

它的意思是就是將h右移16位并進(jìn)行異或操作，為什么要這么做呢？

因?yàn)槟莻€(gè)hash值計(jì)算出來這么大，那怎么把它連續(xù)地映射到一個(gè)小一點(diǎn)的連續(xù)數(shù)組空間呢？

所以需要取模，我們需要將hash值對數(shù)組的大小進(jìn)行一次取模。

我們需要對2的冪次大小的數(shù)組進(jìn)行一次取模計(jì)算。

但對二的冪次取模相當(dāng)于直接截取數(shù)字比較低的若干位，這在數(shù)組元素較少的時(shí)候，相當(dāng)于只使用了數(shù)字比較低位的信息，而放棄了高位的信息，可能會(huì)增加沖突的概率。

所以，JDK的代碼引入了??^ h >>> 16?? 這樣的位運(yùn)算，其實(shí)就是把高16位的信息疊加到了低16位，這樣我們在取模的時(shí)候就可以用到高位的信息了。

如何處理哈希沖突呢？

JDK中采用的是開鏈法。

哈希表內(nèi)置數(shù)組中的每個(gè)槽位，存儲(chǔ)的是一個(gè)鏈表，鏈表節(jié)點(diǎn)的值存放的就是需要存儲(chǔ)的鍵值對。

如果碰到哈希沖突，也就是兩個(gè)不同的key映射到了數(shù)組中的同一個(gè)槽位，我們就將該元素直接放到槽位對應(yīng)鏈表的尾部。

總結(jié)一下

手寫數(shù)據(jù)結(jié)構(gòu)統(tǒng)計(jì)單詞的數(shù)量正確的思路就是：

根據(jù)全文長度大概預(yù)估一下會(huì)有多少個(gè)單詞，開一個(gè)數(shù)倍于它的數(shù)組，再設(shè)計(jì)一個(gè)合理的hash函數(shù)，把每個(gè)單詞映射到數(shù)組的某個(gè)下標(biāo)，用這個(gè)數(shù)組計(jì)數(shù)統(tǒng)計(jì)就好啦。

當(dāng)然在實(shí)際工程中，我們不會(huì)為每個(gè)場景都單獨(dú)寫一個(gè)這樣的散列表實(shí)現(xiàn)，也不用自己去處理復(fù)雜的擴(kuò)容場景。