Java是一種可以撰寫跨平臺應(yīng)用軟件的面向?qū)ο蟮某绦蛟O(shè)計語言算利。Java 技術(shù)具有卓越的通用性册踩、高效性、平臺移植性和安全性效拭，廣泛應(yīng)用于PC暂吉、數(shù)據(jù)中心、游戲控制臺缎患、科學(xué)超級計算機慕的、移動電話和互聯(lián)網(wǎng)，同時擁有全球最大的開發(fā)者專業(yè)社群挤渔。

給你java學(xué)習(xí)路線：html-css-js-jq-javase-數(shù)據(jù)庫-jsp-servlet-Struts2-hibernate-mybatis-spring4-springmvc-ssh-ssm

小編推薦一個學(xué)Java的學(xué)習(xí)裙【 六五零肮街，五五四，六零七 】判导，無論你是大牛還是小白嫉父，是想轉(zhuǎn)行還是想入行都可以來了解一起進步一起學(xué)習(xí)！裙內(nèi)有開發(fā)工具眼刃，很多干貨和技術(shù)資料分享绕辖！

HashMap?是基于?Map?的鍵值對映射表，底層是通過數(shù)組擂红、鏈表仪际、紅黑樹（JDK1.8加入）來實現(xiàn)的。

HashMap結(jié)構(gòu)

HashMap?中存儲元素昵骤，是將?key?和?value?封裝成了一個?Node?树碱，先以一個?Node?數(shù)組的來存儲，通過?key?的?hashCode?來計算?hash?值涉茧，根據(jù)?hash?值和?HashMap?的大小確定存入元素在數(shù)組中的位置赴恨。當(dāng)?hashCode?相同時，即產(chǎn)生了相同的數(shù)組索引位置伴栓，那么就會通過單向鏈表的形式來繼續(xù)存儲伦连。

static class Node implements Map.Entry { final int hash; final K key;V value;Node next;Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next;} // 省略部分代碼... }

HashMap?中所有的映射都保存在節(jié)點?Node?中雨饺，同時為了解決發(fā)生?hash?碰撞的沖突，節(jié)點可以持有下一個節(jié)點的引用惑淳，以形成一個單向鏈表额港。

HashMap結(jié)構(gòu)圖（JDK1.7及之前）

在JDK1.8，?HashMap?又做了一些改動歧焦，當(dāng)數(shù)組?table?某個索引位置的上鏈表的長度大于8的話移斩，則會將鏈表轉(zhuǎn)化為紅黑樹。

static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; // red-black tree linksTreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletionboolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next);} // 省略部分代碼... }

同樣地绢馍，映射的key-value就保存在?TreeNode?中向瓷。?parent?、?left?舰涌、?right?持有相應(yīng)節(jié)點的引用形成紅黑樹猖任。

小編推薦一個學(xué)Java的學(xué)習(xí)裙【 六五零，五五四瓷耙，六零七 】朱躺，無論你是大牛還是小白，是想轉(zhuǎn)行還是想入行都可以來了解一起進步一起學(xué)習(xí)搁痛！裙內(nèi)有開發(fā)工具长搀，很多干貨和技術(shù)資料分享！

HashMap結(jié)構(gòu)圖（JDK1.8）

HashMap源碼分析

主要屬性：

transient Node[] table; // 數(shù)組transient int size; // 大小int threshold // 擴容閾值final float loadFactor; // 加載因子鸡典，默認(rèn)值為0.75

構(gòu)造方法：

// 使用默認(rèn)的初始容量和加載因子public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}// 指定初始容量源请，使用默認(rèn)的加載因子public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 用現(xiàn)有的Map來構(gòu)造一個新的HashMappublic HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}// 根據(jù)自定義的初始容量和加載因子來構(gòu)造HashMappublic HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) {initialCapacity = MAXIMUM_CAPACITY;} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {initialCapacity = DEFAULT_INITIAL_CAPACITY;} if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " +loadFactor);threshold = initialCapacity;init();}

