詳談HashMap和ConcurrentHashMap的區(qū)別(HashMap的底層源碼)

更新時間：2017年08月11日 08:37:00 投稿：jingxian

下面小編就為大家?guī)硪黄斦凥ashMap和ConcurrentHashMap的區(qū)別(HashMap的底層源碼)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

HashMap本質(zhì)是數(shù)組加鏈表，根據(jù)key取得hash值，然后計算出數(shù)組下標，如果多個key對應到同一個下標，就用鏈表串起來，新插入的在前面。

ConcurrentHashMap在HashMap的基礎上將數(shù)據(jù)分為多個segment，默認16個，然后每次操作對一個segment加鎖，避免多線程鎖的幾率，提高并發(fā)效率。

1. HashMap的數(shù)據(jù)結(jié)構(gòu)

HashMap底層就是一個數(shù)組結(jié)構(gòu)，數(shù)組中存放的是一個Entry對象，如果產(chǎn)生的hash沖突，這時候該位置存儲的就是一個鏈表了。

HashMap中Entry類的代碼：

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類中的一些關鍵屬性：

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的幾個構(gòu)造方法：

 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方法：

public V put(K key, V value) {
 if (key == null) // 如果鍵為null的話，調(diào)用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時，會調(diào)用putForNullKey，HashMap允許key為null，這樣的對象是放在table[0]中。如果不為空，則調(diào)用int hash = hash(key.hashCode());這是HashMap的一個自定義的hash方法，在key.hashCode()基礎上進行二次hash，源碼如下：

static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

得到hash碼之后就會通過hash碼去計算出應該存儲在數(shù)組中的索引，計算索引的函數(shù)如下：

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相同的鍵，則調(diào)用addEntry方法創(chuàng)建一個Entry對象，addEntry方法如下：

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構(gòu)建一個新的Entry對象放到索引為bucketIndex的位置，并且將該位置原先的對象設置為新對象的next構(gòu)成鏈表。第4行和第5行就是判斷put后size是否達到了臨界值threshold，如果達到了臨界值就要進行擴容，HashMap擴容是擴為原來的兩倍。resize()方法如下：

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方法的源碼：

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)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: