散串列漫談
散串列的英文叫做Hash Table，平時我們也稱之為哈希表，其基本思想是通過某個函式將資料映射到陣列中的某個位置，再通過陣列可以通過下標隨機訪問特性快速查找元素的，
通過這樣的定義我們可以分析出，散串列的關鍵在于兩個因素
HASH函式- 陣列
作為最著名的散串列實作，我們來看一下Java的HashMap是怎么實作的，
首先膜拜這幾個亮閃閃的人物
- Doug Lea
- Josh Bloch
正所謂"編程不識Doug Lea,寫盡Java也枉然"，我們在java.utils.concurrent包里還會再次遇到，
對于一個工業級的散串列實作需要考慮的問題
-
如何設計散列函式？
-
如何解決散列沖突？
-
裝載因子過大/過小怎么辦？
-
如何避免低效的擴容？
針對這幾個問題，以下依次分析
1. 如何設計散列函式？
散列函式的設計應該有兩個要求：高效、隨機且均勻分布
散串列的查詢時間復雜度包括三個方面，hash的時間開銷，從陣列中索引值得開銷，當然還有解決hash沖突的開銷，
理論上我們會說O(10000+N)的復雜度也是O(N)呀，但是工程上是要有取舍的，假如一個hash函式需要上萬次操作，而元素的個數只有幾十個，這時候反而是順序遍歷更快，工程上也有很多這種場景，如果陣列元素很少的情況下直接遍歷反而會比HashMap更快，
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0
&& (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
上面的代碼是Java 11中的HashMap的get方法及其實作，getNode的程序很好理解：
- 先通過
hash找到在陣列中的下標，如果陣列是慷訓者對應位置為空說明元素不在表中； - 否則找對應位置元素的key是否與查找的key相等，如果相等則回傳
- 如果下標相同的位置key不同，說明遇到hash沖突了，按開鏈法依次從鏈表找key相同的，或者是從紅黑樹里查找
這里有幾個問題：
1. first = tab[(n - 1) & hash]是什么意思？
實際上這個做法等價于hash % n，也就是對陣列長度取余，當然這是有前提的，當n是2的冪次時該等式成立，這里需要回答兩個問題:
-
為什么要取余?
因為hash函式回傳的數字是一個
int可能超出陣列長度，這樣做的目的是將hash值均勻分布到陣列的范圍內，實際上，取余也是一種常見的hash演算法， -
為什么不用
%呢？當然是為了性能，
HashMap是一個非常常用的類，能扣一點性能是一點，一般認為JAVA中的&會比%快10倍左右(來源待考).為什么這樣做能成立呢，實際上\(2^n-1\)用二進制表示就是\(0b\underbrace{111111}, n個1\)，對其做與運算相當于舍棄高位，等價于取余
2. (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)是什么意思？
-
key == null時hash值是0，所以HashMap可以存key為null的值； -
(h = key.hashCode()) ^ (h >>> 16)這句話的意思是將key.hashCode())與h >>> 16異或假設
length=8,key的hashcode = 78897121，轉換成二進制就是：100101100111101111111100001與
(length-1)& 運算如下0000 0100 1011 0011 1101 1111 1110 0001 & 0000 0000 0000 0000 0000 0000 0000 0111 = 0000 0000 0000 0000 0000 0000 0000 0001我們可以得出結論：
- length = 2^N時，下標運算的結果取決于哈希值的低N位
- 對于大多數情況，length小于2^16，為了讓高16位參與運算將h右移16位與自身做異或運算，得到的下標更為隨機
Times33演算法與最快的Hash表
事實上，我們在String的hashCode里面看到了這樣一段代碼
public static int hashCode(byte[] value) {
int h = 0;
for (byte v : value) {
h = 31 * h + (v & 0xff);
}
return h;
}
這個演算法思想來源于Times33演算法hash(i) = hash(i-1) * 33 + str[i]，為毛是31,可以參考StackOverflow上的這個回答
Why does Java's hashCode() in String use 31 as a multiplier?
簡單來說：
- 它是一個質數
- n * 31 == (n << 5) - n
- 基于測驗和統計資料，如果你使用 31，33， 37，39 和 41 這幾個數值，將其應用于 hashCode 的演算法中，每一個數字對超過 50000 個英語單詞（由兩個 Unix 版本的字典的并集構成）產生的 hash 只會產生少于 7 個的沖突，
說完HASH函式，我們再扯扯陣列，
散列函式的設計前文已經分析了，HashMap使用的是物件的hashCode()，為了使哈希函式高效，生成的值分布均勻，使用了高16位異或，和length - 1取或運算，
2. 如何解決散列沖突?
既然用到hash，就免不了有hash 沖突，所謂hash沖突就是有多個key經過hash計算后映射到到了相同的下標，常用的解決方法有
- 開放尋址法(open addressing)
- 鏈表法(chaining)
開放尋址法
開放尋址法的核心思想是，如果出現了散列沖突，就重新探測一個新的空閑位置，主要方法有線性探測(Linear Probing)、二次探測(Quadratic probing)、雙重散列(Double hashing)
1. 線性探測
線性探測的思路就是，如果某個資料經過hash后發現位置已經被占用了，就從這個位置開始，依次向后查找，直到有空閑位置就插入，
查找的時候也是一樣的，如果通過hash后發現位置存在值且不相等，就從這個位置開始，依次向后查找，直到找到相等的元素，如果找到空閑位置說明該元素不在表中，
洗掉的時候呢，從上面的描述知道，如果單純的線性遍歷然后洗掉對應的元素會造成空洞，查找時候會提前回傳，演算法失效，如何解決呢，可以在洗掉的時候將后續的元素依次往前搬移，當然也可以優化一點，將最后一個元素交換到洗掉的位置；還有更優化的方法是在洗掉的位置使用deleted標記，相應的也需要修改插入和查找的邏輯，
2. 二次探測
所謂二次探測思路和線性探測類似，只不過每次探測的步長改成了原來的二次方`
\[H_0 = hash(x) \\ H_i = mod((H_0 + i^2), m), m = 1, 2, 3, ..., (m-1)/2 \]
主要優勢是可以解決線性探測分布更為隨機，避免資料過于聚集，
3. 雙重散列
實際上就是用多組散列函式，第一組發現沖突后再用第二組，依次直到找到空閑位置
鏈表法
鏈表法很簡單就是在發現hash沖突后在將沖突的元素依次向該下標的槽位對應鏈表的后面加一條資料即可，查詢也是順著鏈表查詢，洗掉直接洗掉鏈表的該節點即可；這里就有一個問題了，如果鏈表過長的話，散串列就退化成鏈表了，解決的方法有兩個，一是減小裝載因子，降低沖突的概率；二是將鏈表轉成快速查找的動態資料結構，常見的有跳表、紅黑樹，這樣最壞的情況下也只是退化成O(logn)的復雜度，
同樣的我們來分析HashMap的實作
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = https://www.cnblogs.com/edifyX/p/e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
以上是插入的代碼，可以看到是標準的鏈表法
- 如果位置沒被占用，呼叫newNode在該位置插入一條資料
- 如果位置占用，且不存在沖突，修改Node的值
- 有沖突判斷是紅黑樹還是鏈表，如果是鏈表就在鏈表尾部插入一條資料，如果鏈表長度大于TREEIFY_THRESHOLD=8，將會呼叫treeifyBin將鏈表轉成紅黑樹，
- 如果元素個數超過閾值，執行
resize()，這個我們后面分析擴容操作
3. 裝載因子過大/過小怎么辦？
不管使用哪種探測方法，當散串列中空閑位置不多的時候，散列沖突的概率就會大大提高(抽屜原理)，為了描述散串列中空閑的程度，我們引入裝載因子的概念
\[loadFactor = size / capacity \]
也就是填入表中元素的個數/散串列的長度，這樣我們就能理解工程上為什么比較常用的是鏈表法了，鏈表法可以容納的裝載因子更高，甚至可以大于1，而開放尋址法的可容納的裝載因子較低，
總結起來就是，開放尋址法簡單，資料存盤為陣列結構，能夠有效的利用CPU快取，但是裝載因子不能過高，常用于資料量較小，裝載因子小的情況，例如 Java 中的 ThreadLocalMap；鏈表法適合于通用的場景，支持更多的優化策略，例如HashMap中的紅黑樹，
再回答上面的問題，裝載因子過大/過小怎么辦
- 過大的散列沖突的概率也越大，效率降低，需要擴容
- 過小浪費空間，需要縮容
陣列擴容/縮容
基本原理很簡單，就是新開辟一個陣列，長度是原來的一倍、1/2，再將原來的元素依次hash并插入新的陣列，這里涉及幾個問題
- 移動大量資料耗時，造成系統抖動
- 沖突鏈表的移動
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
如何避免低效的擴容？
這里可以考慮redis的rehash機制，采用漸進式的方式，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/41957.html
標籤：Java