構(gòu)造函數(shù)主要是設(shè)置?HashMap?的初始容量，以及擴容的加載因子彻况。?HashMap(Map m)?構(gòu)造函數(shù)根據(jù)已有的映射來構(gòu)造新的?HashMap?巢钓，它同樣采用的默認(rèn)的加載因子，并將?m?中的元素添加到新構(gòu)造的?HashMap?中疗垛。

數(shù)據(jù)存放：

public void putAll(Map m) {putMapEntries(m, true);}final void putMapEntries(Map m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // pre-sizefloat ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY); if (t > threshold)threshold = tableSizeFor(t);} else if (s > threshold)resize(); for (Map.Entry e : m.entrySet()) {K key = e.getKey();V value = e.getValue();putVal(hash(key), key, value, false, evict);}}}

putAll?方法直接調(diào)用?putMapEntries?。?putMapEntries?方法中先根據(jù)已有的?Map?中的元素數(shù)量對新構(gòu)造的?HashMap?進行擴容硫朦，然后遍歷舊的?Map?贷腕，取出元素存放到新的?HashMap中。

// 存放key-valuepublic V put(K key, V value) { return putVal(hash(key), key, value, false, true);}// 根據(jù)key的hashCode來計算hash值static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node[] tab; Node p; int n, i; // table為null的話咬展，進行初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; // 根據(jù)（n-1）&hash來計算出元素在數(shù)組中的位置iif ((p = tab[i = (n - 1) & hash]) == null) // 如果數(shù)組中該位置沒有元素泽裳，即tab[i]==null,則直接構(gòu)建Node存放在該位置tab[i] = newNode(hash, key, value, null); else { // tab[i]不為nullNode e; K k; // 如果數(shù)組中已有的節(jié)點tab[i]與需要新存入的元素的key相同，則直接替換掉tab[i]if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p; else if (p instanceof TreeNode) // 如果tab[i]為紅黑樹節(jié)點破婆，則直接存入紅黑樹 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { // tab[i]為鏈表的第一個節(jié)點涮总，遍歷鏈表，將新的節(jié)點加入到鏈表的末尾for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) {p.next = newNode(hash, key, value, null); // 如果鏈表的長度大于閾值祷舀，則將鏈表轉(zhuǎn)換為紅黑樹if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash); break;} // 如果鏈表中存在與新加入的元素key相同瀑梗，則直接替換掉if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break;p = e;}} if (e != null) { // existing mapping for keyV oldValue = e.value; if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e); return oldValue;}}++modCount; // 添加完成后烹笔，檢查是否需要擴容if (++size > threshold)resize();afterNodeInsertion(evict); return null;}

put?方法的主要邏輯：根據(jù)添加節(jié)點的?hash?值計算計算它在數(shù)組中的位置?i?，判斷?tab[i]是否為空抛丽，為空則直接加入谤职；不為空的話，需要判斷該節(jié)點的?key?是否與新加入的節(jié)點的key相同亿鲜，相同的話直接替換允蜈；如果不同則需要判斷?tab[i]?節(jié)點是否是紅黑樹節(jié)點，如果是紅黑樹節(jié)點蒿柳，則直接加入到紅黑樹中饶套；如果不是紅黑樹節(jié)點，那肯定就是鏈表的第一個節(jié)點了垒探，遍歷鏈表妓蛮，在遍歷的過程中還需要判斷是否與鏈表中已有節(jié)點的?key?相同，如果相同叛复，同樣直接替換掉仔引，都不同的話就直接添加到鏈表的末尾。并且呢褐奥，加入鏈表后還需要判斷鏈表的長度是否超過了閾值8咖耘，超過了的話，需要將鏈表轉(zhuǎn)換為紅黑樹撬码。

HashMap?在添加數(shù)據(jù)的時候儿倒，會判斷當(dāng)前數(shù)據(jù)量是否超過設(shè)定的閾值，如果超過的話會進行擴容呜笑，在擴容過程中會將已添加的數(shù)據(jù)進行重新添加夫否，以致原來添加元素的順序和位置都改變了，所以?HashMap?不能保證元素的存入取出順序叫胁。

刪除數(shù)據(jù)：

// 根據(jù)key刪除數(shù)據(jù)public V remove(Object key) {Node e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;}// 根據(jù)key-value刪除數(shù)據(jù)@Overridepublic boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) != null;}// 刪除節(jié)點final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {Node[] tab; Node p; int n, index; // 根據(jù)hash值得到數(shù)組索引位置的節(jié)點pif ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node node = null, e; K k; V v; // p節(jié)點的key與需要刪除的節(jié)點的key相同的話凰慈，則說明p就是需要刪除的節(jié)點if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p; // 賦值給nodeelse if ((e = p.next) != null) { if (p instanceof TreeNode) // p節(jié)點為紅黑樹節(jié)點，從紅黑樹中獲取匹配的刪除節(jié)點node = ((TreeNode)p).getTreeNode(hash, key); else { // p節(jié)點為鏈表的第一個節(jié)點驼鹅，遍歷鏈表微谓，找到匹配的刪除節(jié)點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é)點node不為null的話，刪除nodeif (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) { if (node instanceof TreeNode) // 從紅黑樹中刪除((TreeNode)node).removeTreeNode(this, tab, movable); else if (node == p) // 從數(shù)組中刪除 tab[index] = node.next; else// 從鏈表中刪除p.next = node.next;++modCount;--size;afterNodeRemoval(node); return node;}} return null;}

remove?的邏輯和加入元素的邏輯相似输钩，依次從數(shù)組豺型、紅黑樹、鏈表中找到匹配的刪除節(jié)點來刪除买乃。

clear?方法：

public void clear() {Node[] tab;modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i)tab[i] = null;}}

