HashMap與HashTable的小細節筆記

1. 繼承樹

繼承類型	HashMap	HashTable
類	AbstractMap<K,V>	Dictionary<K,V>
接口	Map<K,V>, Cloneable, Serializable	Map<K,V>, Cloneable, Serializable

繼承的接口是一樣的，都是Map，Cloneable，Serializable 接口

繼承的類不一樣。

1. 資料存儲結構

HashMap	HashTable
Node<K,V>[] 連結清單數組（後面會轉紅黑樹）	Entry<K,V>[] 連結清單數組

其中Node，Entry 都是接口 Map.Entry 的一個實作。大體上沒有什麼差别。

1. 執行個體化過程的差別

類目	HashMap	HashTable
是否執行個體化數組	不會執行個體化 Node 數組	會根據初始數組容量，初始化Entry 空數組
預設數組容量	預設初始數組容量大小是16	預設數組大小是11
預設擴容因子	0.75f	0.75f

執行個體化對象的時候，最大的差别是：

• HashMap 是僅僅做了一些基本的參數設定，不會生産數組。
• HashTable 是出了數組容量、擴容因子的設定，還會生成一個空數組

1. Hash 和index 計算的差別

類目	HashMap	HashTable
hash 計算	h=h==0?: (h = key.hashCode()) ^ (h >>> 16)	h=h=0?0:key.hashCode()，直接調用hashcode 方法 擷取 hash值
index定位	(n-1)& hash	(hash & 0x7FFFFFFF) % tab.length

• >>>

  是邏輯右移，就是不管符号，右移的時候，左邊補0，如1101>>>1= 0110；

• hashMap 在hash 的時候，特意的把hash值進行了一次異或運算。得到的結果是：

  高16不會變。低16變成了高16位和低16位的異或結果，使得低16位也有了高16位的特征；盡量的做到隻有有1位的變化，就會是的 異或結果不一樣，進而降低了Hash沖突。

  • 0^1=1
  • 1^1=0
  • 0^0=0
• index的計算，涉及兩個點
  • hash值為可能出現負數，需要把hash值修改為 正數 ，index 一定是 正數
  • 在目前的數組長度範圍内。

HashTable 做法

• 為了確定 hash值不會出現負數，HashTable 做法比較簡單 hash & 0x7FFFFFFF 的效果相當于Math.abs(hash); 取絕對值；0x7FFFFFFF 的二進制： 0111 1111 1111 1111 1111 1111 1111； 做 & 運算後，最高位的符号位一定是 0； 其餘位不變。
  • 0&1=0，1&1=1
• 為了確定index 不會超出數組容量，那麼HashTable 進行了取模運算，得到的餘數就是目前插入的index.

HashMap 做法

• n=tab.length 為2n，那麼n-1 一定是一個正數，是以最高位一定是0，就是類似與上面的0x7FFFFFFF=232 -1 ；
• （n-1）& hash 直接确定了 結果是一個正數，并且（n-1）& hash <= n-1;

綜合上面的對比，index 計算上，HashMap 全部都是位運算，會快一些。在Hash的分布上，HashMap 更加能夠避免Hash碰撞 。

1. 新增元素

類目	HashMap	HashTable
Value 是否能夠為空	可以 value == null	value != null
是否線程同步	否	是，synchronized 修飾方法
擴容順序	确認Hash是否沖突，否則先插入元素 ，沖突則确認是否存在， 判斷是否需要擴容	複制一遍目前的table，判斷是否需要擴容 ，取出index位置的資料, 插入元素
Hash 沖突處理	通過(n-1)&hash 定位數組位置找到連結清單的第一個元素，開始周遊next 是否為空；空則新增元素在連結清單【最後一個】位置，不為空則 修改next的value	通過(hash & 0x7FFFFFFF) % tab.length 來定位數組位置找到連結清單的第一個元素，開始周遊next 是否為空；不為空則修改，則修改對應的value，否則添加新的元素在連結清單的【第一個】位置

是以結構圖如下

小細節點：

• HashTable 在Hash沖突的情況下，新增元素，是取兩次，第一次判斷是否重複；第二次 把老的index值關聯到新的值的next上，把最新值放到 index 位置上。HashMap 則是沿着index 定位到元素，判斷是否重複，否則關聯到最後的next 上去。

1. 擴容過程

