HashMap詳講

HashMap詳講hashing散列法或哈希法的概念什么是HashMap以及HashMap的構成HashMap的基本存儲原理以及存儲內容的組成HashMap的工作原理以及存取方法過程HashMap中的碰撞探測collision detection以及碰撞的解決方法如何重新調整HashMap的大小不可變對象的好處HashMap多線程的條件競爭

下面就根據這些問題講解一下HashMap

hashing(散列法或哈希法)的概念

可以自行百度

什么是HashMap以及HashMap的構成

HashMap是基于哈希表的Map接口的非同步實現。此實現提供所有可選的映射操作，并允許使用null值和null鍵。HashMap儲存的是鍵值對，HashMap很快。此類不保證映射的順序，特別是它不保證該順序恒久不變。

HashMap實際上是一個“鏈表散列”的數據結構，即數組和鏈表的結合體。

數組：存儲區間連續，占用內存嚴重，尋址容易，插入刪除困難； 鏈表：存儲區間離散，占用內存比較寬松，尋址困難，插入刪除容易； Hashmap綜合應用了這兩種數據結構，實現了尋址容易，插入刪除也容易。

hashMap的結構示意圖如下：

HashMap的基本存儲原理以及存儲內容的組成

基本原理：先聲明一個下標范圍比較大的數組來存儲元素。另外設計一個哈希函數（也叫做散列函數）來獲得每一個元素的Key（關鍵字）的函數值（即數組下標，hash值）相對應，數組存儲的元素是一個Entry類，這個類有三個數據域，key、value（鍵值對），next(指向下一個Entry)。 例如， 第一個鍵值對A進來。通過計算其key的hash得到的index=0。記做:Entry[0] = A。 第二個鍵值對B，通過計算其index也等于0， HashMap會將B.next =A,Entry[0] =B, 第三個鍵值對 C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發現index=0的地方事實上存取了A,B,C三個鍵值對,它們通過next這個屬性鏈接在一起。我們可以將這個地方稱為桶。 對于不同的元素，可能計算出了相同的函數值，這樣就產生了“沖突”，這就需要解決沖突，“直接定址”與“解決沖突”是哈希表的兩大特點。

HashMap的工作原理以及存取方法過程

HashMap的工作原理 ：HashMap是基于散列法（又稱哈希法hashing）的原理，使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法，返回的hashCode用于找到bucket（桶）位置來儲存Entry對象。”HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。并不是僅僅只在bucket中存儲值。

HashMap具體的存取過程如下： put鍵值對的方法的過程是： 1、獲取key ； 2、通過hash函數得到hash值； int hash=key.hashCode(); //獲取key的hashCode，這個值是一個固定的int值

3、得到桶號(一般都為hash值對桶數求模) ，也即數組下標int index=hash%Entry[].length。//獲取數組下標：key的hash值對Entry數組長度進行取余

4、 存放key和value在桶內。 table[index]=Entry對象；

get值方法的過程是: 1、獲取key 2、通過hash函數得到hash值 int hash=key.hashCode();

3、得到桶號(一般都為hash值對桶數求模) int index =hash%Entry[].length;

4、比較桶的內部元素是否與key相等，若都不相等，則沒有找到。

5、取出相等的記錄的value。

HashMap中直接地址用hash函數生成；解決沖突，用比較函數解決。如果每個桶內部只有一個元素，那么查找的時候只有一次比較。當許多桶內沒有值時，許多查詢就會更快了(指查不到的時候)。

HashMap中的碰撞探測(collision detection)以及碰撞的解決方法

當兩個對象的hashcode相同時，它們的bucket位置相同，‘碰撞’會發生。因為HashMap使用LinkedList存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在LinkedList中。這兩個對象就算hashcode相同，但是它們可能并不相等。 那如何獲取這兩個對象的值呢？當我們調用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，遍歷LinkedList直到找到值對象。找到bucket位置之后，會調用keys.equals()方法去找到LinkedList中正確的節點，最終找到要找的值對象使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。

如何重新調整HashMap的大小

“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？” 默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創建原來HashMap大小的兩倍的bucket數組，來重新調整map的大小，并將原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。

不可變對象的好處

上面說到使用包裝類時刻作為鍵的原因是 String, Interger這樣的wrapper類作為HashMap的鍵是很合適的，而且String最為常用。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。

HashMap多線程的條件競爭

重新調整HashMap大小存在什么問題嗎？”在多線程的情況下，可能產生條件競爭(race condition)。因為如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，存儲在LinkedList中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在LinkedList的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了，那么就死循環了。(在多線程的情況下，為什么還要使用HashMap呢？不懂)

我們也可以使用自定義的對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經滿足了作為鍵的條件，因為當它創建之后就已經不能改變了。

我們可以使用CocurrentHashMap來代替HashTable嗎？這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道HashTable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性。