真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

Java集合系列之HashMap源碼分析

前面我們已經(jīng)分析了ArrayList和LinkedList這兩個集合,我們知道ArrayList是基于數(shù)組實現(xiàn)的,LinkedList是基于鏈表實現(xiàn)的。它們各自有自己的優(yōu)劣勢,例如ArrayList在定位查找元素時會優(yōu)于LinkedList,而LinkedList在添加刪除元素時會優(yōu)于ArrayList。而本篇介紹的HashMap綜合了二者的優(yōu)勢,它的底層是基于哈希表實現(xiàn)的,如果不考慮哈希沖突的話,HashMap在增刪改查操作上的時間復雜度都能夠達到驚人的O(1)。我們先看看它所基于的哈希表的結(jié)構(gòu)。

成都創(chuàng)新互聯(lián)致力于成都網(wǎng)站設(shè)計、網(wǎng)站制作,成都網(wǎng)站設(shè)計,集團網(wǎng)站建設(shè)等服務(wù)標準化,推過標準化降低中小企業(yè)的建站的成本,并持續(xù)提升建站的定制化服務(wù)水平進行質(zhì)量交付,讓企業(yè)網(wǎng)站從市場競爭中脫穎而出。 選擇成都創(chuàng)新互聯(lián),就選擇了安全、穩(wěn)定、美觀的網(wǎng)站建設(shè)服務(wù)!

Java集合系列之HashMap源碼分析

從上圖中可以看到,哈希表是由數(shù)組和鏈表共同構(gòu)成的一種結(jié)構(gòu),當然上圖是一個不好的示例,一個好的哈希函數(shù)應(yīng)該要盡量平均元素在數(shù)組中的分布,減少哈希沖突從而減小鏈表的長度。鏈表的長度越長,意味著在查找時需要遍歷的結(jié)點越多,哈希表的性能也就越差。接下來我們來看下HashMap的部分成員變量。

//默認初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//默認最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//默認加載因子, 指哈希表可以達到多滿的尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//空的哈希表
static final Entry<?,?>[] EMPTY_TABLE = {};

//實際使用的哈希表
transient Entry[] table = (Entry[]) EMPTY_TABLE;

//HashMap大小, 即HashMap存儲的鍵值對數(shù)量
transient int size;

//鍵值對的閾值, 用于判斷是否需要擴增哈希表容量
int threshold;

//加載因子
final float loadFactor;

//修改次數(shù), 用于fail-fast機制
transient int modCount;

//使用替代哈希的默認閥值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//隨機的哈希種子, 有助于減少哈希碰撞的次數(shù)
transient int hashSeed = 0;

由成員變量中看到,HashMap默認的初始容量為16,默認的加載因子是0.75。而threshold是集合能夠存儲的鍵值對的閥值,默認是初始容量*加載因子,也就是16*0.75=12,當鍵值對要超過閥值時,意味著這時候的哈希表已處于飽和狀態(tài),再繼續(xù)添加元素就會增加哈希沖突,從而使HashMap的性能下降。這時會觸發(fā)自動擴容機制,以保證HashMap的性能。我們還可以看到哈希表其實就是一個Entry數(shù)組,數(shù)組存放的每個Entry都是單向鏈表的頭結(jié)點。這個Entry是HashMap的靜態(tài)內(nèi)部類,來看看Entry的成員變量。

static class Entry implements Map.Entry {
  final K key;   //鍵
  V value;     //值
  Entry next; //下一個Entry的引用
  int hash;     //哈希碼
  
  ...        //省略下面代碼
}

一個Entry實例就是一個鍵值對,里面包含了key和value,同時每個Entry實例還有一個指向下一個Entry實例的引用。為了避免重復計算,每個Entry實例還存放了對應(yīng)的Hash碼??梢哉fEntry數(shù)組就是HashMap的核心,所有的操作都是針對這個數(shù)組來完成的。由于HashMap源碼比較長,不可能面面俱到的介紹它的所有方法,因此我們只抓住重點來進行介紹。接下來我們將以問題為導向,針對下面幾個問題深入探究HashMap的內(nèi)部機制。

1. HashMap在構(gòu)造時做了哪些操作?

//構(gòu)造器, 傳入初始化容量和加載因子
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0) {
    throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  }
  //如果初始化容量大于最大容量, 就把它設(shè)為最大容量
  if (initialCapacity > MAXIMUM_CAPACITY) {
    initialCapacity = MAXIMUM_CAPACITY;
  }
  //如果加載因子小于0或者加載因子不是浮點數(shù), 則拋出異常
  if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
    throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  }
  //設(shè)置加載因子
  this.loadFactor = loadFactor;
  //閾值為初始化容量
  threshold = initialCapacity;
  init();
}

