如何實現一個優秀的散列表！
前言
假設現在有一篇很長的文檔，如果希望統計文檔中每個單詞在文檔中出現了多少次，應該怎么做呢?
很簡單!
我們可以建一個HashMap，以String類型為Key，Int類型為Value。
- 遍歷文檔中的每個單詞 word ，找到鍵值對中key為 word 的項，并對相關的value進行自增操作。
- 如果該key= word 的項在 HashMap中不存在，我們就插入一個(word,1)的項表示新增。
- 這樣每組鍵值對表示的就是某個單詞對應的數量，等整個文檔遍歷完成，我們就可以得到每個單詞的數量了。
簡單實現下，代碼示例如下：
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是怎么做到高效統計單詞對應數量的?我們下面會逐步來研究一下!
首先我們先來看看如果只統計某一個單詞的數量?
只需要開一個變量，同樣遍歷所有單詞，遇到和目標單詞一樣的，才對這個變量進行自增操作;
- 等遍歷完成，我們就可以得到該單詞的數量了。
- 我們可以把所有可能出現的單詞都列出來，每個單詞，單獨用一個變量去統計它出現的數量，遍歷所有單詞，判斷當前單詞應該被累計到哪個變量中。
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++;
}
}
}
注意：這樣的代碼顯然有兩個很大的問題。
- 對單詞和計數器的映射關系是通過一堆if-else寫死的，維護性很差。
- 必須已知所有可能出現的單詞，如果遇到一個新的單詞，就沒有辦法處理它了。
優化 1
我們可以開一個數組去維護計數器。
具體做法就是，給每個單詞編個號，直接用編號對應下標的數組元素作為它的計數器就好啦。
我們可以建立兩個數組：
- 第一個數組用于存放所有單詞，數組下標就是單詞編號了，我們稱之為字典數組。
- 第二個數組用于存放每個單詞對應的計數器，我們稱之為計數數組。
每遇到一個新的單詞，都遍歷一遍字典數組，如果沒有出現過，我們就將當前單詞插入到字典數組結尾。
這樣做，整體的時間復雜度較高，還是不行。
優化 2
優化方式：
- 一種是我們維護一個有序的數據結構，讓比較和插入的過程更加高效，而不是需要遍歷每一個元素判斷逐一判斷。
- 另一種思路就是我們是否能尋找到一種直接基于字符串快速計算出編號的方式，并將這個編號映射到一個可以在O(1)時間內基于下標訪問的數組中。
以單詞為例，英文單詞的每個字母只可能是 a-z。
我們用0表示a、1表示b，以此類推，用25表示z，然后將一個單詞看成一個26進制的數字即可。
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]);
}
}
這樣我們統計N個單詞出現數量的時候，整體只需要O(N)的復雜度，相比于原來的需要遍歷字典的做法就明顯高效的多。
這其實就是散列的思想了。
優化 3
使用散列!
散列函數的本質，就是將一個更大且可能不連續空間(比如所有的單詞)，映射到一個空間有限的數組里，從而借用數組基于下標O(1)快速隨機訪問數組元素的能力。
但設計一個合理的散列函數是一個非常難的事情。
比如對26進制的哈希值再進行一次對大質數取mod的運算，只有這樣才能用比較有限的計數數組空間去表示整個哈希表。
取了mod之后，我們很快就會發現，現在可能出現一種情況，把兩個不同的單詞用26進制表示并取模之后，得到的值很可能是一樣的。
這個問題被稱之為哈希碰撞。
如何實現
最后我們考慮一下散列函數到底需要怎么設計。
以JDK(JDK14)的HashMap為例：
- 主要實現在 java.util 下的 HashMap 中，這是一個最簡單的不考慮并發的、基于散列的Map實現。
找到其中用于計算哈希值的hash方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以發現就是對key.hashCode()進行了一次特別的位運算。
hashcode方法：
在Java中每個對象生成時都會產生一個對應的hashcode。
- 當然數據類型不同，hashcode的計算方式是不一樣的，但一定會保證的是兩個一樣的對象，對應的hashcode也是一樣的。
所以在比較兩個對象是否相等時，我們可以先比較hashcode是否一致，如果不一致，就不需要繼續調用equals，大大降低了比較對象相等的代價。
我們就一起來看看JDK中對String類型的hashcode是怎么計算的，我們進入 java.lang 包查看String類型的實現：
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是兩種字符串的編碼格式，實現思路其實差不多，我們來看看StringUTF16中hashcode的實現：
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;
}
其實就是對字符串逐位按照下面的方式進行計算，和展開成26進制的想法本質上是相似的。
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
為什么選擇了31?
首先在各種哈希計算中，我們比較傾向使用奇素數進行乘法運算，而不是用偶數。
因為用偶數，尤其是2的冪次，進行乘法，相當于直接對原來的數據進行移位運算;這樣溢出的時候，部分位的信息就完全丟失了，可能增加哈希沖突的概率。
為什么選擇了31這個奇怪的數，這是因為計算機在進行移位運算要比普通乘法運算快得多，而31*i可以直接轉化為(i << 5)- i ，這是一個性能比較好的乘法計算方式，現代的編譯器都可以推理并自動完成相關的優化。
具體可以參考《Effective Java》中的相關章節。
h>>>16。
我們現在來看 ^ h >>> 16 又是一個什么樣的作用呢?
它的意思是就是將h右移16位并進行異或操作，為什么要這么做呢?
因為那個hash值計算出來這么大，那怎么把它連續地映射到一個小一點的連續數組空間呢?
所以需要取模，我們需要將hash值對數組的大小進行一次取模。
我們需要對2的冪次大小的數組進行一次取模計算。
但對二的冪次取模相當于直接截取數字比較低的若干位，這在數組元素較少的時候，相當于只使用了數字比較低位的信息，而放棄了高位的信息，可能會增加沖突的概率。
所以，JDK的代碼引入了^ h >>> 16 這樣的位運算，其實就是把高16位的信息疊加到了低16位，這樣我們在取模的時候就可以用到高位的信息了。
如何處理哈希沖突呢?
JDK中采用的是開鏈法。
哈希表內置數組中的每個槽位，存儲的是一個鏈表，鏈表節點的值存放的就是需要存儲的鍵值對。
如果碰到哈希沖突，也就是兩個不同的key映射到了數組中的同一個槽位，我們就將該元素直接放到槽位對應鏈表的尾部。
總結一下
手寫數據結構統計單詞的數量正確的思路就是：
根據全文長度大概預估一下會有多少個單詞，開一個數倍于它的數組，再設計一個合理的hash函數，把每個單詞映射到數組的某個下標，用這個數組計數統計就好啦。
當然在實際工程中，我們不會為每個場景都單獨寫一個這樣的散列表實現，也不用自己去處理復雜的擴容場景。
