本篇文章為個人學習筆記，參考自：https://blog.csdn.net/qq_41345773/article/details/92066554 有興趣的朋友可以去了解

一.概述

HashMap是基于Map接口實現(xiàn)，元素以鍵值對的方式存儲辫愉，key允許為null 但是不允許重復

問題：HashMap是根據(jù)key的hashCode來尋找存放位置的拓诸，那當key為null時， 怎么存儲呢？
從源碼中我們就可以看到在put方法里頭肺樟，其實第一行就處理了key=null的情況：

if (key == null)  
   return putForNullKey(value);  
//那就看看這個putForNullKey是怎么處理的吧挎袜。  
private V putForNullKey(V value) {  
   for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
       if (e.key == null) {  
           V oldValue = e.value;  
           e.value = value;  
           e.recordAccess(this);  
           return oldValue;  
       }  
   }  
   modCount++;  
   addEntry(0, null, value, 0);  
   return null;  
}

可以看到顽聂，前面那個for循環(huán)，是在talbe[0]鏈表中查找key為null的元素盯仪，如果找到紊搪，則將value重新賦值給這個元素的value，并返回原來的value全景，如果上面for循環(huán)沒找到則將這個元素添加到talbe[0]鏈表的表頭耀石，所以在HashMap中key為null的值都是放在數(shù)據(jù)的第0個位置。

二.基本屬性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默認初始化大小 16 
static final float DEFAULT_LOAD_FACTOR = 0.75f;     //負載因子0.75
static final Entry<?,?>[] EMPTY_TABLE = {};         //初始化的默認數(shù)組
transient int size;     //HashMap中元素的數(shù)量
int threshold;          //判斷是否需要調整HashMap的容量

參數(shù)說明：
1. DEFAULT_INITIAL_CAPACITY
HashMap的默認初始化長度為16爸黄，因為HashMap的擴容是一項耗時的操作滞伟，所以如果能預估HashMap的長度，可以在構造函數(shù)中指定默認長度炕贵，但需要注意的是梆奈，HashMap的默認長度會為比你傳入長度值大并且最接近的二的次方的值，比如你默認長度為20称开，但實際HashMap的默認長度會為2的5次即32亩钟；
2.DEFAULT_LOAD_FACTOR 負載因子
DEFAULT_LOAD_FACTOR 負載因子是表示Hsah表中元素的填滿的程度,若:加載因子越大,填滿的元素越多,好處是,空間利用率高了,但:沖突的機會加大了.鏈表長度會越來越長,查找效率降低乓梨。反之,加載因子越小,填滿的元素越少,好處是:沖突的機會減小了,但:空間浪費多了.表中的數(shù)據(jù)將過于稀疏（很多空間還沒用，就開始擴容了）
沖突的機會越大,則查找的成本越高.因此,必須在 "沖突的機會"與"空間利用率"之間尋找一種平衡與折衷. 這種平衡與折衷本質上是數(shù)據(jù)結構中有名的"時-空"矛盾的平衡與折衷.
hashMap默認的負載因子為0.75清酥，這是考慮到存儲空間和查詢時間上成本的一個折中值扶镀，增大負載因子，可以減少hash表（就是那個entry數(shù)組）所占用的內空間总处，但會增加查詢數(shù)據(jù)的時間開銷狈惫，而查詢是最頻繁的操作（put()和get()都用到查詢）；減小負載因子鹦马，會提高查詢時間胧谈，但會增加hash表所占的內存空間。
3.size荸频、threshold
HashMap中元素的數(shù)量菱肖，當調用createEntry()方法后size會進行++操作；threshold指的是HashMap的閾值旭从，它的值為HashMap默認初始化值 * 負載因子稳强；如果size>threshold,HashMap就會調用resize()方法進行擴容，擴容后的長度為原來長度的2倍和悦；

