整合營銷服務(wù)商
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
系列上一篇文章「vue基礎(chǔ)」新手快速入門篇（一），我們通過引入JS的文件，快速的了解了Vue的基礎(chǔ)語法和簡單用法，本篇文章筆者將帶著大家繼續(xù)學(xué)習(xí)，如何使用工程化工具構(gòu)建Vue項(xiàng)目。
像其他框架一樣，Vue 的生態(tài)也有很多一系列的工具，通過工具，可以快速幫我們構(gòu)建項(xiàng)目、發(fā)布項(xiàng)目、部署打包等，方便我們調(diào)試，避免不必要的Bug等。本篇文章我將重點(diǎn)介紹下構(gòu)建工具和調(diào)試用的瀏覽器插件，這兩款工具都有相關(guān)的官方工具，因此推薦大家進(jìn)行使用。
雖然我們可以通過引入 CDN JS 的方式快速構(gòu)建項(xiàng)目，這種方式只適合你剛接觸 Vue ，方便你快速上手學(xué)習(xí)Vue而已。但是我們還是需要一款現(xiàn)代化、模塊化、高效的工具在實(shí)際的項(xiàng)目的開發(fā)中幫助提高開發(fā)效率。
擁有良好的構(gòu)建工具為我們的開發(fā)工作帶來了便捷，不僅如此，它確保了過程的可靠性、避免了重復(fù)性、減少人為犯錯(cuò)的機(jī)會(huì)。接下來讓我們一起簡單的了解下構(gòu)建工具的核心特點(diǎn)。
使用 JavaScript 新特性
使用新的語法和功能（ES6+），讓我們的代碼更加簡潔，可讀性會(huì)更好，即使現(xiàn)代瀏覽器都支持ES2015，但是你的項(xiàng)目很有可能需要兼容低版本的瀏覽器，比如政府醫(yī)院的項(xiàng)目，還有相當(dāng)多的機(jī)器使用 windows XP。
通過添加 Babel 到我們的構(gòu)建工具中，就能很輕松的將 ES6+ 這些語法編譯成舊瀏覽器支持 JavaScript 語法。不僅如此，大家應(yīng)該都比較清楚，ECMAScript 幾乎每年都會(huì)發(fā)布新版本，估計(jì)現(xiàn)在都到10了，通過構(gòu)建工具的引用，我們可以與時(shí)俱進(jìn)的使用更多的新語法特性。
保證代碼質(zhì)量
ESLint 是一個(gè)可配置的 JavaScript 語法規(guī)則和代碼風(fēng)格的檢查工具。ESLint 能夠輔助你輕松寫出高質(zhì)量的 JavaScript 代碼。甚至還有ESLint的官方Vue插件eslint-plugin-vue，它將幫助你生成符合最佳實(shí)踐的高質(zhì)量代碼。
組件單文件化
引入構(gòu)建工具的好處就是，你可以在應(yīng)用程序里使用單文件組件（Vue’s single-file components，簡稱SFC）。SFC 的好處就是將代碼、樣式、模板組合在一起進(jìn)行集中編寫。將邏輯和UI放在一起的好處，由于所有相關(guān)內(nèi)容都集中放在一起，便于維護(hù)，由于每個(gè)組件又是獨(dú)立的，因此重用性更好。如下段代碼所示：
工具中的 vue-loader webpack 插件，將標(biāo)簽內(nèi)的HTML代碼編譯成JavaScript代碼，和組件內(nèi)的JavaScript代碼一起打包到應(yīng)用程序中。
壓縮版本的JS，體積更小
經(jīng)過構(gòu)建工具壓縮后，編譯后的JS文件體積更小，這就意味著用戶打開網(wǎng)站的速度會(huì)更快，用戶的體驗(yàn)就會(huì)更好。
Vue CLI 致力于將 Vue 生態(tài)中的工具基礎(chǔ)標(biāo)準(zhǔn)化。它確保了各種構(gòu)建工具能夠基于智能的默認(rèn)配置即可平穩(wěn)銜接，這樣你可以專注在撰寫應(yīng)用上，而不必花好幾天去糾結(jié)配置的問題。與此同時(shí)，它也為每個(gè)工具提供了調(diào)整配置的靈活性，無需 eject。
安裝 CLI
安裝 CLI 工具十分簡單，但是安裝的前提，你需要安裝 Node 環(huán)境。接下來，我們通過以下命令全局安裝 CLI：
npm install -g @vue/cli
創(chuàng)建一個(gè)新項(xiàng)目
啟動(dòng)控制終端，然后輸入以下命令進(jìn)行創(chuàng)建：
vue create my-new-project
此命會(huì)在當(dāng)前目錄下，創(chuàng)建一個(gè)以項(xiàng)目名稱命名的文件夾，然后通過交互輸入的形式，進(jìn)行配置項(xiàng)目選選項(xiàng)。如下圖所示,我們選擇默認(rèn)方式：
完成創(chuàng)建后，項(xiàng)目文件的目錄結(jié)構(gòu)如下圖所示：
切換到 package.json 你會(huì)看到項(xiàng)目的基礎(chǔ)配置，如下圖所示：
這里有幾個(gè)命令需要解釋下：
接下來我們運(yùn)行下 npm run serve 命令，效果如下圖所示：
Webpack配置
Vue CLI構(gòu)建工具是基于webpack之上的，但是抽象了所有配置，以方便我們進(jìn)行開發(fā)和使用。你可以通過運(yùn)行命令隨時(shí)查看webpack的配置。命令如下所示：
vue inspect
如果使用手工方式創(chuàng)建項(xiàng)目
上述流程是通過默認(rèn)集成的方式進(jìn)行創(chuàng)建項(xiàng)目，你也可以選擇手工的方式的方式進(jìn)行創(chuàng)建，如下圖所示：
接下來我們來了解下這些插件：
如果你在創(chuàng)建項(xiàng)目時(shí)，錯(cuò)過了這些選項(xiàng)，你完全不用擔(dān)心，你可以通過手工命令的形式自行安裝，比如我們要安裝 typescript 插件，命令如下：
vue add @vue/cli-plugin-typescript # or vue add @vue/typescript
Vue的瀏覽器工具集成在谷歌開發(fā)者工具上，方便你查看正在運(yùn)行中Vue應(yīng)用程序,你可以點(diǎn)擊https://github.com/vuejs/vue-devtools#installation 這個(gè)官方地址去下載安裝vue-devtools，安裝成功后，運(yùn)行你的Vue站點(diǎn)，打開瀏覽器開發(fā)者工具，你就會(huì)看到一個(gè)Vue的選項(xiàng)卡，點(diǎn)擊進(jìn)行切換，你就會(huì)看到如下圖所示的內(nèi)容：
Components Tab
組件選項(xiàng)卡，將對(duì)于頁面組件的結(jié)構(gòu)進(jìn)行了樹形化，更加直觀的展示了當(dāng)前組件包含了哪些組件，組件里包含了哪些內(nèi)容，比如props,data 等。
Vuex Tab
更加直觀的展示了當(dāng)前全局?jǐn)?shù)據(jù)的存儲(chǔ)狀態(tài)，及相關(guān) mutations 、getters 等內(nèi)容。
Events Tab
你可以通過事件選項(xiàng)卡，定位事件來源于那個(gè)組件，點(diǎn)擊對(duì)應(yīng)的事件，你能看到和事件更多相關(guān)的信息。
大部分前端開發(fā)者想必都喜歡用微軟的 VSCode 開發(fā)工具，目前針對(duì)Vue來說，使用最廣泛的要數(shù) Vetur VSCode擴(kuò)展插件，安裝也十分簡單：
今天的內(nèi)容就和大家聊到這里，我們一起學(xué)習(xí)了為什么要使用構(gòu)建工具，如何來安裝構(gòu)建工具以及相關(guān)的瀏覽器、編輯器插件，下一篇文章我將和大家聊聊如何編寫自定義組件。
在實(shí)際需求中，我們常常會(huì)遇到這樣的問題，在諸多的數(shù)據(jù)中，通過其編號(hào)來尋找某一些信息，從而進(jìn)行查看或者修改，例如通過學(xué)號(hào)查詢學(xué)生信息。今天我們所介紹的Map集合就可以很好的幫助我們實(shí)現(xiàn)這種需求
Map是一種存儲(chǔ)元素對(duì)的集合（元素對(duì)分別稱作 鍵 和 值 也稱鍵值對(duì)）它將鍵映射到值的對(duì)象。一個(gè)映射不能包含重復(fù)的鍵，并且每個(gè)鍵最 多只能映射到一個(gè)值。
怎么理解呢？
鍵 (key)：就是你存的值的編號(hào) 值 (value)：就是你要存放的數(shù)據(jù)
你可以近似的將鍵理解為下標(biāo)，值依據(jù)鍵而存儲(chǔ)，每個(gè)鍵都有其對(duì)應(yīng)值。這兩者是1、1對(duì)應(yīng)的
但在之前下標(biāo)是整數(shù)，但是Map中鍵可以使任意類型的對(duì)象。
散列表也叫hash表 ，是根據(jù)關(guān)鍵碼值而進(jìn)行直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射也叫散列函數(shù)，存放記錄的數(shù)組叫散列表。
一個(gè)通俗的例子是，為了查找電話簿中某人的號(hào)碼，可以創(chuàng)建一個(gè)按照人名首字母順序排列的表（即建立人名到首字母的一個(gè)函數(shù)關(guān)系），在首字母為W的表中查找“王”姓的電話號(hào)碼，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字，“取首字母”是這個(gè)例子中散列函數(shù)的函數(shù)法則，存放首字母的表對(duì)應(yīng)散列表。關(guān)鍵字和函數(shù)法則理論上可以任意確定。—— 維基百科
哈希表其實(shí)就是數(shù)組的一種擴(kuò)展，因?yàn)槠浔举|(zhì)上用的就是數(shù)組可以按照下標(biāo)隨機(jī)訪問數(shù)據(jù)的特點(diǎn)，我們來一步一步看一下
首先創(chuàng)建一個(gè)數(shù)組，我們將數(shù)組的每一個(gè)存儲(chǔ)空間看做一個(gè)一個(gè)箱子或者一個(gè)一個(gè)桶，存儲(chǔ)一些 key-value 的數(shù)據(jù)如，【張三，20】【李四，30】【王五，40】【趙六，50】【孫七，60】，依次放置于數(shù)組中。
如果按照普通順序表的查詢方式，就需要從開始依次比對(duì)查詢，但是數(shù)據(jù)量越多，順序表查找耗費(fèi)的時(shí)間就越長。在大量數(shù)據(jù)的情況下，很顯然不上算。
還有很多種數(shù)據(jù)結(jié)構(gòu)，它們并不關(guān)心元素的順序，能夠快速的查找元素?cái)?shù)據(jù)，其中一種就是：散列表
下面看看散列表如何做到這么高效處理的
這次依舊使用 5 個(gè)箱子（桶）空間的數(shù)組來存儲(chǔ)數(shù)據(jù)，我們開始存第一個(gè)數(shù)據(jù)【張三，20】，散列表會(huì)使用哈希函數(shù)（Hash算法）計(jì)算出 “張三” 的鍵，也就是字符串 “張三” 的哈希值，例如返回一個(gè) 5372 ，將其做取余處理，除數(shù)為數(shù)組的長度，即：5372 mod 5=2，因此將其放在下標(biāo)（index）為 2 的位置，例如 第二個(gè)數(shù)據(jù)的哈希值為 6386，繼續(xù)操作 6386 mod 5=1，即將其放在下標(biāo)（index）為 1 的位置，以此類推.....
但是有一種情況就會(huì)出現(xiàn)了，例如我們存儲(chǔ)第三個(gè)數(shù)據(jù)【王五，40】的時(shí)候，經(jīng)過哈希函數(shù)計(jì)算，得出的結(jié)果為 5277，5277 mod 5=2 ，但是 2 這個(gè)位置已經(jīng)有【張三，20】這個(gè)數(shù)據(jù)存在了，這種存儲(chǔ)位置重復(fù)了的情況便叫作沖突
在 JDK 1.8 之前，HashMap 的底層是數(shù)組和鏈表。因此當(dāng)出現(xiàn)哈希沖突后，使用拉鏈法解決沖突。
拉鏈法，就是將數(shù)組的每一個(gè)格子（箱子），都看作一個(gè)鏈表，例如下標(biāo)為 1 的格子，就是一個(gè)鏈表，已經(jīng)存儲(chǔ)了 【張三，20】，若仍有數(shù)據(jù)哈希值 mod 后等于 1 ，則直接在 1 中的這個(gè)鏈表中追加上這些數(shù)據(jù)就可以了。
JDK 8 做了一些較大的調(diào)整，當(dāng)數(shù)組中每個(gè)格子里的鏈表，長度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，就可以大大的減少搜索時(shí)間。
而且，如果散列表快滿的情況下下，還會(huì)有機(jī)制進(jìn)行再散列，下面會(huì)在源碼中深入分析。
紅黑樹是一種復(fù)雜的樹形結(jié)構(gòu)，這里不做過于詳細(xì)的解釋，講一下其基本的結(jié)構(gòu)，有一個(gè)基本的概念。
紅黑樹就是為了防止二叉樹一些極端的情況，例如變成一條線狀，或者左右不均衡，從二叉查找樹，2-3樹 等演變出來的一種樹形結(jié)構(gòu)。最主要的目的就是為了保持平衡。保證樹的左右分支葉子等基本平衡。
具體的數(shù)據(jù)結(jié)果演變是比較復(fù)雜的，這一篇還是主要講解 HashMap ，有需要以后會(huì)專篇講解一些常見的數(shù)據(jù)結(jié)構(gòu)的 Java 版本
// 序列化自動(dòng)生成的一個(gè)碼，用來在正反序列化中驗(yàn)證版本一致性。
private static final long serialVersionUID=362498820763181265L;
// 默認(rèn)的初始容量 1 * 2^4=16
static final int DEFAULT_INITIAL_CAPACITY=1 << 4;
// 最大容量 1 * 2^30
static final int MAXIMUM_CAPACITY=1 << 30;
// 默認(rèn)的加載因子 0.75
static final float DEFAULT_LOAD_FACTOR=0.75f;
// 桶的樹化閾值，當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹，
// 也就是上面提到的長度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹
static final int TREEIFY_THRESHOLD=8;
// 桶的鏈表還原閾值，當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)樹轉(zhuǎn)鏈表
// 一個(gè)道理
static final int UNTREEIFY_THRESHOLD=6;
// 最小樹形化容量閾值，當(dāng)哈希表中的容量 > 該值時(shí)，才允許樹形化鏈表
// 否則，若桶內(nèi)元素太多時(shí)，則直接擴(kuò)容，而不是樹形化
// 為了避免進(jìn)行擴(kuò)容和樹形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY=64;
// 存儲(chǔ)元素的數(shù)組，總是2的冪次倍
transient Node<k,v>[] table;
// 存放具體元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的個(gè)數(shù)（不是數(shù)組的長度）
transient int size;
// 擴(kuò)容和修改的計(jì)數(shù)變量
transient int modCount;
// 臨界值 當(dāng)實(shí)際大小(容量*填充因子)超過臨界值時(shí)，會(huì)進(jìn)行擴(kuò)容
int threshold;
// 加載因子
final float loadFactor;其中有幾個(gè)需要強(qiáng)調(diào)的內(nèi)容
threshold 臨界值
loadFactor加載因子
因?yàn)橐欢l件下會(huì)轉(zhuǎn)換成紅黑樹這種數(shù)據(jù)結(jié)果，所以除了普通的 Node 節(jié)點(diǎn)，還有 樹節(jié)點(diǎn)（TreeNode 節(jié)點(diǎn)）
static class Node<K,V> implements Map.Entry<K,V> {
// 哈希碼，用來查找位置以及比對(duì)元素是否相同
final int hash;
// 鍵
final K key;
// 值
V value;
// 指向下一個(gè)結(jié)點(diǎn)
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash=hash;
this.key=key;
this.value=value;
this.next=next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
// 重寫了 hashCode， ^ 是位異或運(yùn)算符
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue=value;
value=newValue;
return oldValue;
}
// 重寫 equals() 方法
public final boolean equals(Object o) {
if (o==this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e=(Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 父節(jié)點(diǎn)
TreeNode<K,V> parent;
// 左節(jié)點(diǎn)
TreeNode<K,V> left;
// 右節(jié)點(diǎn)
TreeNode<K,V> right;
TreeNode<K,V> prev;
// 判斷顏色，默認(rèn)紅色
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 返回根節(jié)點(diǎn)
final TreeNode<K,V> root() {
for (TreeNode<K,V> r=this, p;;) {
if ((p=r.parent)==null)
return r;
r=p;
}// 指定了具體容量大小和加載因子的構(gòu)造函數(shù)
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);
this.loadFactor=loadFactor;
this.threshold=tableSizeFor(initialCapacity);
}
// 指定了具體容量大小的構(gòu)造函數(shù)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 默認(rèn)無參構(gòu)造函數(shù)
public HashMap() {
this.loadFactor=DEFAULT_LOAD_FACTOR;
}
// 指定了 map 的構(gòu)造函數(shù)
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor=DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}tableSizeFor
/**
* 返回一個(gè)大于輸入?yún)?shù)，且最接近的，2的整數(shù)次冪的數(shù)
* 只是一個(gè)初始化內(nèi)容，創(chuàng)建哈希表時(shí)，會(huì)再重新賦值
*/
static final int tableSizeFor(int cap) {
int n=cap - 1;
n |=n >>> 1;
n |=n >>> 2;
n |=n >>> 4;
n |=n >>> 8;
n |=n >>> 16;
return (n < 0) ? 1 : (n >=MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}putMapEntries
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 拿到給定 Map 的長度
int s=m.size();
if (s > 0) {
// 判斷當(dāng)前實(shí)際存儲(chǔ)數(shù)據(jù)的這個(gè) table 是否已經(jīng)初始化
if (table==null) { // pre-size
// 沒初始化，就將 s 處理后設(shè)為m的實(shí)際元素個(gè)數(shù)
float ft=((float)s / loadFactor) + 1.0F;
// 防止小于最小容量（閾值）
int t=((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 若大于臨界值，則初始化閾值
if (t > threshold)
threshold=tableSizeFor(t);
}
// table 已初始化，并且給定 Map m 元素個(gè)數(shù)大于閾值，進(jìn)行擴(kuò)容處理
else if (s > threshold)
resize();
// 將給定集合 m 中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key=e.getKey();
V value=e.getValue();
// putVal 方法會(huì)在介紹添加相關(guān)方法時(shí)介紹
putVal(hash(key), key, value, false, evict);
}
}
}對(duì)于 HashMap ，其提供給外界的公共添加方法只有 put(K key, V value) 一個(gè)，其他 put 方法都是供 put(K key, V value) 內(nèi)部調(diào)用的
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}關(guān)于 putVal 的每個(gè)參數(shù)和細(xì)節(jié)下面接著說，看一下第一個(gè)參數(shù) hash(key) 首先提一下，在 HashMap 中是如何計(jì)算 hash 值的，跳轉(zhuǎn)到 3.1 可看，也可以看完最后去看也可以。
[3.1 hash() 中的擾動(dòng)函數(shù)如何解決Hash沖突 ※](###3.1 hash() 中的擾動(dòng)函數(shù)如何解決Hash沖突 ※)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table未初始化（為null）或者長度為0，調(diào)用 resize 進(jìn)行擴(kuò)容
if ((tab=table)==null || (n=tab.length)==0)
n=(tab=resize()).length;
// 若桶為空，即無發(fā)生碰撞
// (n - 1) & hash 用來確定元素存放在哪個(gè)位置，即哪個(gè)桶中
if ((p=tab[i=(n - 1) & hash])==null)
// 新生成結(jié)點(diǎn)放入桶中(數(shù)組中)
tab[i]=newNode(hash, key, value, null);
// 若桶中已經(jīng)存在元素
else {
Node<K,V> e; K k;
// 若節(jié)點(diǎn) key 存在，就和要插入的key比較
if (p.hash==hash &&
((k=p.key)==key || (key !=null && key.equals(k))))
// 如果key相同就直接覆蓋 value
e=p;
// hash值不相等，即key不相等，轉(zhuǎn)為紅黑樹結(jié)點(diǎn)
else if (p instanceof TreeNode)
// 插入到樹中
e=((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 若是為鏈表結(jié)點(diǎn)
else {
// 遍歷找到尾節(jié)點(diǎn)插入
for (int binCount=0; ; ++binCount) {
// 到達(dá)鏈表的尾部
if ((e=p.next)==null) {
// 在尾部插入新結(jié)點(diǎn)
p.next=newNode(hash, key, value, null);
// 結(jié)點(diǎn)數(shù)量達(dá)到閾值，轉(zhuǎn)化為紅黑樹
if (binCount >=TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循環(huán)
break;
}
// 遍歷的過程中，遇到相同 key 則覆蓋 value
if (e.hash==hash &&
((k=e.key)==key || (key !=null && key.equals(k))))
// 相等，跳出循環(huán)
break;
// 用于遍歷桶中的鏈表，與前面的e=p.next組合，可以遍歷鏈表
p=e;
}
}
// 在桶中找到key值、hash值與插入元素相等的結(jié)點(diǎn)
if (e !=null) {
// 記錄e的value
V oldValue=e.value;
// onlyIfAbsent 為 false 或者舊值為 null
if (!onlyIfAbsent || oldValue==null)
// 用新值替換舊值
e.value=value;
// 訪問后回調(diào)
afterNodeAccess(e);
// 返回舊值
return oldValue;
}
}
// 結(jié)構(gòu)性修改
++modCount;
// 超過最大容量，擴(kuò)容
if (++size > threshold)
resize();
// 插入后回調(diào)
afterNodeInsertion(evict);
return null;
} 總結(jié)一下大致流程：
同樣 get 方法中也用到了 hash 方法計(jì)算 key 的哈希值，同樣跳轉(zhuǎn)到 3.1 可看，也可以看完最后去看也可以。
[3.1 hash() 中的擾動(dòng)函數(shù)如何解決Hash沖突 ※](###3.1 hash() 中的擾動(dòng)函數(shù)如何解決Hash沖突 ※)
public V get(Object key) {
Node<K,V> e;
return (e=getNode(hash(key), key))==null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 保證計(jì)算出來的哈希值，確定是在哈希表上的
if ((tab=table) !=null && (n=tab.length) > 0 &&
(first=tab[(n - 1) & hash]) !=null) {
// 要是直接在桶的首個(gè)位置上，直接就可以返回（這個(gè)桶中只有一個(gè)元素，或者在首個(gè)）
if (first.hash==hash && // always check first node
((k=first.key)==key || (key !=null && key.equals(k))))
return first;
// 桶中不止一個(gè)節(jié)點(diǎn)
if ((e=first.next) !=null) {
// 在樹中 get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在鏈表中g(shù)et
do {
if (e.hash==hash &&
((k=e.key)==key || (key !=null && key.equals(k))))
return e;
} while ((e=e.next) !=null);
}
}
return null;
}同樣 get 方法中也用到了 hash 方法計(jì)算 key 的哈希值，同樣跳轉(zhuǎn)到 3.1 可看，也可以看完最后去看也可以。
[3.1 hash() 中的擾動(dòng)函數(shù)如何解決Hash沖突 ※](###3.1 hash() 中的擾動(dòng)函數(shù)如何解決Hash沖突 ※)
public V remove(Object key) {
Node<K,V> e;
return (e=removeNode(hash(key), key, null, false, true))==null ?
null : e.value;
}final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 桶不為空，映射的哈希值也存在
if ((tab=table) !=null && (n=tab.length) > 0 &&
(p=tab[index=(n - 1) & hash]) !=null) {
Node<K,V> node=null, e; K k; V v;
// 如果在桶的首位就找到對(duì)應(yīng)元素，記錄下來
if (p.hash==hash &&
((k=p.key)==key || (key !=null && key.equals(k))))
node=p;
// 若不在首位，就去紅黑樹或者鏈表中查詢了
else if ((e=p.next) !=null) {
if (p instanceof TreeNode)
node=((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash==hash &&
((k=e.key)==key ||
(key !=null && key.equals(k)))) {
node=e;
break;
}
p=e;
} while ((e=e.next) !=null);
}
}
// 找到了要?jiǎng)h除的節(jié)點(diǎn)和值，就分三種情況去刪除，鏈表，紅黑樹，桶的首位
if (node !=null && (!matchValue || (v=node.value)==value ||
(value !=null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node==p)
tab[index]=node.next;
else
p.next=node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}resize 在程序中是非常耗時(shí)的。要盡量避免用它。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab=table;
int oldCap=(oldTab==null) ? 0 : oldTab.length;
int oldThr=threshold;
int newCap, newThr=0;
if (oldCap > 0) {
// 超過最大值，不再擴(kuò)容，沒辦法了
if (oldCap >=MAXIMUM_CAPACITY) {
threshold=Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值，就擴(kuò)充為原來的2倍
else if ((newCap=oldCap << 1) < MAXIMUM_CAPACITY && oldCap >=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 初始化時(shí)，threshold 暫時(shí)保存 initialCapacity 參數(shù)的值
newCap=oldThr;
else {
// signifies using defaults
newCap=DEFAULT_INITIAL_CAPACITY;
newThr=(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的resize上限
if (newThr==0) {
float ft=(float)newCap * loadFactor;
newThr=(newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold=newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab=(Node<K,V>[])new Node[newCap];
table=newTab;
if (oldTab !=null) {
// 將舊的鍵值對(duì)移動(dòng)到新的哈希桶數(shù)組中
for (int j=0; j < oldCap; ++j) {
Node<K,V> e;
if ((e=oldTab[j]) !=null) {
oldTab[j]=null;
// / 無鏈條，也就是沒有下一個(gè)，只有自己
if (e.next==null)
newTab[e.hash & (newCap - 1)]=e;
else if (e instanceof TreeNode)
// 拆紅黑樹，先拆成兩個(gè)子鏈表，再分別按需轉(zhuǎn)成紅黑樹
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 拆鏈表，拆成兩個(gè)子鏈表并保持原有順序
Node<K,V> loHead=null, loTail=null;
Node<K,V> hiHead=null, hiTail=null;
Node<K,V> next;
do {
next=e.next;
// 原索引
if ((e.hash & oldCap)==0) {
if (loTail==null)
loHead=e;
else
loTail.next=e;
loTail=e;
}
// 原索引 + oldCap
else {
if (hiTail==null)
hiHead=e;
else
hiTail.next=e;
hiTail=e;
}
} while ((e=next) !=null);
// 原索引放到新的哈希桶中
if (loTail !=null) {
loTail.next=null;
newTab[j]=loHead;
}
// 原索引 +oldCap 放到新的哈希桶中
if (hiTail !=null) {
hiTail.next=null;
newTab[j + oldCap]=hiHead;
}
}
}
}
}
return newTab;
}看HashMap的put方法源碼：
//HashMap 源碼節(jié)選-JDK8
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}而我們的值在返回前需要經(jīng)過HashMap中的hash方法
接著定位到hash方法的源碼：
static final int hash(Object key) {
int h;
return (key==null) ? 0 : (h=key.hashCode()) ^ (h >>> 16);
}hash方法的返回結(jié)果中是一句三目運(yùn)算符，鍵 (key) 為null即返回 0,存在則返回后一句的內(nèi)容
(h=key.hashCode()) ^ (h >>> 16)JDK8中 HashMap——hash 方法中的這段代碼叫做 “擾動(dòng)函數(shù)”
我們來分析一下：
hashCode 是 Object 類中的一個(gè)方法，在子類中一般都會(huì)重寫，而根據(jù)我們之前自己給出的程序，暫以 Integer 類型為例，我們來看一下 Integer 中 hashCode 方法的源碼：
/**
* Returns a hash code for this {@code Integer}.
*
* @return a hash code value for this object, equal to the
* primitive {@code int} value represented by this
* {@code Integer} object.
*/
@Override
public int hashCode() {
return Integer.hashCode(value);
}
/**
* Returns a hash code for a {@code int} value; compatible with
* {@code Integer.hashCode()}.
*
* @param value the value to hash
* @since 1.8
*
* @return a hash code value for a {@code int} value.
*/
public static int hashCode(int value) {
return value;
}
Integer 中 hashCode 方法的返回值就是這個(gè)數(shù)本身
注：整數(shù)的值因?yàn)榕c整數(shù)本身一樣唯一，所以它是一個(gè)足夠好的散列
所以，下面的 A、B 兩個(gè)式子就是等價(jià)的
//注：key為 hash(Object key)參數(shù)
A：(h=key.hashCode()) ^ (h >>> 16)
B：key ^ (key >>> 16)分析到這一步，我們的式子只剩下位運(yùn)算了，先不急著算什么，我們先理清思路
HashSet因?yàn)榈讓邮褂?/span>哈希表（鏈表結(jié)合數(shù)組）實(shí)現(xiàn)，存儲(chǔ)時(shí)key通過一些運(yùn)算后得出自己在數(shù)組中所處的位置。
我們?cè)趆ashCoe方法中返回到了一個(gè)等同于本身值的散列值，但是考慮到int類型數(shù)據(jù)的范圍：-2147483648~2147483647 ，著很顯然，這些散列值不能直接使用，因?yàn)閮?nèi)存是沒有辦法放得下，一個(gè)40億長度的數(shù)組的。所以它使用了對(duì)數(shù)組長度進(jìn)行取模運(yùn)算，得余后再作為其數(shù)組下標(biāo)，indexFor( ) ——JDK7中，就這樣出現(xiàn)了，在JDK8中 indexFor()就消失了，而全部使用下面的語句代替，原理是一樣的。
//JDK8中
(tab.length - 1) & hash； //JDK7中
bucketIndex=indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length - 1);
}提一句，為什么取模運(yùn)算時(shí)我們用 & 而不用 % 呢，因?yàn)槲贿\(yùn)算直接對(duì)內(nèi)存數(shù)據(jù)進(jìn)行操作，不需要轉(zhuǎn)成十進(jìn)制，因此處理速度非常快，這樣就導(dǎo)致位運(yùn)算 & 效率要比取模運(yùn)算 % 高很多。
看到這里我們就知道了，存儲(chǔ)時(shí)key需要通過hash方法和indexFor( )運(yùn)算，來確定自己的對(duì)應(yīng)下標(biāo)
(取模運(yùn)算，應(yīng)以JDK8為準(zhǔn)，但為了稱呼方便，還是按照J(rèn)DK7的叫法來說，下面的例子均為此，特此提前聲明)
但是先直接看與運(yùn)算(&)，好像又出現(xiàn)了一些問題，我們舉個(gè)例子：
HashMap中初始長度為16，length - 1=15；其二進(jìn)制表示為 00000000 00000000 00000000 00001111
而與運(yùn)算計(jì)算方式為：遇0則0，我們隨便舉一個(gè)key值
1111 1111 1010 0101 1111 0000 0011 1100
& 0000 0000 0000 0000 0000 0000 0000 1111
----------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1100我們將這32位從中分開，左邊16位稱作高位，右邊16位稱作低位，可以看到經(jīng)過&運(yùn)算后 結(jié)果就是高位全部歸0，剩下了低位的最后四位。但是問題就來了，我們按照當(dāng)前初始長度為默認(rèn)的16，HashCode值為下圖兩個(gè)，可以看到，在不經(jīng)過擾動(dòng)計(jì)算時(shí)，只進(jìn)行與(&)運(yùn)算后 Index值均為 12 這也就導(dǎo)致了哈希沖突
哈希沖突的簡單理解：計(jì)劃把一個(gè)對(duì)象插入到散列表(哈希表)中，但是發(fā)現(xiàn)這個(gè)位置已經(jīng)被別的對(duì)象所占據(jù)了
例子中，兩個(gè)不同的HashCode值卻經(jīng)過運(yùn)算后，得到了相同的值，也就代表，他們都需要被放在下標(biāo)為2的位置
一般來說，如果數(shù)據(jù)分布比較廣泛，而且存儲(chǔ)數(shù)據(jù)的數(shù)組長度比較大，那么哈希沖突就會(huì)比較少，否則很高。
但是，如果像上例中只取最后幾位的時(shí)候，這可不是什么好事，即使我的數(shù)據(jù)分布很散亂，但是哈希沖突仍然會(huì)很嚴(yán)重。
別忘了，我們的擾動(dòng)函數(shù)還在前面擱著呢，這個(gè)時(shí)候它就要發(fā)揮強(qiáng)大的作用了,還是使用上面兩個(gè)發(fā)生了哈希沖突的數(shù)據(jù)，這一次我們加入擾動(dòng)函數(shù)再進(jìn)行與(&)運(yùn)算
補(bǔ)充 ：>>> 按位右移補(bǔ)零操作符，左操作數(shù)的值按右操作數(shù)指定的為主右移，移動(dòng)得到的空位以零填充
^ 位異或運(yùn)算，相同則 0，不同則 1
可以看到，本發(fā)生了哈希沖突的兩組數(shù)據(jù)，經(jīng)過擾動(dòng)函數(shù)處理后，數(shù)值變得不再一樣了，也就避免了沖突
其實(shí)在擾動(dòng)函數(shù)中，將數(shù)據(jù)右位移16位，哈希碼的高位和低位混合了起來，這也正解決了前面所講 高位歸0，計(jì)算只依賴低位最后幾位的情況, 這使得高位的一些特征也對(duì)低位產(chǎn)生了影響，使得低位的隨機(jī)性加強(qiáng)，能更好的避免沖突
作者：BWH_Steven
原文鏈接：https://www.cnblogs.com/ideal-20/p/14424234.html
本篇博客我們來介紹在 JDK1.8 中 HashMap 的源碼實(shí)現(xiàn)，這也是最常用的一個(gè)集合。但是在介紹 HashMap 之前，我們先介紹什么是 Hash表。
Hash表也稱為散列表，也有直接譯作哈希表，Hash表是一種根據(jù)關(guān)鍵字值（key - value）而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說它通過把關(guān)鍵碼值映射到表中的一個(gè)位置來訪問記錄，以此來加快查找的速度。在鏈表、數(shù)組等數(shù)據(jù)結(jié)構(gòu)中，查找某個(gè)關(guān)鍵字，通常要遍歷整個(gè)數(shù)據(jù)結(jié)構(gòu)，也就是O(N)的時(shí)間級(jí)，但是對(duì)于哈希表來說，只是O(1)的時(shí)間級(jí)。
比如對(duì)于前面我們講解的 ArrayList 集合和 LinkedList ，如果我們要查找這兩個(gè)集合中的某個(gè)元素，通常是通過遍歷整個(gè)集合，需要O(N)的時(shí)間級(jí)。
如果是哈希表，它是通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表，只需要O(1)的時(shí)間級(jí)。
①、存放在哈希表中的數(shù)據(jù)是key-value 鍵值對(duì)，比如存放哈希表的數(shù)據(jù)為:
{Key1-Value1,Key2-Value2,Key3-Value3,Key4-Value4,Key5-Value5,Key6-Value6}
如果我們想查找是否存在鍵值對(duì) Key3-Value3，首先通過 Key3 經(jīng)過散列函數(shù)，得到值 k3，然后通過 k3 和散列表對(duì)應(yīng)的值找到是 Value3。
②、當(dāng)然也有可能存放哈希表的值只是 Value1,Value2,Value3這種類型：
{Value1,Value2,Value3,Value4,Value5,Value6}
這時(shí)候我們可以假設(shè) Value1 是等于 Key1的，也就是{Value1-Value1,Value2-Value2,Value3-Value3,Value4-Value4,Value5-Value5,Value6-Value6}可以將 Value1經(jīng)過散列函數(shù)轉(zhuǎn)換成與散列表對(duì)應(yīng)的值。
大家都用過漢語字典吧，漢語字典的優(yōu)點(diǎn)是我們可以通過前面的拼音目錄快速定位到所要查找的漢字。當(dāng)給定我們某個(gè)漢字時(shí)，大腦會(huì)自動(dòng)將漢字轉(zhuǎn)換成拼音（如果我們認(rèn)識(shí)，不認(rèn)識(shí)可以通過偏旁部首），這個(gè)轉(zhuǎn)換的過程我們可以看成是一個(gè)散列函數(shù)，之后在根據(jù)轉(zhuǎn)換得到的拼音找到該字所在的頁碼，從而找到該漢字。
漢語字典是哈希表的典型實(shí)現(xiàn)，但是我們仔細(xì)思考，會(huì)發(fā)現(xiàn)這樣幾個(gè)問題？
①、為什么要有散列函數(shù)？
②、多個(gè) key 通過散列函數(shù)會(huì)得到相同的值，這時(shí)候怎么辦？
對(duì)于第一個(gè)問題，散列函數(shù)的存在能夠幫助我們更快的確定key和value的映射關(guān)系，試想一下，如果沒有漢字和拼音的轉(zhuǎn)換規(guī)則（或者漢字和偏旁部首的），給你一個(gè)漢字，你該如何從字典中找到該漢字？我想除了遍歷整部字典，你沒有什么更好的辦法。
對(duì)于第二個(gè)問題，多個(gè) key 通過散列函數(shù)得到相同的值，這其實(shí)也是哈希表最大的問題——沖突。比如同音字漢字，我們得到的拼音就會(huì)是相同的，那么我們?cè)撊绾卧谧值渲写娣磐糇譂h字呢？有兩種做法：
第一種是開放地址法，當(dāng)我們遇到?jīng)_突了，這時(shí)候通過另一種函數(shù)再計(jì)算一遍，得到相應(yīng)的映射關(guān)系。比如對(duì)于漢語字典，一個(gè)字 “余”，拼音是“yu”，我們將其放在頁碼為567(假設(shè)在該位置)，這時(shí)候又來了一個(gè)漢字“于”，拼音也是“yu”，那么這時(shí)候我們要是按照轉(zhuǎn)換規(guī)則，也得將其放在頁碼為567的位置，但是我們發(fā)現(xiàn)這個(gè)頁碼已經(jīng)被占用了，這時(shí)候怎么辦？我們可以在通過另一種函數(shù)，得到的值加1。那么漢字"于"就會(huì)被放在576+1=577的位置。
第二種是鏈地址法，我們可以將字典的每一頁都看成是一個(gè)子數(shù)組或者子鏈表，當(dāng)遇到?jīng)_突了，直接往當(dāng)前頁碼的子數(shù)組或者子鏈表里面填充即可。那么我們進(jìn)行同音字查找的時(shí)候，可能需要遍歷其子數(shù)組或者子鏈表。如下圖所示：
對(duì)于開放地址法，可能會(huì)遇到二次沖突，三次沖突，所以需要良好的散列函數(shù)，分布的越均勻越好。對(duì)于鏈地址法，雖然不會(huì)造成二次沖突，但是如果一次沖突很多，那么會(huì)造成子數(shù)組或者子鏈表很長，那么我們查找所需遍歷的時(shí)間也會(huì)很長。
聽名字就知道，HashMap 是一個(gè)利用哈希表原理來存儲(chǔ)元素的集合。遇到?jīng)_突時(shí)，HashMap 是采用的鏈地址法來解決，在 JDK1.7 中，HashMap 是由 數(shù)組+鏈表構(gòu)成的。但是在 JDK1.8 中，HashMap 是由 數(shù)組+鏈表+紅黑樹構(gòu)成，新增了紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)變得復(fù)雜了，但是效率也變的更高效。下面我們來具體介紹在 JDK1.8 中 HashMap 是如何實(shí)現(xiàn)的。
HashMap 是一個(gè)散列表，它存儲(chǔ)的內(nèi)容是鍵值對(duì)(key-value)映射，而且 key 和 value 都可以為 null。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
首先該類實(shí)現(xiàn)了一個(gè) Map 接口，該接口定義了一組鍵值對(duì)映射通用的操作。儲(chǔ)存一組成對(duì)的鍵-值對(duì)象，提供key（鍵）到value（值）的映射，Map中的key不要求有序，不允許重復(fù)。value同樣不要求有序，但可以重復(fù)。但是我們發(fā)現(xiàn)該接口方法有很多，我們?cè)O(shè)計(jì)某個(gè)鍵值對(duì)的集合有時(shí)候并不像實(shí)現(xiàn)那么多方法，那該怎么辦？
JDK 還為我們提供了一個(gè)抽象類 AbstractMap ，該抽象類繼承 Map 接口，所以如果我們不想實(shí)現(xiàn)所有的 Map 接口方法，就可以選擇繼承抽象類 AbstractMap 。
但是我們發(fā)現(xiàn) HashMap 類即繼承了 AbstractMap 接口，也實(shí)現(xiàn)了 Map 接口，這樣做難道不是多此一舉？后面我們會(huì)講的 LinkedHashSet 集合也有這樣的寫法。
畢竟 JDK 經(jīng)過這么多年的發(fā)展維護(hù)，博主起初也是認(rèn)為這樣是有具體的作用的，后來找了很多資料，發(fā)現(xiàn)這其實(shí)完全沒有任何作用
據(jù) java 集合框架的創(chuàng)始人Josh Bloch描述，這樣的寫法是一個(gè)失誤。在java集合框架中，類似這樣的寫法很多，最開始寫java集合框架的時(shí)候，他認(rèn)為這樣寫，在某些地方可能是有價(jià)值的，直到他意識(shí)到錯(cuò)了。顯然的，JDK的維護(hù)者，后來不認(rèn)為這個(gè)小小的失誤值得去修改，所以就這樣存在下來了。 HashMap 集合還實(shí)現(xiàn)了 Cloneable 接口以及 Serializable 接口，分別用來進(jìn)行對(duì)象克隆以及將對(duì)象進(jìn)行序列化。
4、字段屬性
//序列化和反序列化時(shí)，通過該字段進(jìn)行版本一致性驗(yàn)證
private static final long serialVersionUID=362498820763181265L;
//默認(rèn) HashMap 集合初始容量為16（必須是 2 的倍數(shù)）
static final int DEFAULT_INITIAL_CAPACITY=1 << 4; // aka 16
//集合的最大容量，如果通過帶參構(gòu)造指定的最大容量超過此數(shù)，默認(rèn)還是使用此數(shù)
static final int MAXIMUM_CAPACITY=1 << 30;
//默認(rèn)的填充因子
static final float DEFAULT_LOAD_FACTOR=0.75f;
//當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹(JDK1.8新增)
static final int TREEIFY_THRESHOLD=8;
//當(dāng)桶(bucket)上的節(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)會(huì)轉(zhuǎn)成鏈表(JDK1.8新增)
static final int UNTREEIFY_THRESHOLD=6;
/**(JDK1.8新增)
* 當(dāng)集合中的容量大于這個(gè)值時(shí)，表中的桶才能進(jìn)行樹形化 ，否則桶內(nèi)元素太多時(shí)會(huì)擴(kuò)容，
* 而不是樹形化 為了避免進(jìn)行擴(kuò)容、樹形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY=64;
注意：后面三個(gè)字段是 JDK1.8 新增的，主要是用來進(jìn)行紅黑樹和鏈表的互相轉(zhuǎn)換。
/**
* 初始化使用，長度總是 2的冪
*/
transient Node<K,V>[] table;
/**
* 保存緩存的entrySet（）
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 此映射中包含的鍵值映射的數(shù)量。（集合存儲(chǔ)鍵值對(duì)的數(shù)量）
*/
transient int size;
/**
* 跟前面ArrayList和LinkedList集合中的字段modCount一樣，記錄集合被修改的次數(shù)
* 主要用于迭代器中的快速失敗
*/
transient int modCount;
/**
* 調(diào)整大小的下一個(gè)大小值（容量*加載因子）。capacity * load factor
*/
int threshold;
/**
* 散列表的加載因子。
*/
final float loadFactor;
下面我們重點(diǎn)介紹上面幾個(gè)字段：
①、Node[] table
我們說 HashMap 是由數(shù)組+鏈表+紅黑樹組成，這里的數(shù)組就是 table 字段。后面對(duì)其進(jìn)行初始化長度默認(rèn)是 DEFAULTINITIALCAPACITY=16。而且 JDK 聲明數(shù)組的長度總是 2的n次方(一定是合數(shù))，為什么這里要求是合數(shù)，一般我們知道哈希算法為了避免沖突都要求長度是質(zhì)數(shù)，這里要求是合數(shù)，下面在介紹 HashMap 的hashCode() 方法(散列函數(shù))，我們?cè)龠M(jìn)行講解。
②、size
集合中存放key-value 的實(shí)時(shí)對(duì)數(shù)。
③、loadFactor
裝載因子，是用來衡量 HashMap 滿的程度，計(jì)算HashMap的實(shí)時(shí)裝載因子的方法為：size/capacity，而不是占用桶的數(shù)量去除以capacity。capacity 是桶的數(shù)量，也就是 table 的長度length。
默認(rèn)的負(fù)載因子0.75 是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇，建議大家不要修改，除非在時(shí)間和空間比較特殊的情況下，如果內(nèi)存空間很多而又對(duì)時(shí)間效率要求很高，可以降低負(fù)載因子loadFactor 的值；相反，如果內(nèi)存空間緊張而對(duì)時(shí)間效率要求不高，可以增加負(fù)載因子 loadFactor 的值，這個(gè)值可以大于1。
④、threshold
計(jì)算公式：capacity * loadFactor。這個(gè)值是當(dāng)前已占用數(shù)組長度的最大值。過這個(gè)數(shù)目就重新resize(擴(kuò)容)，擴(kuò)容后的 HashMap 容量是之前容量的兩倍
①、默認(rèn)無參構(gòu)造函數(shù)
/**
* 默認(rèn)構(gòu)造函數(shù)，初始化加載因子loadFactor=0.75
*/
public HashMap() {
this.loadFactor=DEFAULT_LOAD_FACTOR;
}
無參構(gòu)造器，初始化散列表的加載因子為0.75
②、指定初始容量的構(gòu)造函數(shù)
/**
*
* @param initialCapacity 指定初始化容量
* @param loadFactor 加載因子 0.75
*/
public HashMap(int initialCapacity, float loadFactor) {
//初始化容量不能小于 0 ，否則拋出異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果初始化容量大于2的30次方，則初始化容量都為2的30次方
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
//如果加載因子小于0，或者加載因子是一個(gè)非數(shù)值，拋出異常
if (loadFactor <=0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor=loadFactor;
this.threshold=tableSizeFor(initialCapacity);
}
// 返回大于等于initialCapacity的最小的二次冪數(shù)值。
// >>> 操作符表示無符號(hào)右移，高位取0。
// | 按位或運(yùn)算
static final int tableSizeFor(int cap) {
int n=cap - 1;
n |=n >>> 1;
n |=n >>> 2;
n |=n >>> 4;
n |=n >>> 8;
n |=n >>> 16;
return (n < 0) ? 1 : (n >=MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
前面我們講解哈希表的時(shí)候，我們知道是用散列函數(shù)來確定索引的位置。散列函數(shù)設(shè)計(jì)的越好，使得元素分布的越均勻。HashMap 是數(shù)組+鏈表+紅黑樹的組合，我們希望在有限個(gè)數(shù)組位置時(shí)，盡量每個(gè)位置的元素只有一個(gè)，那么當(dāng)我們用散列函數(shù)求得索引位置的時(shí)候，我們能馬上知道對(duì)應(yīng)位置的元素是不是我們想要的，而不是要進(jìn)行鏈表的遍歷或者紅黑樹的遍歷，這會(huì)大大優(yōu)化我們的查詢效率。我們看 HashMap 中的哈希算法：
static final int hash(Object key) {
int h;
return (key==null) ? 0 : (h=key.hashCode()) ^ (h >>> 16);
}
i=(table.length - 1) & hash;//這一步是在后面添加元素putVal()方法中進(jìn)行位置的確定
主要分為三步：
①、取 hashCode 值： key.hashCode()
②、高位參與運(yùn)算：h>>>16
③、取模運(yùn)算：(n-1) & hash
這里獲取 hashCode() 方法的值是變量，但是我們知道，對(duì)于任意給定的對(duì)象，只要它的 hashCode() 返回值相同，那么程序調(diào)用 hash(Object key) 所計(jì)算得到的 hash碼 值總是相同的。
為了讓數(shù)組元素分布均勻，我們首先想到的是把獲得的 hash碼對(duì)數(shù)組長度取模運(yùn)算( hash%length)，但是計(jì)算機(jī)都是二進(jìn)制進(jìn)行操作，取模運(yùn)算相對(duì)開銷還是很大的，那該如何優(yōu)化呢？
HashMap 使用的方法很巧妙，它通過 hash & (table.length -1)來得到該對(duì)象的保存位，前面說過 HashMap 底層數(shù)組的長度總是2的n次方，這是HashMap在速度上的優(yōu)化。當(dāng) length 總是2的n次方時(shí)，hash & (length-1)運(yùn)算等價(jià)于對(duì) length 取模，也就是 hash%length，但是&比%具有更高的效率。比如 n % 32=n & (32 -1)
這也解釋了為什么要保證數(shù)組的長度總是2的n次方。
再就是在 JDK1.8 中還有個(gè)高位參與運(yùn)算，hashCode() 得到的是一個(gè)32位 int 類型的值，通過hashCode()的高16位 異或 低16位實(shí)現(xiàn)的：(h=k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質(zhì)量來考慮的，這么做可以在數(shù)組table的length比較小的時(shí)候，也能保證考慮到高低Bit都參與到Hash的計(jì)算中，同時(shí)不會(huì)有太大的開銷。
下面舉例說明下，n為table的長度：
//hash(key)就是上面講的hash方法，對(duì)其進(jìn)行了第一步和第二步處理
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
*
* @param hash 索引的位置
* @param key 鍵
* @param value 值
* @param onlyIfAbsent true 表示不要更改現(xiàn)有值
* @param evict false表示table處于創(chuàng)建模式
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table為null或者長度為0，則進(jìn)行初始化
//resize()方法本來是用于擴(kuò)容，由于初始化沒有實(shí)際分配空間，這里用該方法進(jìn)行空間分配，后面會(huì)詳細(xì)講解該方法
if ((tab=table)==null || (n=tab.length)==0)
n=(tab=resize()).length;
//注意：這里用到了前面講解獲得key的hash碼的第三步，取模運(yùn)算，下面的if-else分別是 tab[i] 為null和不為null
if ((p=tab[i=(n - 1) & hash])==null)
tab[i]=newNode(hash, key, value, null);//tab[i] 為null，直接將新的key-value插入到計(jì)算的索引i位置
else {//tab[i] 不為null，表示該位置已經(jīng)有值了
Node<K,V> e; K k;
if (p.hash==hash &&
((k=p.key)==key || (key !=null && key.equals(k))))
e=p;//節(jié)點(diǎn)key已經(jīng)有值了，直接用新值覆蓋
//該鏈?zhǔn)羌t黑樹
else if (p instanceof TreeNode)
e=((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//該鏈?zhǔn)擎湵?
else {
for (int binCount=0; ; ++binCount) {
if ((e=p.next)==null) {
p.next=newNode(hash, key, value, null);
//鏈表長度大于8，轉(zhuǎn)換成紅黑樹
if (binCount >=TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key已經(jīng)存在直接覆蓋value
if (e.hash==hash &&
((k=e.key)==key || (key !=null && key.equals(k))))
break;
p=e;
}
}
if (e !=null) { // existing mapping for key
V oldValue=e.value;
if (!onlyIfAbsent || oldValue==null)
e.value=value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//用作修改和新增快速失敗
if (++size > threshold)//超過最大容量，進(jìn)行擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
①、判斷鍵值對(duì)數(shù)組 table 是否為空或?yàn)閚ull，否則執(zhí)行resize()進(jìn)行擴(kuò)容；
②、根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果table[i]==null，直接新建節(jié)點(diǎn)添加，轉(zhuǎn)向⑥，如果table[i]不為空，轉(zhuǎn)向③；
③、判斷table[i]的首個(gè)元素是否和key一樣，如果相同直接覆蓋value，否則轉(zhuǎn)向④，這里的相同指的是hashCode以及equals；
④、判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對(duì)，否則轉(zhuǎn)向⑤；
⑤、遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；
⑥、插入成功后，判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超過了最大容量threshold，如果超過，進(jìn)行擴(kuò)容。
⑦、如果新插入的key不存在，則返回null，如果新插入的key存在，則返回原key對(duì)應(yīng)的value值（注意新插入的value會(huì)覆蓋原value值）
注意1：看第 58,59 行代碼：
if (++size > threshold)//超過最大容量，進(jìn)行擴(kuò)容
resize();
這里有個(gè)考點(diǎn)，我們知道 HashMap 是由數(shù)組+鏈表+紅黑樹（JDK1.8）組成，如果在添加元素時(shí)，發(fā)生沖突，會(huì)將沖突的數(shù)放在鏈表上，當(dāng)鏈表長度超過8時(shí)，會(huì)自動(dòng)轉(zhuǎn)換成紅黑樹。
那么有如下問題：數(shù)組上有5個(gè)元素，而某個(gè)鏈表上有3個(gè)元素，問此HashMap的 size 是多大？
我們分析第58,59 行代碼，很容易知道，只要是調(diào)用put() 方法添加元素，那么就會(huì)調(diào)用 ++size(這里有個(gè)例外是插入重復(fù)key的鍵值對(duì)，不會(huì)調(diào)用，但是重復(fù)key元素不會(huì)影響size),所以，上面的答案是 7。
注意2：看第 53 、 60 行代碼：
afterNodeAccess(e);
afterNodeInsertion(evict);
這里調(diào)用的該方法，其實(shí)是調(diào)用了如下實(shí)現(xiàn)方法：
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
這都是一個(gè)空的方法實(shí)現(xiàn)，我們?cè)谶@里可以不用管，但是在后面介紹 LinkedHashMap 會(huì)用到，LinkedHashMap 是繼承的 HashMap，并且重寫了該方法，后面我們會(huì)詳細(xì)介紹。
擴(kuò)容（resize），我們知道集合是由數(shù)組+鏈表+紅黑樹構(gòu)成，向 HashMap 中插入元素時(shí)，如果HashMap 集合的元素已經(jīng)大于了最大承載容量threshold（capacity * loadFactor），這里的threshold不是數(shù)組的最大長度。那么必須擴(kuò)大數(shù)組的長度，Java中數(shù)組是無法自動(dòng)擴(kuò)容的，我們采用的方法是用一個(gè)更大的數(shù)組代替這個(gè)小的數(shù)組，就好比以前是用小桶裝水，現(xiàn)在小桶裝不下了，我們使用一個(gè)更大的桶。
JDK1.8融入了紅黑樹的機(jī)制，比較復(fù)雜，這里我們先介紹 JDK1.7的擴(kuò)容源碼，便于理解，然后在介紹JDK1.8的源碼。
//參數(shù) newCapacity 為新數(shù)組的大小
void resize(int newCapacity) {
Entry[] oldTable=table;//引用擴(kuò)容前的 Entry 數(shù)組
int oldCapacity=oldTable.length;
if (oldCapacity==MAXIMUM_CAPACITY) {//擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大(2^30)了
threshold=Integer.MAX_VALUE;///修改閾值為int的最大值(2^31-1)，這樣以后就不會(huì)擴(kuò)容了
return;
}
Entry[] newTable=new Entry[newCapacity];//初始化一個(gè)新的Entry數(shù)組
transfer(newTable, initHashSeedAsNeeded(newCapacity));//將數(shù)組元素轉(zhuǎn)移到新數(shù)組里面
table=newTable;
threshold=(int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改閾值
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity=newTable.length;
for (Entry<K,V> e : table) {//遍歷數(shù)組
while(null !=e) {
Entry<K,V> next=e.next;
if (rehash) {
e.hash=null==e.key ? 0 : hash(e.key);
}
int i=indexFor(e.hash, newCapacity);//重新計(jì)算每個(gè)元素在數(shù)組中的索引位置
e.next=newTable[i];//標(biāo)記下一個(gè)元素，添加是鏈表頭添加
newTable[i]=e;//將元素放在鏈上
e=next;//訪問下一個(gè) Entry 鏈上的元素
}
}
}
通過方法我們可以看到，JDK1.7中首先是創(chuàng)建一個(gè)新的大容量數(shù)組，然后依次重新計(jì)算原集合所有元素的索引，然后重新賦值。如果數(shù)組某個(gè)位置發(fā)生了hash沖突，使用的是單鏈表的頭插入方法，同一位置的新元素總是放在鏈表的頭部，這樣與原集合鏈表對(duì)比，擴(kuò)容之后的可能就是倒序的鏈表了。
下面我們?cè)诳纯碕DK1.8的。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab=table;
int oldCap=(oldTab==null) ? 0 : oldTab.length;//原數(shù)組如果為null，則長度賦值0
int oldThr=threshold;
int newCap, newThr=0;
if (oldCap > 0) {//如果原數(shù)組長度大于0
if (oldCap >=MAXIMUM_CAPACITY) {//數(shù)組大小如果已經(jīng)大于等于最大值(2^30)
threshold=Integer.MAX_VALUE;//修改閾值為int的最大值(2^31-1)，這樣以后就不會(huì)擴(kuò)容了
return oldTab;
}
//原數(shù)組長度大于等于初始化長度16，并且原數(shù)組長度擴(kuò)大1倍也小于2^30次方
else if ((newCap=oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr << 1; // 閥值擴(kuò)大1倍
}
else if (oldThr > 0) //舊閥值大于0，則將新容量直接等于就閥值
newCap=oldThr;
else {//閥值等于0，oldCap也等于0（集合未進(jìn)行初始化）
newCap=DEFAULT_INITIAL_CAPACITY;//數(shù)組長度初始化為16
newThr=(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//閥值等于16*0.75=12
}
//計(jì)算新的閥值上限
if (newThr==0) {
float ft=(float)newCap * loadFactor;
newThr=(newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold=newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab=(Node<K,V>[])new Node[newCap];
table=newTab;
if (oldTab !=null) {
//把每個(gè)bucket都移動(dòng)到新的buckets中
for (int j=0; j < oldCap; ++j) {
Node<K,V> e;
if ((e=oldTab[j]) !=null) {
oldTab[j]=null;//元數(shù)據(jù)j位置置為null，便于垃圾回收
if (e.next==null)//數(shù)組沒有下一個(gè)引用（不是鏈表）
newTab[e.hash & (newCap - 1)]=e;
else if (e instanceof TreeNode)//紅黑樹
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead=null, loTail=null;
Node<K,V> hiHead=null, hiTail=null;
Node<K,V> next;
do {
next=e.next;
//原索引
if ((e.hash & oldCap)==0) {
if (loTail==null)
loHead=e;
else
loTail.next=e;
loTail=e;
}
//原索引+oldCap
else {
if (hiTail==null)
hiHead=e;
else
hiTail.next=e;
hiTail=e;
}
} while ((e=next) !=null);
//原索引放到bucket里
if (loTail !=null) {
loTail.next=null;
newTab[j]=loHead;
}
//原索引+oldCap放到bucket里
if (hiTail !=null) {
hiTail.next=null;
newTab[j + oldCap]=hiHead;
}
}
}
}
}
return newTab;
}
該方法分為兩部分，首先是計(jì)算新桶數(shù)組的容量 newCap 和新閾值 newThr，然后將原集合的元素重新映射到新集合中。
相比于JDK1.7，1.8使用的是2次冪的擴(kuò)展(指長度擴(kuò)為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置。我們?cè)跀U(kuò)充HashMap的時(shí)候，不需要像JDK1.7的實(shí)現(xiàn)那樣重新計(jì)算hash，只需要看看原來的hash值新增的那個(gè)bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”。
HashMap 刪除元素首先是要找到 桶的位置，然后如果是鏈表，則進(jìn)行鏈表遍歷，找到需要?jiǎng)h除的元素后，進(jìn)行刪除；如果是紅黑樹，也是進(jìn)行樹的遍歷，找到元素刪除后，進(jìn)行平衡調(diào)節(jié)，注意，當(dāng)紅黑樹的節(jié)點(diǎn)數(shù)小于 6 時(shí)，會(huì)轉(zhuǎn)化成鏈表。
public V remove(Object key) {
Node<K,V> e;
return (e=removeNode(hash(key), key, null, false, true))==null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//(n - 1) & hash找到桶的位置
if ((tab=table) !=null && (n=tab.length) > 0 &&
(p=tab[index=(n - 1) & hash]) !=null) {
Node<K,V> node=null, e; K k; V v;
//如果鍵的值與鏈表第一個(gè)節(jié)點(diǎn)相等，則將 node 指向該節(jié)點(diǎn)
if (p.hash==hash &&
((k=p.key)==key || (key !=null && key.equals(k))))
node=p;
//如果桶節(jié)點(diǎn)存在下一個(gè)節(jié)點(diǎn)
else if ((e=p.next) !=null) {
//節(jié)點(diǎn)為紅黑樹
if (p instanceof TreeNode)
node=((TreeNode<K,V>)p).getTreeNode(hash, key);//找到需要?jiǎng)h除的紅黑樹節(jié)點(diǎn)
else {
do {//遍歷鏈表，找到待刪除的節(jié)點(diǎn)
if (e.hash==hash &&
((k=e.key)==key ||
(key !=null && key.equals(k)))) {
node=e;
break;
}
p=e;
} while ((e=e.next) !=null);
}
}
//刪除節(jié)點(diǎn)，并進(jìn)行調(diào)節(jié)紅黑樹平衡
if (node !=null && (!matchValue || (v=node.value)==value ||
(value !=null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node==p)
tab[index]=node.next;
else
p.next=node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
注意第 46 行代碼
afterNodeRemoval(node);
這也是為實(shí)現(xiàn) LinkedHashMap 做準(zhǔn)備的，在這里和上面一樣，是一個(gè)空方法實(shí)現(xiàn)，可以不用管。而在 LinkedHashMap 中進(jìn)行了重寫，用來維護(hù)刪除節(jié)點(diǎn)后，鏈表的前后關(guān)系。
①、通過 key 查找 value
首先通過 key 找到計(jì)算索引，找到桶位置，先檢查第一個(gè)節(jié)點(diǎn)，如果是則返回，如果不是，則遍歷其后面的鏈表或者紅黑樹。其余情況全部返回 null。
public V get(Object key) {
Node<K,V> e;
return (e=getNode(hash(key), key))==null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab=table) !=null && (n=tab.length) > 0 &&
(first=tab[(n - 1) & hash]) !=null) {
//根據(jù)key計(jì)算的索引檢查第一個(gè)索引
if (first.hash==hash && // always check first node
((k=first.key)==key || (key !=null && key.equals(k))))
return first;
//不是第一個(gè)節(jié)點(diǎn)
if ((e=first.next) !=null) {
if (first instanceof TreeNode)//遍歷樹查找元素
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//遍歷鏈表查找元素
if (e.hash==hash &&
((k=e.key)==key || (key !=null && key.equals(k))))
return e;
} while ((e=e.next) !=null);
}
}
return null;
}
②、判斷是否存在給定的 key 或者 value
public boolean containsKey(Object key) {
return getNode(hash(key), key) !=null;
}
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab=table) !=null && size > 0) {
//遍歷桶
for (int i=0; i < tab.length; ++i) {
//遍歷桶中的每個(gè)節(jié)點(diǎn)元素
for (Node<K,V> e=tab[i]; e !=null; e=e.next) {
if ((v=e.value)==value ||
(value !=null && value.equals(v)))
return true;
}
}
}
return false;
}
首先構(gòu)造一個(gè) HashMap 集合：
HashMap<String,Object> map=new HashMap<>();
map.put("A","1");
map.put("B","2");
map.put("C","3");
①、分別獲取 key 集合和 value 集合。
//1、分別獲取key和value的集合
for(String key : map.keySet()){
System.out.println(key);
}
for(Object value : map.values()){
System.out.println(value);
}
②、獲取 key 集合，然后遍歷key集合，根據(jù)key分別得到相應(yīng)value
//2、獲取key集合，然后遍歷key，根據(jù)key得到 value
Set<String> keySet=map.keySet();
for(String str : keySet){
System.out.println(str+"-"+map.get(str));
}
③、得到 Entry 集合，然后遍歷 Entry
//3、得到 Entry 集合，然后遍歷 Entry
Set<Map.Entry<String,Object>> entrySet=map.entrySet();
for(Map.Entry<String,Object> entry : entrySet){
System.out.println(entry.getKey()+"-"+entry.getValue());
}
④、迭代
//4、迭代
Iterator<Map.Entry<String,Object>> iterator=map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry<String,Object> mapEntry=iterator.next();
System.out.println(mapEntry.getKey()+"-"+mapEntry.getValue());
}
基本上使用第三種方法是性能最好的，
第一種遍歷方法在我們只需要 key 集合或者只需要 value 集合時(shí)使用；
第二種方法效率很低，不推薦使用；
第四種方法效率也挺好，關(guān)鍵是在遍歷的過程中我們可以對(duì)集合中的元素進(jìn)行刪除。
①、基于JDK1.8的HashMap是由數(shù)組+鏈表+紅黑樹組成，當(dāng)鏈表長度超過 8 時(shí)會(huì)自動(dòng)轉(zhuǎn)換成紅黑樹，當(dāng)紅黑樹節(jié)點(diǎn)個(gè)數(shù)小于 6 時(shí)，又會(huì)轉(zhuǎn)化成鏈表。相對(duì)于早期版本的 JDK HashMap 實(shí)現(xiàn)，新增了紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)量較大且哈希碰撞較多時(shí)，能夠極大的增加檢索的效率。
②、允許 key 和 value 都為 null。key 重復(fù)會(huì)被覆蓋，value 允許重復(fù)。
③、非線程安全
④、無序（遍歷HashMap得到元素的順序不是按照插入的順序）
參考文檔：https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#
http://www.importnew.com/20386.html
https://www.cnblogs.com/nullllun/p/8327664.html
本系列教程持續(xù)更新，可以微信搜索「 IT可樂 」第一時(shí)間閱讀。回復(fù)《電子書》有我為大家特別篩選的書籍資料
*請(qǐng)認(rèn)真填寫需求信息，我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。
