HashMap的了解（JDK1.7）

基于哈希函數的鍵值映射集合；

底層資料結構是數組+連結清單；

數組展現在内部的Entry類型的數組table；

連結清單展現在内部類Entry中的Entry類型屬性next，用于存放下一個節點的引用；

向HashMap中存放元素：hashMap.put(“name”,“paul”);

既然底層是數組，按我們一般數組存放元素的方法：

int[] nums = new int[10];

nums[0] = 0;

是需要指定數組下标的，那put時究竟元素放在數組的什麼位置了呢？這就引出了哈希函數；

哈希函數簡單了解為給定一個值，該函數會傳回另一個值，然後根據計算出的值再想辦法找到一個數組下标，僞代碼為：

int hash = hash(key);//根據key計算出哈希值

int index = hash % arr.length;//根據哈希值與數組長度取餘，得出數組下标（實際HashMap使用了更高效的按位與運算）

下标找到了，那就把元素放在該數組該下标位置了，但是如果多個元素key根據哈希函數和取餘算出了相同的數組下标時怎麼辦呢？

其實這就是哈希沖突，解決辦法有開放位址法、再哈希法、拉鍊法等，HashMap使用拉鍊法解決該問題。當有多個元素都計算出了

相同的下标時，就把新元素放在連結清單的頭，next指針指向原來連結清單的頭。

随着放入的元素越來越多，哈希沖突越來越嚴重，連結清單越來越長，哈希表的時間複雜度從O(1)逐漸向O(n)發展，性能越來越差，怎麼辦呢？

擴容吧。什麼時候擴容？擴容多少？如何擴容？

當容量超過門檻值時擴容，門檻值=容量負載因子，預設160.75=12；

擴容擴一倍，即擴容後容量是原來的2倍；

申請記憶體，建立一個容量是原來2倍的Entry數組，然後把原數組中元素轉移到新數組中，元素存放位置為：原下标或

（原下标+擴容大小）；

最佳實踐：

擴容需要新申請記憶體，轉移元素，回收舊數組記憶體，耗時多吧，怎麼辦呢？如果能預估哈希表中的元素個數，那就在初始化哈希表時指定一個初始化容量，減少頻繁擴容申請記憶體回收舊記憶體的性能消耗。（阿裡代碼規約推薦：集合初始化時，指定集合初始值大小）

如果對讀性能要求高，那就調低負載因子，理想情況下遇到哈希沖突就擴容，使得每個數組下标隻存放一個元素，那就能一直保持O(1)的時間複雜度；

如果記憶體不太夠，那就調高負載因子，盡量不讓數組擴容；