前言

　　由于HashMap在java開發(fā)中占有的舉足輕重的地位，所以對hashmap的一些重要性質(zhì)和優(yōu)化點進行一些總結(jié)就顯得尤為重要了，同時也能在實際工作中提高hashMap的效率，但對于全面介紹分析hashMap，本文不做過多概述。本文主要是希望對java初學者或者是有意對hashMap的使用效率有更深了解的的讀者提供幫助。

一、hashMap重要屬性

　　1、

　　/** 　 　* The default initial capacity - MUST be a power of two.(map的初始大小) 　　*/　　DEFAULT_INITIAL_CAPACITY = 16;(默認大小)

　　2、　

　　/** 　　* The maximum capacity, used if a higher value is implicitly specified 　 　* by either of the constructors with arguments. 　　* MUST be a power of two <= 1<<30.

　　 *(最大容量，如果指定的容易大于最大容量，將使用此值) 　　*/　　MAXIMUM_CAPACITY = 1 << 30;(最大容量)

　　3、　

　　/** 　　* The load factor used when none specified in constructor. 　　*/　　DEFAULT_LOAD_FACTOR = 0.75f;(默認負載因子)

　　4、　

　　/** 　　* The next size value at which to resize (capacity * load factor). 　　* (map是否擴容的決定性因素) 　　*/ 　　threshold;

　　5、

　　bucket(數(shù)組中最小存儲單元，在源碼中為Entry)

二、HashMap創(chuàng)建到put流程基本介紹

　　hashMap由其名字可以知道，它使用的是哈希算法來管理存儲其中的對象的，具體是用數(shù)組和鏈表兩種數(shù)據(jù)結(jié)構管理的。

　　1、初始化

　　　　如果參數(shù)均為指定，則使用默認值初始化　　

　　　　this.loadFactor = DEFAULT_LOAD_FACTOR; 　　　　threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 　　　　table = new Entry[DEFAULT_INITIAL_CAPACITY];(這里就是初始化了一個數(shù)組，用于存放對象,buckets)

　　　　如果指定loadFactor和initialCapacity，則

　　　　this.loadFactor =loadFactor

　　　　程序?qū)⒗胕nitialCapacity計算一個新的capacity，capacity大小為大于初始容易值的最小的2的整數(shù)次冪的值(如初始容量為15，則capacity為16.初始為3，則capacity為4)，

　　　　threshold = (int)(capacity * loadFactor);

　　 table = new Entry[capacity];

　　2、put

　　　　put過程中，如果一個對象hash到同一個bucket，則會形成一個鏈表，鏈表查詢是線性的。在對象放入map后，會檢查map大小。如果map的size大于或等于threshold(capacity * load factor)，注意不是在size大于capacity時擴容，則會以map兩倍容量擴容(此步驟設計到重新申請空間和計算hash值，性能消耗比較大)

　　三、優(yōu)化hashMap

　　　　如果哈希映射的內(nèi)部數(shù)組只包含一個元素，則所有項將映射到此數(shù)組位置，從而構成一個較長的鏈接列表。由于我們的更新和訪問使用了對鏈接列表的線性搜索，而這要比 Map 中的每個數(shù)組索引只包含一個對象的情形要慢得多，因此這樣做的效率很低。訪問或更新鏈接列表的時間與列表的大小線性相關，而使用哈希函數(shù)問或更新數(shù)組中的單個元素則與數(shù)組大小無關 — 就漸進性質(zhì)（Big-O 表示法）而言，前者為 O(n)，而后者為 O(1)。因此，使用一個較大的數(shù)組而不是讓太多的項聚集在太少的數(shù)組位置中是有意義的。

　　　　調(diào)整 Map 實現(xiàn)的大小

　　　　在哈希術語中，內(nèi)部數(shù)組中的每個位置稱作“存儲桶”(bucket)，而可用的存儲桶數(shù)（即內(nèi)部數(shù)組的大小）稱作容量 (capacity)。為使 Map 對象有效地處理任意數(shù)目的項，Map 實現(xiàn)可以調(diào)整自身的大小。但調(diào)整大小的開銷很大。調(diào)整大小需要將所有元素重新插入到新數(shù)組中，這是因為不同的數(shù)組大小意味著對象現(xiàn)在映射到不同的索引值。先前沖突的鍵可能不再沖突，而先前不沖突的其他鍵現(xiàn)在可能沖突。這顯然表明，如果將 Map 調(diào)整得足夠大，則可以減少甚至不再需要重新調(diào)整大小，這很有可能顯著提高速度。

　　　　使用 1.4.2 JVM 運行一個簡單的測試，即用大量的項（數(shù)目超過一百萬）填充 HashMap。表 5 顯示了結(jié)果，并將所有時間標準化為已預先設置大小的服務器模式（關聯(lián)文件中的 。對于已預先設置大小的 JVM，客戶端和服務器模式 JVM 運行時間幾乎相同（在放棄 JIT 編譯階段后）。但使用 Map 的默認大小將引發(fā)多次調(diào)整大小操作，開銷很大，在服務器模式下要多用 50% 的時間，而在客戶端模式下幾乎要多用兩倍的時間！

表 5：填充已預先設置大小的 HashMap 與填充默認大小的 HashMap 所需時間的比較

　　　　使用負載因子

為確定何時調(diào)整大小，而不是對每個存儲桶中的鏈接列表的深度進行記數(shù)，基于哈希的 Map 使用一個額外參數(shù)并粗略計算存儲桶的密度。Map 在調(diào)整大小之前，使用名為“負載因子”的參數(shù)指示 Map 將承擔的“負載”量，即它的負載程度。負載因子、項數(shù)（Map 大小）與容量之間的關系簡單明了：

• 如果（負載因子）x（容量）>（Map 大小），則調(diào)整 Map 大小

　　　　例如，如果默認負載因子為 0.75，默認容量為 11，則 11 x 0.75 = 8.25，該值向下取整為 8 個元素。因此，如果將第 8 個項添加到此 Map，則該 Map 將自身的大小調(diào)整為一個更大的值。相反，要計算避免調(diào)整大小所需的初始容量，用將要添加的項數(shù)除以負載因子，并向上取整，例如，

• 對于負載因子為 0.75 的 100 個項，應將容量設置為 100/0.75 = 133.33，并將結(jié)果向上取整為 134（或取整為 135 以使用奇數(shù)）

　　奇數(shù)個bucket使 map 能夠通過減少沖突數(shù)來提高執(zhí)行效率。雖然我所做的測試（關聯(lián)文件中的 并未表明質(zhì)數(shù)可以始終獲得更好的效率，但理想情形是容量取質(zhì)數(shù)。1.4 版后的某些 Map（如 HashMap 和 LinkedHashMap，而非 Hashtable 或 IdentityHashMap）使用需要 2 的冪容量的哈希函數(shù)，但下一個最高 2 的冪容量由這些 Map 計算，因此您不必親自計算。

　　負載因子本身是空間和時間之間的調(diào)整折衷。較小的負載因子將占用更多的空間，但將降低沖突的可能性，從而將加快訪問和更新的速度。使用大于 0.75 的負載因子可能是不明智的，而使用大于 1.0 的負載因子肯定是不明知的，這是因為這必定會引發(fā)一次沖突。使用小于 0.50 的負載因子好處并不大，但只要您有效地調(diào)整 Map 的大小，應不會對小負載因子造成性能開銷，而只會造成內(nèi)存開銷。但較小的負載因子將意味著如果您未預先調(diào)整 Map 的大小，則導致更頻繁的調(diào)整大小，從而降低性能，因此在調(diào)整負載因子時一定要注意這個問題。