void init() {}

所有的構(gòu)造器都會調(diào)用到這個構(gòu)造器,在這個構(gòu)造器中我們看到除了對參數(shù)做一些校驗之外,它就做了兩件事,設(shè)置加載因子為傳入的加載因子,設(shè)置閥值為傳入的初始化大小。而init方法是空的,啥也沒做。注意,這時候并沒有根據(jù)傳入的初始化大小去新建一個Entry數(shù)組哦。那在什么時候再去新建數(shù)組呢?繼續(xù)往下看。

2. HashMap添加鍵值對時會進行什么操作?

//放置key-value鍵值對到HashMap中
public V put(K key, V value) {
  //如果哈希表沒有初始化就進行初始化
  if (table == EMPTY_TABLE) {
    //初始化哈希表
    inflateTable(threshold);
  }
  if (key == null) {
    return putForNullKey(value);
  }
  //計算key的hash碼
  int hash = hash(key);
  //根據(jù)hash碼定位在哈希表的位置
  int i = indexFor(hash, table.length);
  for (Entry e = table[i]; e != null; e = e.next) {
    Object k;
    //如果對應(yīng)的key已經(jīng)存在, 就替換它的value值, 并返回原先的value值
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      V oldValue = e.value;
      e.value = value;
      e.recordAccess(this);
      return oldValue;
    }
  }
  modCount++;
  //如果沒有對應(yīng)的key就添加Entry到HashMap中
  addEntry(hash, key, value, i);
  //添加成功返回null
  return null;
}

看到,在添加鍵值對時會先檢查哈希表是否是個空表,如果是空表就進行初始化。之后再進行后續(xù)操作,調(diào)用哈希函數(shù)計算傳入的key的Hash碼。根據(jù)hash碼定位到Entry數(shù)組的指定槽位,然后對該槽位的單向鏈表進行遍歷,如果傳入的已經(jīng)存在了就進行替換操作,否則就新建一個Entry添加到哈希表中。

3. 哈希表是怎樣初始化的?

//初始化哈希表, 會對哈希表容量進行膨脹, 因為有可能傳入的容量不是2的冪
private void inflateTable(int toSize) {
  //哈希表容量必須是2的次冪
  int capacity = roundUpToPowerOf2(toSize);
  //設(shè)置閥值, 這里一般是取capacity*loadFactor
  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  //新建指定容量的哈希表
  table = new Entry[capacity];
  //初始化哈希種子
  initHashSeedAsNeeded(capacity);
}

上面我們知道,在構(gòu)造HashMap時不會新建Entry數(shù)組,而是在put操作時檢查當前哈希表是否是個空表,如果是空表就調(diào)用inflateTable方法進行初始化。上面貼出了這個方法的代碼,可以看到方法內(nèi)部會重新計算Entry數(shù)組的容量,因為在構(gòu)造HashMap時傳入的初始化大小可能不是2的冪,因此要將這個數(shù)轉(zhuǎn)換成2的冪再去根據(jù)新的容量新建Entry數(shù)組。初始化哈希表時再次重新設(shè)置閥值,閥值一般是capacity*loadFactor。此外,在初始化哈希表時還會去初始化哈希種子(hashSeed),這個hashSeed用于優(yōu)化哈希函數(shù),默認為0是不使用替代哈希算法,但是也可以自己去設(shè)置hashSeed的值,以達到優(yōu)化效果。具體下面會講到。

4. HashMap在什么時候判斷是否要擴容,以及它是怎樣擴容的?

//添加Entry方法, 先判斷是否要擴容
void addEntry(int hash, K key, V value, int bucketIndex) {
  //如果HashMap的大小大于閥值并且哈希表對應(yīng)槽位的值不為空
  if ((size >= threshold) && (null != table[bucketIndex])) {
    //因為HashMap的大小大于閥值, 表明即將發(fā)生哈希沖突, 所以進行擴容
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }
  //在這里表明HashMap的大小沒有超過閥值, 所以不需要擴容
  createEntry(hash, key, value, bucketIndex);
}

//對哈希表進行擴容
void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  //如果當前已經(jīng)是最大容量就只能增大閥值了
  if (oldCapacity == MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return;
  }
  //否則就進行擴容
  Entry[] newTable = new Entry[newCapacity];
  //遷移哈希表的方法
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  //將當前哈希表設(shè)置為新的哈希表
  table = newTable;
  //更新哈希表閾值
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

