Hashtable 提供的功能
- Hashtable是一個線程安全的Map，其線程安全是通過在各個方法上加上synchronized關(guān)鍵字實現(xiàn)的喇勋，即：該類只能被一個線程所使用，其他調(diào)用該類時會阻塞等待;
- 實現(xiàn)了哈希表偎行，映射key到value川背；
- key和value都不能為null（因為需要調(diào)用hashCode()方法，如果為null的話就會拋出NPE）蛤袒，key類型必須實現(xiàn)hashCode()和equals()方法熄云；
- put(K k,V v);
- get(K k,V v);
Hashtable沒有實現(xiàn)hash沖突的解決方案，沖突需要按自己的邏輯實現(xiàn)妙真，它只提供了哈希表自動擴容的功能缴允；- 出現(xiàn)hash沖突時，采用單向鏈表來儲存沖突的元素珍德。
Hashtable 涉及到的概念
- 初始化容量：key數(shù)組初始長度练般，默認值是11
- 負載系數(shù)（load factor）：即到達容量的百分比時，哈希表就會重新hash到一個新容量的哈希表中,取值范圍是：<1.0 的百分數(shù) 默認取值是.75(75%锈候，當加入的鍵值對數(shù)量達到初始容量的75%時薄料，繼續(xù)加入的話會重新hash到一個新的容量的哈希表中)
- 閾(yù)值：threshold=初始化容量*0.75和Integer.MAX_VALUE-8（注：Integer.MAX_VALUE=0x7FFFFFFF）
中較小值 - 重新Hash：加入元素時，當數(shù)組大小大于等于閾值時泵琳，key數(shù)組的容量會左移2位后+1即：原容量*4+1摄职，然后按新的容量hash后放入新的數(shù)組中誊役。
- 哈希函數(shù)：(key.hashCode() & 0x7FFFFFFF) % key數(shù)組現(xiàn)在的長度
Hashtable常用方法分析
- put(K k,V v);
添加元素到哈希表時，判斷元素是否存在谷市，如果存在（key的hash相同并且值也相同）的話蛔垢，就會覆蓋掉原來的元素，并返回原來的值歌懒；如果不存在的話啦桌，就會直接新建一個元素，若產(chǎn)生hash沖突則將舊元素鏈接到新元素的尾部及皂。 - get(K k);
獲取元素時甫男，先根據(jù)key的hash獲取到對應(yīng)key數(shù)組的下標，獲取對應(yīng)的元素（因為數(shù)組元素的值是一個單鏈表验烧，所以如果當前的值不匹配時就需要判斷鏈表的下一個元素）板驳。
處理 Hash沖突
Hashtable 處理 Hash沖突 時通過單鏈表。碍拆。
涉及的基本概念
- 位運算
- 數(shù)組
- 哈希表
- 單鏈表
- Java transient 關(guān)鍵字原理
- Java 序列化若治、反序列化以及自定義序列化、反序列話邏輯（writeObject(ObjectOutputStream o)和readObject(ObjectInputStream i)）
存在未理解之處
Hashtable的count字段是什么時候初始化的感混？從賦值來看是通過readObject()方法來實現(xiàn)的端幼。但是具體實現(xiàn)需要回去取研讀下《Java編程思想》序列化章節(jié)內(nèi)容。
private transient int count;
未理解之處的解答
- Hashtable的count字段是什么時候初始化的弧满？因為該變量是類變量編譯的時候會自動賦值婆跑。可以總結(jié)下Java各種類型的變量庭呜。
模擬hash沖突
可以根據(jù)hash函數(shù)(key.hashCode() & 0x7FFFFFFF) % key數(shù)組現(xiàn)在的長度來模擬hash沖突滑进，只要key的hashCode是相同但是又不equals()的就是Hash沖突。如下實例：
public class MyKey implements Serializable {
private int i;
public MyKey(int i) {
this.i = i;
}
@Override
public int hashCode() {
if (i % 2 == 0) {
return 1;
} else {
return 2;
}
}
}
Hashtable處理hash沖突
如下實例：
public static void main(String[] args) {
Hashtable<MyKey, Integer> map = new Hashtable<>();
for (int i = 0; i < 11; i++) {
map.put(new MyKey(i), i);
}
map.get(new MyKey(1));
}
如何在IDEA調(diào)試模式下查看儲存結(jié)構(gòu)募谎？
Hashtable在IDEA下的默認視圖：
Java-Hashtable-data-structure-default-view.png
如何查看對象視圖扶关？如下圖操作：
Java-Hashtable-data-structure-object-view.png
對象視圖如下
Java-Hashtable-data-structure.png
從如上對象視圖可以看出Hashtable的table字段的具體存儲方式：
table數(shù)組中有兩個元素，一個是MyKey.i=10数冬，一個是Mykey.i=9,按如上查看對象視圖的方法查看這兩個元素的對象視圖查看java.util.Hashtable.Entry#next屬性节槐，可以看到MyKey.i=10的next屬性值是MyKey.i=8...
各元素的具體結(jié)構(gòu)如下：
MyKey.i=10.next -> MyKey.i=8
MyKey.i=8.next -> MyKey.i=0
MyKey.i=0.next -> MyKey.i=2
MyKey.i=2.next -> MyKey.i=4
MyKey.i=4.next -> MyKey.i=6
MyKey.i=6.next -> null
MyKey.i=9.next -> MyKey.i=1
MyKey.i=1.next -> MyKey.i=3
MyKey.i=3.next -> MyKey.i=5
MyKey.i=5.next -> MyKey.i=7
MyKey.i=7.next -> null
為什么順序不是按加入的順序的呢，而是一部分到過來的吉执？
因為Hashtable的key數(shù)組默認大小是11疯淫，當加入11個元素時，會自動擴容戳玫，在加入第8個元素時會rehash一次熙掺，rehash時是將新哈希表中的元素作為后面加入元素的next的，所有就會出現(xiàn)部分元素順序相反咕宿。
