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