? ? ? ? 想必經(jīng)歷過面試的人很多都能被問到這個問題桐款，當(dāng)然小編也不例外咸这，今天就給大家剖析一下HashMap在jdk1.8中的結(jié)構(gòu)及其使用，分享在這鲁僚，從中自己也在學(xué)習(xí)炊苫，不斷積累技術(shù)和大家一起分享
一：概述
? ? ? HashMap最早在jdk1.2中就存在了，HashMap繼承自父類（AbstractMap）冰沙，實現(xiàn)了Map侨艾、Cloneable、Serializable接口拓挥，底層思想是基于散列算法實現(xiàn)的唠梨，HashMap可以用null作為鍵，也可以用null作為值侥啤，當(dāng)存儲的鍵為null時当叭，對應(yīng)計算的結(jié)果是0茬故，用0作為鍵值的，HashMap不是線程安全的蚁鳖，如果使用HashMap要滿足線程安全磺芭，可以使用Collectio類的的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap類醉箕。
一：數(shù)據(jù)的存儲結(jié)構(gòu)
? ? ? 在jdk1.7中的HashMap中的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+單鏈表的組合钾腺，使用鏈表處理hash值沖突的元素，而存在的問題就是當(dāng)hash鍵值相等的情況較多時讥裤，都會將值保存在一個單鏈表上放棒，也就是其中的一個桶中，導(dǎo)致通過key值去查找效率很低己英，所以在jdk1.8中间螟，HashMap采用了數(shù)組+鏈表+紅黑樹來實現(xiàn)，這在結(jié)構(gòu)上與jdk 1.7最大的不同损肛，而在jdk1.8中厢破，如果hash鍵值沖突較多時，單鏈表的長度超過規(guī)定的臨界值(8)時,就會將鏈表轉(zhuǎn)換成紅黑樹的結(jié)構(gòu)存儲荧关，這樣就能高效的查詢溉奕，提高HashMap的查詢效率褂傀。
? ? ? 1. HashMap成員變量:?
? ? ? ? ? ? * The default initial capacity - MUST be a power of two.
? ? ? ? ? ? *? 默認HashMap初始化的容量為16忍啤，且長度必須為2的冪等
? ? ? ? ? ? */
? ? ? ? ? ? static final int DEFAULT_INITIAL_CAPACITY = 16;
? ? ? ? /**
? ? ? ? ? ? * The table, resized as necessary. Length MUST Always be a power of two.
? ? ? ? ? ? ? ? * 數(shù)組是存儲HashMap的鏈表表頭
? ? ? ? ? ? */
? ? ? ? ? ? transient Entry<K,V>[] table
? ? ? ? ? ? /** 最大初始容量，2^30 */
? ? ? ? ? ? static final int MAXIMUM_CAPACITY = 1 << 30;
? ? ? ? ? /** 負載因子仙辟，默認0.75同波，負載因子越小，hash沖突機率越低 */
? ? ? ? ? static final float DEFAULT_LOAD_FACTOR = 0.75f;
? ? ? ? ? /** 初始化一個Entry的空數(shù)組 */
? ? ? ? ? static final Entry<?,?>[] EMPTY_TABLE = {};
? ? ? ? ? /** HashMap實際存儲的元素個數(shù) */
? ? ? ? ? transient int size;
? ? ? ? ? /** 臨界值（HashMap 實際能存儲的大械）,公式為(threshold = capacity * loadFactor) */
? ? ? ? ? int threshold;
? ? ? ? ? /** 負載因子 */
? ? ? ? final float loadFactor;
? ? ? ? ? /** HashMap的結(jié)構(gòu)被修改的次數(shù)未檩，用于迭代器 */
? ? ? ? transient int modCount;
2：HashMap的數(shù)組
圖1
3：紅黑樹結(jié)構(gòu)及性質(zhì)介紹
? ? 紅黑樹其實就是一種自平衡的二叉查找樹，他這個自平衡的特性就是針對HashMap中鏈表可能會很長粟焊，做出的優(yōu)化冤狡。紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色项棠。在二叉查找中有的性質(zhì)外悲雳，紅黑樹也有自己的特點:
特點1. 節(jié)點都是紅色或黑色，所以稱為紅黑樹香追。
特點2. 樹的根節(jié)點是黑色合瓢。
特點3. 每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的透典。
特點4. 每個紅色節(jié)點的兩個子節(jié)點都是黑色晴楔。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
特點5. 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點顿苇。
static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
? ? TreeNode<k,v> parent;? // 父節(jié)點
? ? TreeNode<k,v> left; //左子樹
? ? TreeNode<k,v> right;//右子樹
? ? TreeNode<k,v> prev;? ? // needed to unlink next upon deletion
? ? boolean red;? ? //顏色屬性
? ? TreeNode(int hash, K key, V val, Node<k,v> next) {
? ? ? ? super(hash, key, val, next);
? ? }
4:HashMap的擴容機制
? ? HashMap中含有resize()方法，當(dāng)HashMap的元素個數(shù)超過數(shù)組的容量長度(length)HashMap就會進行擴容,默認情況下數(shù)組容量是16,當(dāng)HashMap中的元素個數(shù)超過12個時(16*0.75 == 12),就超過了臨界值(也就是源碼中的threshold),這時税弃，HashMap就需要把數(shù)組大小擴容到原來的一倍,然后通過rehash(再哈希),重新計算每個元素在數(shù)組中的位置.
獲取更多視頻資料纪岁，請關(guān)注微信公眾號
