HashMap本質是數(shù)組加鏈表，根據(jù)key取得hash值，然后計算出數(shù)組下標，如果多個key對應到同一個下標，就用鏈表串起來，新插入的在前面。
ConcurrentHashMap在HashMap的基礎上將數(shù)據(jù)分為多個segment，默認16個，然后每次操作對一個segment加鎖，避免多線程鎖的幾率，提高并發(fā)效率。
1. HashMap的數(shù)據(jù)結構
HashMap底層就是一個數(shù)組結構，數(shù)組中存放的是一個Entry對象，如果產(chǎn)生的hash沖突，這時候該位置存儲的就是一個鏈表了。
HashMap中Entry類的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;final int hash;/** * Creates new entry. */Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; // hash值沖突后存放在鏈表的下一個 key = k; hash = h;}.........} |
HashMap其實就是一個Entry數(shù)組，Entry對象中包含了鍵和值，其中next也是一個Entry對象，它就是用來處理hash沖突的，形成一個鏈表。
2. HashMap源碼分析
下面是HashMap類中的一些關鍵屬性：
|
1
2
3
4
5
|
transient Entry[] table; // 存儲元素的實體數(shù)組transient int size; // 存放元素的個數(shù)int threshold; // 臨界值，當實際大小超過臨界值時，會進行擴容，threshold = loadFactor * 容量final float loadFactor; // 加載因子transient int modCount; // 被修改的次數(shù) |
如果機器內(nèi)存足夠，并且想要提高查詢速度的話可以將加載因子設置小一點；相反如果機器內(nèi)存緊張，并且對查詢速度沒有什么要求的話可以將加載因子設置大一點。不過一般我們都不用去設置它，讓它取默認值0.75就好了。
下面是HashMap的幾個構造方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
public HashMap(int initialCapacity, float loadFactor) { // 確保數(shù)字合法 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); // Find a power of 2 >= initialCapacity int capacity = 1; // 初始容量 while (capacity < initialCapacity) // 確保容量為2的n次冪，使capacity為大于initialCapacity的最小的2的n次冪 capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init();}public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init();} |
默認初始容量為16，加載因子為0.75。上面代碼中13-15行，這段代碼的作用是確保容量為2的n次冪，使capacity為大于initialCapacity的最小的2的n次冪。
下面看看HashMap存儲數(shù)據(jù)的過程是怎樣的，首先看看HashMap的put方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public V put(K key, V value) { if (key == null) // 如果鍵為null的話，調用putForNullKey(value) return putForNullKey(value); int hash = hash(key.hashCode()); // 根據(jù)鍵的hashCode計算hash碼 int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 處理沖突的，如果hash值相同，則在該位置用鏈表存儲 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同則覆蓋并返回舊值 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null;} |
當我們往HashMap中put元素的時候，先根據(jù)key的hash值得到這個元素在數(shù)組中的位置，然后就可以把這個元素放到對應的位置中了。如果這個元素所在的位子上已經(jīng)存放有其他元素了，那么在同一個位子上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。從HashMap中get元素時，首先計算key的hashcode，找到數(shù)組中對應位置的某一元素，然后通過key的equals方法在對應位置的鏈表中找到需要的元素。
具體的實現(xiàn)是：當你的key為null時，會調用putForNullKey，HashMap允許key為null，這樣的對象是放在table[0]中。如果不為空，則調用int hash = hash(key.hashCode());這是HashMap的一個自定義的hash方法，在key.hashCode()基礎上進行二次hash，源碼如下：
|
1
2
3
4
|
static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);} |
得到hash碼之后就會通過hash碼去計算出應該存儲在數(shù)組中的索引，計算索引的函數(shù)如下：
|
1
2
3
|
static int indexFor(int h, int length) {return h & (length-1);} |
它通過 h & (table.length-1) 來得到該對象的保存位，而HashMap底層數(shù)組的長度總是 2 的n 次方，這是HashMap在速度上的優(yōu)化。當length總是 2 的n次方時，h & (length-1)運算等價于對length取模，也就是h % length，但是&比%具有更高的效率。當數(shù)組長度為2的n次冪的時候，不同的key算出的index相同的幾率較小，那么數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。
下面繼續(xù)回到put方法里面，前面已經(jīng)計算出索引的值了，看到第6到14行，如果數(shù)組中該索引的位置的鏈表已經(jīng)存在key相同的對象，則將其覆蓋掉并返回原先的值。如果沒有與key相同的鍵，則調用addEntry方法創(chuàng)建一個Entry對象，addEntry方法如下：
|
1
2
3
4
5
6
|
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; // 如果要加入的位置有值，將該位置原先的值設置為新entry的next,也就是新entry鏈表的下一個節(jié)點 table[bucketIndex] = new Entry<>(hash, key, value, e); if (size++ >= threshold) // 如果大于臨界值就擴容 resize(2 * table.length); // 以2的倍數(shù)擴容} |
參數(shù)bucketIndex就是indexFor函數(shù)計算出來的索引值，第2行代碼是取得數(shù)組中索引為bucketIndex的Entry對象，第3行就是用hash、key、value構建一個新的Entry對象放到索引為bucketIndex的位置，并且將該位置原先的對象設置為新對象的next構成鏈表。第4行和第5行就是判斷put后size是否達到了臨界值threshold，如果達到了臨界值就要進行擴容，HashMap擴容是擴為原來的兩倍。resize()方法如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; }8 Entry[] newTable = new Entry[newCapacity]; transfer(newTable); // 用來將原先table的元素全部移到newTable里面 table = newTable; // 再將newTable賦值給table threshold = (int)(newCapacity * loadFactor); // 重新計算臨界值} |
擴容是需要進行數(shù)組復制的，上面代碼中第10行為復制數(shù)組，復制數(shù)組是非常消耗性能的操作，所以如果我們已經(jīng)預知HashMap中元素的個數(shù)，那么預設元素的個數(shù)能夠有效的提高HashMap的性能。下面是get方法的源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public V get(Object key) { if (key == null)return getForNullKey();int hash = hash(key.hashCode());// 找到數(shù)組的下標，進行遍歷for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; // 找到則返回}return null; // 否則，返回null} |
以上這篇詳談HashMap和ConcurrentHashMap的區(qū)別(HashMap的底層源碼)就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
原文鏈接：http://www.cnblogs.com/jimmysun/p/7339032.html
