HashMap和HashTable，HashMap中key和value的原理

HashMap和HashTable，HashMap中key和value的原理 - 跳刀的兔子 - 部落格園

一、HashMap和HashTable

差別：

1.HashTable是Dictionary的子類,HashMap是Map接口的一個實作類;

2.HashTable中的方法是同步的,而HashMap中方法是非同步的.也就是說,在多線程的情況下用HashMap需要額外的同步機制.

Map Collections.synchronziedMap(Map m)這個方法傳回一個同步的Map,封裝了底層的HashMap方法,使得多線程安全.

或者采用ConcurrentMap接口;

3.HashMap中,鍵和值都可以為null(null鍵隻能有一個)，HashTable不允許為null。當get()方法時傳回null，即表示沒有該鍵，也可以表示該鍵對應的值為null。是以判斷HashMap裡是否存在某個鍵時，不能用get()方法，應該用containsKey()方法

相同：

1.有兩個參數影響性能：初始容量和加載因子。

初始容量：哈希表建立時的容量，初始容量設定太高可能會浪費空間；

加載因子：對哈希表在其容量自動增加之前可以達到多滿的一個尺度（預設為.75），加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本。

當哈希表中的條目數超出了加載因子與目前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建内部資料結構）。

2.所有類的“Collection視圖方法”傳回的Collection的iterator方法傳回的疊代器是快速失敗的。

二、HashMap中key和value的原理

HashMap是基于哈希表的Map接口的非同步實作。此實作提供所有可選的映射操作，并允許使用null值和null鍵。HashMap實際上是一個“連結清單散列”的資料結構，即數組和連結清單的結合體。HashMap底層就是一個數組結構，數組中的每一項又是一個連結清單。當建立一個HashMap的時候，就會初始化一個數組。每個Map.Entry是一個Key-Value對，也是數組中的元素，它持有指向下一個元素的引用，這就構成了連結清單。 HashMap的存取實作：

   1) 存儲：

　　當我們往HashMap中put元素的時候，先根據key的hashCode重新計算hash值，根據hash值得到這個元素在數組中的位置（即下标），如果數組該位置上已經存放有其他元素了，那麼在這個位置上的元素将以連結清單的形式存放，新加入的放在鍊頭，最先加入的放在鍊尾。如果數組該位置上沒有元素，就直接将該元素放到此數組中的該位置上。

當系統決定存儲HashMap中的key-value對時，完全沒有考慮Entry中的value，僅僅隻是根據key來計算并決定每個Entry的存儲位置。我們完全可以把 Map 集合中的 value 當成 key 的附屬，當系統決定了 key 的存儲位置之後，value 随之儲存在那裡即可。

   hash(int h)--計算hash值的方法根據key的hashCode重新計算一次散列。此算法加入了高位計算，防止低位不變，高位變化時，造成的hash沖突。

  2) 讀取：

　　從HashMap中get元素時，首先計算key的hashCode，找到數組中對應位置的某一進制素，然後通過key的equals方法在對應位置的連結清單中找到需要的元素。

3）Fail-Fast機制：

   我們知道java.util.HashMap不是線程安全的，是以如果在使用疊代器的過程中有其他線程修改了map，那麼将抛出ConcurrentModificationException，這就是所謂fail-fast政策。

   這一政策在源碼中的實作是通過modCount域，modCount顧名思義就是修改次數，對HashMap内容的修改都将增加這個值，那麼在疊代器初始化過程中會将這個值賦給疊代器的expectedModCount。在疊代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經有其他線程修改了Map： 注意到modCount聲明為volatile，保證線程之間修改的可見性。

作者：少帥