在調(diào)用put方法添加一個鍵值對時,如果集合中沒有存在的key就去調(diào)用addEntry方法新建一個Entry??吹缴厦尜N出的addEntry代碼,在新建一個Entry之前會先判斷當前集合元素的大小是否超過了閥值,如果超過了閥值就調(diào)用resize進行擴容。傳入的新的容量是原來哈希表的兩倍,在resize方法內(nèi)部會新建一個容量為原先的2倍的Entry數(shù)組。然后將舊的哈希表里面的元素全部遷移到新的哈希表,其中可能會進行再哈希,根據(jù)initHashSeedAsNeeded方法計算的值來確定是否進行再哈希。完成哈希表的遷移之后,將當前哈希表替換為新的,最后再根據(jù)新的哈希表容量來重新計算HashMap的閥值。

5. 為什么Entry數(shù)組的大小必須為2的冪?

 //返回哈希碼對應(yīng)的數(shù)組下標
 static int indexFor(int h, int length) {
   return h & (length-1);
 }

indexFor方法是根據(jù)hash碼來計算出在數(shù)組中對應(yīng)的下標。我們可以看到在這個方法內(nèi)部使用了與(&)操作符。與操作是對兩個操作數(shù)進行位運算,如果對應(yīng)的兩個位都為1,結(jié)果才為1,否則為0。與操作經(jīng)常會用于去除操作數(shù)的高位值,例如:01011010 & 00001111 = 00001010。我們繼續(xù)回到代碼中,看看h&(length-1)做了些什么。

Java集合系列之HashMap源碼分析

已知傳入的length是Entry數(shù)組的長度,我們知道數(shù)組下標是從0開始計算的,所以數(shù)組的最大下標為length-1。如果length為2的冪,那么length-1的二進制位后面都為1。這時h&(length-1)的作用就是去掉了h的高位值,只留下h的低位值來作為數(shù)組的下標。由此可以看到Entry數(shù)組的大小規(guī)定為2的冪就是為了能夠使用這個算法來確定數(shù)組的下標。

6. 哈希函數(shù)是怎樣計算Hash碼的?

//生成hash碼的函數(shù)
final int hash(Object k) {
  int h = hashSeed;
  //key是String類型的就使用另外的哈希算法
  if (0 != h && k instanceof String) {
    return sun.misc.Hashing.stringHash42((String) k);
  }
  h ^= k.hashCode();
  //擾動函數(shù)
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

hash方法的最后兩行是真正計算hash值的算法,計算hash碼的算法被稱為擾動函數(shù),所謂的擾動函數(shù)就是把所有東西雜糅到一起,可以看到這里使用了四個向右移位運算。目的就是將h的高位值與低位值混合一下,以此增加低位值的隨機性。在上面我們知道定位數(shù)組的下標是根據(jù)hash碼的低位值來確定的。key的hash碼是通過hashCode方法來生成的,而一個糟糕的hashCode方法生成的hash碼的低位值可能會有很大的重復。為了使得hash碼在數(shù)組上映射的比較均勻,擾動函數(shù)就派上用場了,把高位值的特性糅合進低位值,增加低位值的隨機性,從而使散列分布的更加松散,以此提高性能。下圖舉了個例子幫助理解。

Java集合系列之HashMap源碼分析

7. 替代哈希是怎么回事?

我們看到hash方法中首先會將hashSeed賦值給h。這個hashSeed就是哈希種子,它是一個隨機的值,作用就是幫助優(yōu)化哈希函數(shù)。hashSeed默認是0,也就是默認不使用替代哈希算法。那么什么時候使用hashSeed呢?首先需要設(shè)置開啟替代哈希,在系統(tǒng)屬性中設(shè)置jdk.map.althashing.threshold的值,在系統(tǒng)屬性中這個值默認是-1,當它是-1的時候使用替代哈希的閥值為Integer.MAX_VALUE。這也意味著可能你永遠也不會使用替代哈希了。當然你可以把這個閥值設(shè)小一點,這樣當集合元素達到閥值后就會生成一個隨機的hashSeed。以此增加hash函數(shù)的隨機性。為什么要使用替代哈希呢?當集合元素達到你設(shè)定的閥值之后,意味著哈希表已經(jīng)比較飽和了,出現(xiàn)哈希沖突的可能性就會大大增加,這時對再添加進來的元素使用更加隨機的散列函數(shù)能夠使后面添加進來的元素更加隨機的分布在散列表中。

注:以上分析全部基于JDK1.7,不同版本之間會有較大的改動,讀者需要注意。


網(wǎng)站題目:Java集合系列之HashMap源碼分析
網(wǎng)站地址:http://weahome.cn/article/iiggdc.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220(工作日)

18980820575(7×24)

提交需求

返回頂部