前言

　　由于HashMap在java開發中占有的舉足輕重的地位，所以對hashmap的一些重要性質和優化點進行一些總結就顯得尤為重要了，同時也能在實際工作中提高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(數組中最小存儲單元，在源碼中為Entry)

二、HashMap創建到put流程基本介紹

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

　　1、初始化

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

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

　　　　如果指定loadFactor和initialCapacity，則

　　　　this.loadFactor =loadFactor

　　　　程序將利用initialCapacity計算一個新的capacity，capacity大小為大于初始容易值的最小的2的整數次冪的值(如初始容量為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值，性能消耗比較大)

　　三、優化hashMap

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

　　　　調整 Map 實現的大小

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

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

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

　　　　使用負載因子

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

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

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

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

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

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