類目	HashMap	HashTable
判斷條件	++size>threshold ；同時沒有超過預設的最大容量1<<30 (230)	count >= threshold ; 沒有超過預設的最大容量Integer.MAX_VALUE - 8
擴容後大小	newCap = oldCap << 1,原來的2倍；也是為了index 定位的時候使用位運算更加高效率	(oldCapacity << 1) + 1，原來的大小* 2 +1 ；保持擴容後的大小為奇數；可以讓後續的取模運算拿到的index 更加均勻些。就是為了均勻分布
擴容後元素的位置變化	分高位為0和高位不為0 的情況；hash&oldCap== 0 屬于高位為0的 保留在原阿裡位置上tab[i]，高位為1的進行oldCap的偏移 tab[i+oldCap]	同一個Hash值的定位沒有變化，但是，定位到的Hash值的連結清單順序變成來反序。比如，第3個位置的連結清單是A->B->C,變成來 C->B->A

hash& oldCap == 0 的講解：

能夠得出上面的結果的前提：1. oldCap = 2n;2. hash = h0?: (h = key.hashCode()) ^ (h >>> 16)；

上面的結構就是可以得出兩個中資料類型：

oldCap=2n的二進制：10000000……；

那麼在進行&操作的時候，除了（最）高位，其他的一定都是0；低位結果就是0；高位的結果是1或者0；

是以就是兩種情況：

hash& oldCap == 0 的情況，記錄為低位資料，疑問點：((newCap = oldCap<<1)-1)& hash 是否和（oldCap-1）&hash 相等； 結果是相等的。論證過程如下：

• oldCap-1 結果是：0000 1111，24-1 ；15，預設大小-1; oldCap=0001 0000
• newCap-1 結果是：0001 1111，25-1; 31，預設大小*2-1
• 又因為 是 hash & oldCap==0；那麼得出結果就是 hash 的第5位的一定是0；也就是在這種情況下，能夠對 hash & （oldCap-1）操作的結果有效的隻有前4位。newCap-1和oldCap-1 都是右邊4位得到有效的計算，其餘的都是0，是以它們的結果是一樣的。
• 那麼就是說，這情況在擴容後，位置不變的。還在原來的index 上。

hash& oldCap != 0 的情況下，記錄為高位資料， 疑問點：（newCap-1）& hash 是多少？

• 我們看newCap-1 和oldCap-1 差别就是 就是一個oldCap，下面通過二進制來論證一下& hash 之後是否也是一個oldCap。
• 在&計算下，hash& oldCap != 0, 那麼可以直接得出是第5位一定不是0就是1。通過二進制的計算比對：
• oldCap-1 結果是：0000 1111，24-1 ；15，預設大小-1
• newCap-1 結果是：0001 1111，25-1; 31，預設大小*2-1
• 結合上面的兩個結論得出：(oldCap-1)& hash = 0000 XXXX,(newCap-1)& hash = 0001 XXXX, 他們差就是 0001 0000， 這個對應的十進制值就是：24 = oldCap; XXXX 表示，低位的結果和1 做& 運算結果是一樣的。
• 是以，hash&oldCap !=0 的情況下，index 定位，發生了一個oldCap 的偏移。屬于高位偏移的資料。

是以 代碼上，在周遊的時候，會出現了 loHead，loTail，hiHead，hiTail； 分别來記錄原來的連結清單。

簡單的了解就是原來的index 對應的連結清單是：tab[i]=A-B-C-D; 擴容後可能結果是：tab[i]=A-C;tab[i+oldCap]=B-D; 使得原本沖突的值，再次分散了。這個就是為什麼HashMap的Hash 沖突會比HashTable 低的直接展現。

上面的過程是在HashMap 對應的連結清單的長度不超過8的時候，會進行的操作，如果連結清單的長度超過了8并且 HashMap.length>= 64 的時候，那麼就會沖連結清單的結構重新轉成 紅黑樹

1. Get 取值

類目	HashMap	HashTable
index定位	(n-1)& hash	(hash & 0x7FFFFFFF) % tab.length

定位完成之後，傳回key和hash 都相同的值。都會周遊 連結清單。

1. 删除：

   定位過程和Get 取值是一樣的。

   拿到 tab[index] 上，如果是連結清單上的資料，斷開next 指針，重連到下一個元素就好了