clear?方法要簡單些姻氨，直接遍歷數(shù)組tab，將數(shù)組中所有元素都置空即可剪验。

最后

對于?HashMap?肴焊，我們只要知道了它的底層結(jié)構(gòu)前联，要理解它的實現(xiàn)原理還是非常簡單。在JDK1.8之后抖韩，加入了紅黑樹的結(jié)構(gòu)蛀恩，使?HashMap?的效率比之前的版本又優(yōu)化了很多，關(guān)于鏈表轉(zhuǎn)化為紅黑樹茂浮，以及紅黑樹轉(zhuǎn)鏈表的具體實現(xiàn)等細(xì)節(jié)后續(xù)再做分析双谆。

小編推薦一個學(xué)Java的學(xué)習(xí)裙【 六五零，五五四席揽，六零七 】顽馋，無論你是大牛還是小白，是想轉(zhuǎn)行還是想入行都可以來了解一起進步一起學(xué)習(xí)幌羞！裙內(nèi)有開發(fā)工具寸谜，很多干貨和技術(shù)資料分享！

1属桦、具有1-5工作經(jīng)驗的熊痴，面對目前流行的技術(shù)不知從何下手，

需要突破技術(shù)瓶頸的聂宾。2果善、在公司待久了，過得很安逸系谐，

但跳槽時面試碰壁巾陕。需要在短時間內(nèi)進修、跳槽拿高薪的纪他。

3鄙煤、如果沒有工作經(jīng)驗，但基礎(chǔ)非常扎實茶袒，對java工作機制梯刚，

常用設(shè)計思想，常用java開發(fā)框架掌握熟練的薪寓。

4乾巧、覺得自己很牛B，一般需求都能搞定预愤。

但是所學(xué)的知識點沒有系統(tǒng)化，很難在技術(shù)領(lǐng)域繼續(xù)突破的咳胃。

5. 高級架構(gòu)備植康！

6.阿里Java高級知識點，分享知識展懈，

多年工作經(jīng)驗的梳理和總結(jié)销睁，帶著大家全面供璧、

科學(xué)地建立自己的技術(shù)體系和技術(shù)認(rèn)知！