/*
 * hash hash值
 * key 鍵值
 * value value值
 * bucketIndex Entry[]數(shù)組中的存儲索引
 * / 
void addEntry(int hash, K key, V value, int bucketIndex) {
     if ((size >= threshold) && (null != table[bucketIndex])) {
         resize(2 * table.length); //擴容操作退疫，將數(shù)據(jù)元素重新計算位置后放入newTable中，鏈表的順序與之前的順序相反
         hash = (null != key) ? hash(key) : 0;
         bucketIndex = indexFor(hash, table.length);
     }
 
    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

三鸽素、HashMap的數(shù)據(jù)儲存結構

JDK1.7以前HashMap采用的是數(shù)組+鏈表的數(shù)據(jù)結構來存儲褒繁；JDK1.8中HashMap采用數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結構來存儲。
以下為JDK1.7時HashMap的數(shù)據(jù)結構理解(借鑒他人博客)
HashMap采用Entry數(shù)組來存儲key-value對馍忽，每一個鍵值對組成了一個Entry實體棒坏，Entry類實際上是一個單向的鏈表結構，它具有Next指針遭笋，可以連接下一個Entry實體坝冕，以此來解決Hash沖突的問題。
數(shù)組存儲區(qū)間是連續(xù)的瓦呼，占用內存嚴重喂窟，故空間復雜的很大。但數(shù)組的二分查找時間復雜度小央串，為O(1)谎替；數(shù)組的特點是：尋址容易，插入和刪除困難蹋辅；
鏈表存儲區(qū)間離散，占用內存比較寬松挫掏，故空間復雜度很小侦另，但時間復雜度很大，達O（N）。鏈表的特點是：尋址困難褒傅，插入和刪除容易弃锐。

image.png

從上圖我們可以發(fā)現(xiàn)數(shù)據(jù)結構由數(shù)組+鏈表組成，一個長度為16的數(shù)組中殿托，每個元素存儲的是一個鏈表的頭結點霹菊。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢。一般情況是通過hash(key.hashCode())%len獲得支竹，也就是元素的key的哈希值對數(shù)組長度取模得到旋廷。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12礼搁。所以12饶碘、28、108以及140都存儲在數(shù)組下標為12的位置馒吴。

HashMap里面實現(xiàn)一個靜態(tài)內部類Entry扎运，其重要的屬性有 hash，key饮戳，value豪治，next。

HashMap里面用到鏈式數(shù)據(jù)結構的一個概念扯罐。上面我們提到過Entry類里面有一個next屬性负拟，作用是指向下一個Entry。打個比方篮赢，第一個鍵值對A進來齿椅，通過計算其key的hash得到的index=0，記做:Entry[0] = A启泣。一會后又進來一個鍵值對B涣脚，通過計算其index也等于0，現(xiàn)在怎么辦寥茫？HashMap會這樣做:B.next = A,Entry[0] = B,如果又進來C,index也等于0,那么C.next = B,Entry[0] = C遣蚀；這樣我們發(fā)現(xiàn)index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起。所以疑問不用擔心纱耻。也就是說數(shù)組中存儲的是最后插入的元素芭梯。到這里為止，HashMap的大致實現(xiàn)弄喘，我們應該已經(jīng)清楚了玖喘。

四、HashMap是如何解決同一hash值蘑志，不同key的問題

對于同一hash值累奈，不同key的沖突,HashMap是采用鏈表法來解決的贬派，即如果出現(xiàn)沖突，則將新加入的對象指向原來的對象澎媒，形成一個單鏈表搞乏。參考代碼如下:

void addEntry(int hash, K key, V value, int bucketIndex) {  
 Entry<K,V> e = table[bucketIndex];  
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  //e 即下一個節(jié)點的entry值 即next
if (size++ >= [threshold](https://www.baidu.com/s?wd=threshold&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd))  
resize(2 * table.length);  
 bsp;

HashMap的底層實現(xiàn) 2020-06-08

HashMap的底層實現(xiàn) 2020-06-08

一.概述

二.基本屬性

三鸽素、HashMap的數(shù)據(jù)儲存結構

四、HashMap是如何解決同一hash值蘑志，不同key的問題