1. 前言
本文的源碼是基于JDK1.7垢乙，JDK1.8中HashMap的實現(xiàn)，引入了紅黑樹语卤，在后面的文章會寫到追逮。
后面還有一篇LinkedHashMap的解析：圖解LinkedHashMap原理。
2. 使用與實現(xiàn)
2.1 基本使用
HashMap很方便地為我們提供了key-value的形式存取數(shù)據(jù)粹舵，使用put方法存數(shù)據(jù)钮孵，get方法取數(shù)據(jù)。
Map<String, String> hashMap = new HashMap<String, String>();
hashMap.put("name", "josan");
String name = hashMap.get("name");
2.2 定義
HashMap繼承了Map接口眼滤，實現(xiàn)了Serializable等接口巴席。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table;
其實HashMap的數(shù)據(jù)是存在table數(shù)組中的，它是一個Entry數(shù)組诅需，Entry是HashMap的一個靜態(tài)內(nèi)部類漾唉，看看它的定義荧库。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
可見，Entry其實就是封裝了key和value赵刑，也就是我們put方法參數(shù)的key和value會被封裝成Entry分衫，然后放到table這個Entry數(shù)組中。但值得注意的是般此，它有一個類型為Entry的next蚪战，它是用于指向下一個Entry的引用，所以table中存儲的是Entry的單向鏈表铐懊。默認(rèn)參數(shù)的HashMap結(jié)構(gòu)如下圖所示：
2.3 構(gòu)造方法
HashMap一共有四個構(gòu)造方法屎勘，我們只看默認(rèn)的構(gòu)造方法。
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 找到第一個大于等于initialCapacity的2的平方的數(shù)
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
// HashMap擴容的閥值居扒，值為HashMap的當(dāng)前容量 * 負(fù)載因子，默認(rèn)為12 = 16 * 0.75
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 初始化table數(shù)組丑慎，這是HashMap真實的存儲容器
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// 該方法為空實現(xiàn)喜喂，主要是給子類去實現(xiàn)
init();
}
initialCapacity是HashMap的初始化容量(即初始化table時用到)，默認(rèn)為16竿裂。
loadFactor為負(fù)載因子玉吁，默認(rèn)為0.75。
threshold是HashMap進行擴容的閥值腻异，當(dāng)HashMap的存放的元素個數(shù)超過該值時进副，會進行擴容，它的值為HashMap的容量乘以負(fù)載因子悔常。比如影斑，HashMap的默認(rèn)閥值為16*0.75，即12机打。
HashMap提供了指定HashMap初始容量和負(fù)載因子的構(gòu)造函數(shù)矫户，這時候會首先找到第一個大于等于initialCapacity的2的平方數(shù)，用于作為初始化table残邀。至于為什么HashMap的容量總是2的平方數(shù)皆辽，后面會說到。
繼續(xù)看HashMap構(gòu)造方法芥挣，init是個空方法驱闷，主要給子類實現(xiàn)，比如LinkedHashMap在init初始化頭部節(jié)點空免，這里暫時先不介紹空另。
2.4 put方法
public V put(K key, V value) {
// 對key為null的處理
if (key == null)
return putForNullKey(value);
// 根據(jù)key算出hash值
int hash = hash(key);
// 根據(jù)hash值和HashMap容量算出在table中應(yīng)該存儲的下標(biāo)i
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 先判斷hash值是否一樣，如果一樣蹋砚，再判斷key是否一樣
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
首先痹换，如果key為null調(diào)用putForNullKey來處理征字，我們暫時先不關(guān)注，后面會講到娇豫。然后調(diào)用hash方法匙姜，根據(jù)key來算得hash值，得到hash值以后冯痢，調(diào)用indexFor方法氮昧，去算出當(dāng)前值在table數(shù)組的下標(biāo)，我們可以來看看indexFor方法：
static int indexFor(int h, int length) {
return h & (length-1);
}
這其實就是mod取余的一種替換方式浦楣，相當(dāng)于h%(lenght-1)袖肥，其中h為hash值，length為HashMap的當(dāng)前長度振劳。而&是位運算椎组，效率要高于%。至于為什么是跟length-1進行&的位運算历恐，是因為length為2的冪次方寸癌，即一定是偶數(shù)，偶數(shù)減1弱贼，即是奇數(shù)蒸苇，這樣保證了（length-1）在二進制中最低位是1，而&運算結(jié)果的最低位是1還是0完全取決于hash值二進制的最低位吮旅。如果length為奇數(shù)溪烤，則length-1則為偶數(shù)，則length-1二進制的最低位橫為0庇勃，則&位運算的結(jié)果最低位橫為0檬嘀，即橫為偶數(shù)。這樣table數(shù)組就只可能在偶數(shù)下標(biāo)的位置存儲了數(shù)據(jù)责嚷，浪費了所有奇數(shù)下標(biāo)的位置枪眉，這樣也更容易產(chǎn)生hash沖突。這也是HashMap的容量為什么總是2的平方數(shù)的原因再层。我們來用表格對比length=15和length=16的情況
我們再回到put方法中贸铜，我們已經(jīng)根據(jù)key得到hash值，然后根據(jù)hash值算出在table的存儲下標(biāo)了聂受，接著就是這段for代碼了：
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 先判斷hash值是否一樣蒿秦，如果一樣，再判斷key是否一樣
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
首先取出table中下標(biāo)為i的Entry蛋济，然后判斷該Entry的hash值和key是否和要存儲的hash值和key相同棍鳖，如果相同，則表示要存儲的key已經(jīng)存在于HashMap，這時候只需要替換已存的Entry的value值即可渡处。如果不相同镜悉，則取e.next繼續(xù)判斷，其實就是遍歷table中下標(biāo)為i的Entry單向鏈表医瘫，找是否有相同的key已經(jīng)在HashMap中侣肄，如果有，就替換value為最新的值醇份，所以HashMap中只能存儲唯一的key稼锅。
關(guān)于需要同時比較hash值和key有以下兩點需要注意
- 為什么比較了hash值還需要比較key：因為不同對象的hash值可能一樣
- 為什么不只比較equal：因為equal可能被重寫了，重寫后的equal的效率要低于hash的直接比較
假設(shè)我們是第一次put僚纷，則整個for循環(huán)體都不會執(zhí)行矩距，我們繼續(xù)往下看put方法。
modCount++;
addEntry(hash, key, value, i);
return null;
這里主要看addEntry方法怖竭，它應(yīng)該就是把key和value封裝成Entry锥债，然后加入到table中的實現(xiàn)。來看看它的方法體：
void addEntry(int hash, K key, V value, int bucketIndex) {
// 當(dāng)前HashMap存儲元素的個數(shù)大于HashMap擴容的閥值痊臭，則進行擴容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 使用key哮肚、value創(chuàng)建Entry并加入到table中
createEntry(hash, key, value, bucketIndex);
}
這里牽涉到了HashMap的擴容，我們先不討論擴容趣兄，后面會講到。然后調(diào)用了createEntry方法悼嫉，它的實現(xiàn)如下：
void createEntry(int hash, K key, V value, int bucketIndex) {
// 取出table中下標(biāo)為bucketIndex的Entry
Entry<K,V> e = table[bucketIndex];
// 利用key艇潭、value來構(gòu)建新的Entry
// 并且之前存放在table[bucketIndex]處的Entry作為新Entry的next
// 把新創(chuàng)建的Entry放到table[bucketIndex]位置
table[bucketIndex] = new Entry<>(hash, key, value, e);
// HashMap當(dāng)前存儲的元素個數(shù)size自增
size++;
}
這里其實就是根據(jù)hash、key戏蔑、value以及table中下標(biāo)為bucketIndex的Entry去構(gòu)建一個新的Entry蹋凝，其中table中下標(biāo)為bucketIndex的Entry作為新Entry的next，這也說明了总棵，當(dāng)hash沖突時鳍寂，采用的拉鏈法來解決hash沖突的，并且是把新元素是插入到單邊表的表頭情龄。如下所示：
2.5 擴容
如果當(dāng)前HashMap中存儲的元素個數(shù)達(dá)到擴容的閥值迄汛，且當(dāng)前要存在的值在table中要存放的位置已經(jīng)有存值時，怎么處理的骤视？我們再來看看addEntry方法中的擴容相關(guān)代碼：
if ((size >= threshold) && (null != table[bucketIndex])) {
// 將table表的長度增加到之前的兩倍
resize(2 * table.length);
// 重新計算哈希值
hash = (null != key) ? hash(key) : 0;
// 從新計算新增元素在擴容后的table中應(yīng)該存放的index
bucketIndex = indexFor(hash, table.length);
}
接下來我們看看resize是如何將table增加長度的：
void resize(int newCapacity) {
// 保存老的table和老table的長度
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 創(chuàng)建一個新的table鞍爱，長度為之前的兩倍
Entry[] newTable = new Entry[newCapacity];
// hash有關(guān)
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// 這里進行異或運算，一般為true
boolean rehash = oldAltHashing ^ useAltHashing;
// 將老table的原有數(shù)據(jù)专酗，從新存儲到新table中
transfer(newTable, rehash);
// 使用新table
table = newTable;
// 擴容后的HashMap的擴容閥門值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
再來看看transfer方法是如何將把老table的數(shù)據(jù)睹逃，轉(zhuǎn)到擴容后的table中的：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍歷老的table數(shù)組
for (Entry<K,V> e : table) {
// 遍歷老table數(shù)組中存儲每條單項鏈表
while(null != e) {
// 取出老table中每個Entry
Entry<K,V> next = e.next;
if (rehash) {
//重新計算hash
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根據(jù)hash值，算出老table中的Entry應(yīng)該在新table中存儲的index
int i = indexFor(e.hash, newCapacity);
// 讓老table轉(zhuǎn)移的Entry的next指向新table中它應(yīng)該存儲的位置
// 即插入到了新table中index處單鏈表的表頭
e.next = newTable[i];
// 將老table取出的entry祷肯，放入到新table中
newTable[i] = e;
// 繼續(xù)取老talbe的下一個Entry
e = next;
}
}
}
從上面易知沉填，擴容就是先創(chuàng)建一個長度為原來2倍的新table疗隶，然后通過遍歷的方式，將老table的數(shù)據(jù)翼闹，重新計算hash并存儲到新table的適當(dāng)位置斑鼻，最后使用新的table，并重新計算HashMap的擴容閥值橄碾。
2.6 get方法
public V get(Object key) {
// 當(dāng)key為null, 這里不討論卵沉，后面統(tǒng)一講
if (key == null)
return getForNullKey();
// 根據(jù)key得到key對應(yīng)的Entry
Entry<K,V> entry = getEntry(key);
//
return null == entry ? null : entry.getValue();
}
然后我們看看getEntry是如果通過key取到Entry的：
final Entry<K,V> getEntry(Object key) {
// 根據(jù)key算出hash
int hash = (key == null) ? 0 : hash(key);
// 先算出hash在table中存儲的index，然后遍歷table中下標(biāo)為index的單向鏈表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 如果hash和key都相同法牲，則把Entry返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
取值史汗，最簡單粗暴的方式肯定是遍歷table，并且遍歷table中存放的單向鏈表拒垃，這樣的話停撞，get的時間復(fù)雜度就是O(n的平方)，但是HashMap的put本身就是有規(guī)律的存儲悼瓮，所以戈毒，取值時，可以按照規(guī)律去降低時間復(fù)雜度横堡。上面的代碼比較簡單埋市，其實節(jié)約的就是遍歷table的過程，因為我們可以用key的hash值算出key對應(yīng)的Entry所在鏈表在在table的下標(biāo)命贴。這樣道宅，我們只要遍歷單向鏈表就可以了，時間復(fù)雜度降低到O(n)胸蛛。
get方法的取值過程如下圖所示：
2.7 使用entrySet取數(shù)據(jù)
HashMap除了提供get方法污茵，通過key來取數(shù)據(jù)的方式，還提供了entrySet方法來遍歷HashMap的方式取數(shù)據(jù)葬项。如下：
Map<String, String> hashMap = new HashMap<String, String>();
hashMap.put("name1", "josan1");
hashMap.put("name2", "josan2");
hashMap.put("name3", "josan3");
Set<Entry<String, String>> set = hashMap.entrySet();
Iterator<Entry<String, String>> iterator = set.iterator();
while(iterator.hasNext()) {
Entry entry = iterator.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
結(jié)果可知泞当，HashMap存儲數(shù)據(jù)是無序的。
我們這里主要是討論民珍，它是如何來完成遍歷的襟士。HashMap重寫了entrySet。
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
// 相當(dāng)于返回了new EntrySet
return es != null ? es : (entrySet = new EntrySet());
}
代碼比較簡單嚷量，直接new EntrySet對象并返回敌蜂，EntrySet是HashMap的內(nèi)部類，注意津肛，不是靜態(tài)內(nèi)部類章喉，所以它的對象會默認(rèn)持有外部類HashMap的對象，定義如下：
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
// 重寫了iterator方法
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
// 不相關(guān)代碼
...
}
我們主要是關(guān)心iterator方法，EntrySet 重寫了該方法秸脱，所以調(diào)用Set的iterator方法落包，會調(diào)用到這個重寫的方法，方法內(nèi)部很簡單單摊唇，直接調(diào)用了newEntryIterator方法咐蝇，返回了一個自定義的迭代器。我們看看newEntryIterator：
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
可看到巷查，直接new了一個EntryIterator對象返回有序，看看EntryIterator的定義：
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
// 重寫了next方法
public Map.Entry<K,V> next() {
return nextEntry();
}
}
EntryIterator 是繼承了HashIterator，我們再來看看HashIterator的定義：
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // 下一個要返回的Entry
int expectedModCount; // For fast-fail
int index; // 當(dāng)前table上下標(biāo)
Entry<K,V> current; // 當(dāng)前的Entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
// 不相關(guān)
......
}
我們先看構(gòu)造方法：
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
// 這里其實就是遍歷table岛请，找到第一個返回的Entry next
// 該值是table數(shù)組的第一個有值的Entry纪挎，所以也肯定是單向鏈表的表頭
while (index < t.length && (next = t[index++]) == null)
;
}
}
以上免钻，就是我們調(diào)用了Iterator<Entry<String, String>> iterator = set.iterator();代碼所執(zhí)行的過程。
接下來就是使用while(iterator.hasNext())去循環(huán)判斷是否有下一個Entry，EntryIterator沒有實現(xiàn)hasNext方法虎忌，所以也是調(diào)用的HashIterator中的hasNext布卡，我們來看看該方法：
public final boolean hasNext() {
// 如果下一個返回的Entry不為null躯护，則返回true
return next != null;
}
該方法很簡單独撇，就是判斷下一個要返回的Entry next是否為null，如果HashMap中有元素岸霹，那么第一次調(diào)用hasNext時next肯定不為null疾层，且是table數(shù)組的第一個有值的Entry，也就是第一條單向鏈表的表頭Entry贡避。
接下來痛黎，就到了調(diào)用EntryIterator.next去取下一個Entry了，EntryIterator對next方法進行了重寫贸桶，看看該方法：
public Map.Entry<K,V> next() {
return nextEntry();
}
直接調(diào)用了nextEntry方法舅逸，返回下一個Entry桌肴，但是EntryIterator并沒有重寫nextEntry皇筛，所以還是調(diào)用的HashIterator的nextEntry方法，方法如下：
final Entry<K,V> nextEntry() {
// 保存下一個需要返回的Entry坠七，作為返回結(jié)果
Entry<K,V> e = next;
// 如果遍歷到table上單向鏈表的最后一個元素時
if ((next = e.next) == null) {
Entry[] t = table;
// 繼續(xù)往下尋找table上有元素的下標(biāo)
// 并且把下一個talbe上有單向鏈表的表頭水醋，作為下一個返回的Entry next
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
其實nextEntry的主要作用有兩點
- 把當(dāng)前遍歷到的Entry返回
- 準(zhǔn)備好下一個需要返回的Entry
如果當(dāng)前返回的Entry不是單向鏈表的最后一個元素，那只要讓下一個返回的Entrynext為當(dāng)前Entry的next屬性（下圖紅色過程）彪置；如果當(dāng)前返回的Entry是單向鏈表的最后一個元素拄踪，那么它就沒有next屬性了，所以要尋找下一個table上有單向鏈表的表頭（下圖綠色過程）
可知拳魁，HashMap的遍歷惶桐，是先遍歷table，然后再遍歷table上每一條單向鏈表，如上述的HashMap遍歷出來的順序就是Entry1姚糊、Entry2....Entry6贿衍，但顯然，這不是插入的順序救恨，所以說：HashMap是無序的贸辈。
2.8 對key為null的處理
先看put方法時，key為null
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//其他不相關(guān)代碼
.......
}
看看putForNullKey的處理
private V putForNullKey(V value) {
// 遍歷table[0]上的單向鏈表
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 如果有key為null的Entry肠槽，則替換該Entry中的value
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果沒有key為null的Entry擎淤，則構(gòu)造一個hash為0、key為null秸仙、value為真實值的Entry
// 插入到table[0]上單向鏈表的頭部
addEntry(0, null, value, 0);
return null;
}
其實key為null的put過程嘴拢，跟普通key值的put過程很類似，區(qū)別在于key為null的hash為0筋栋，存放在table[0]的單向鏈表上而已炊汤。
我們再來看看對于key為null的取值：
public V get(Object key) {
if (key == null)
return getForNullKey();
//不相關(guān)的代碼
......
}
取值就是通過getForNullKey方法來完成的，代碼如下：
private V getForNullKey() {
// 遍歷table[0]上的單向鏈表
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 如果key為null弊攘，則返回該Entry的value值
if (e.key == null)
return e.value;
}
return null;
}
key為null的取值抢腐，跟普通key的取值也很類似，只是不需要去算hash和確定存儲在table上的index而已襟交，而是直接遍歷talbe[0]迈倍。
所以，在HashMap中捣域，不允許key重復(fù)啼染，而key為null的情況，只允許一個key為null的Entry焕梅，并且存儲在table[0]的單向鏈表上迹鹅。
2.9 remove方法
HashMap提供了remove方法，用于根據(jù)key移除HashMap中對應(yīng)的Entry
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
首先調(diào)用removeEntryForKey方法把key對應(yīng)的Entry從HashMap中移除贞言。然后把移除的值返回斜棚。我們繼續(xù)看removeEntryForKey方法：
final Entry<K,V> removeEntryForKey(Object key) {
// 算出hash
int hash = (key == null) ? 0 : hash(key);
// 得到在table中的index
int i = indexFor(hash, table.length);
// 當(dāng)前結(jié)點的上一個結(jié)點，初始為table[index]上單向鏈表的頭結(jié)點
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
// 得到下一個結(jié)點
Entry<K,V> next = e.next;
Object k;
// 如果找到了刪除的結(jié)點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
// 如果是table上的單向鏈表的頭結(jié)點该窗，則直接讓把該結(jié)點的next結(jié)點放到頭結(jié)點
if (prev == e)
table[i] = next;
else
// 如果不是單向鏈表的頭結(jié)點弟蚀，則把上一個結(jié)點的next指向本結(jié)點的next
prev.next = next;
// 空實現(xiàn)
e.recordRemoval(this);
return e;
}
// 沒有找到刪除的結(jié)點，繼續(xù)往下找
prev = e;
e = next;
}
return e;
}
其實邏輯也很簡單酗失，先根據(jù)key算出hash义钉，然后根據(jù)hash得到在table上的index，再遍歷talbe[index]的單向鏈表规肴，這時候需要看要刪除的元素是否就是單向鏈表的表頭捶闸，如果是夜畴，則直接讓table[index]=next，即刪除了需要刪除的元素删壮；如果不是單向鏈表的頭斩启，那表示有前面的結(jié)點，則讓pre.next = next醉锅，也刪除了需要刪除的元素兔簇。
2.10 線程安全問題
由前面HashMap的put和get方法分析可得，put和get方法真實操作的都是Entry[] table這個數(shù)組硬耍，而所有操作都沒有進行同步處理垄琐，所以HashMap是線程不安全的。如果想要實現(xiàn)線程安全经柴，推薦使用ConcurrentHashMap狸窘。
3 總結(jié)
- HashMap是基于哈希表實現(xiàn)的，用Entry[]來存儲數(shù)據(jù)坯认，而Entry中封裝了key翻擒、value、hash以及Entry類型的next
- HashMap存儲數(shù)據(jù)是無序的
- hash沖突是通過拉鏈法解決的
- HashMap的容量永遠(yuǎn)為2的冪次方牛哺，有利于哈希表的散列
- HashMap不支持存儲多個相同的key陋气，且只保存一個key為null的值，多個會覆蓋
- put過程引润，是先通過key算出hash巩趁，然后用hash算出應(yīng)該存儲在table中的index，然后遍歷table[index]淳附，看是否有相同的key存在议慰，存在，則更新value奴曙；不存在則插入到table[index]單向鏈表的表頭别凹，時間復(fù)雜度為O(n)
- get過程，通過key算出hash洽糟，然后用hash算出應(yīng)該存儲在table中的index炉菲，然后遍歷table[index]，然后比對key脊框，找到相同的key颁督，則取出其value践啄，時間復(fù)雜度為O(n)
- HashMap是線程不安全的浇雹，如果有線程安全需求，推薦使用ConcurrentHashMap屿讽。
