哈希表（hash table）也叫散列表，是一種非常重要的數據結構，應用場景及其豐富，許多緩存技術（比如memcached）的核心其實就是在
內存中維護一張大的哈希表。HashMap基於哈希表的 Map 接口的實現。此實現提供所有可選的映射操作，並允許使用 null 值和 null 鍵。
HashMap的實現
HashMap的主幹是一個Node數組。Node是HashMap的基本組成單元，每一個Node包含一個key-value鍵值對。其中next也是一個Node對象，它就是用來處理hash衝突的，形成一個鏈表。
HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希衝突而存在的，如果定位到的數組位置不含鏈表（當前entry的next指向null）,那麼對於查找，添加等操作很快，僅需一次尋址即可；如果定位到的數組包含鏈表，對於添加操作，其時間複雜度為O(n)，首先遍歷鏈表，存在即覆蓋，否則新增；對於查找操作來講，仍需遍歷鏈表，然後通過key對象的equals方法逐一比對查找。所以，性能考慮，HashMap中的鏈表出現越少，性能才會越好。
哈希衝突
HashMap的底層主要是基於數組和鏈表來實現的，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置。HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同，計算出來的hash值就一樣。如果存儲的對象對多了，就有可能不同的對象所算出來的hash值是相同的，這就出現了所謂的hash衝突。學過數據結構的同學都知道，解決hash衝突的方法有很多，HashMap底層是通過鏈表來解決hash衝突的。
關鍵屬性
transient Entry[] table;//存儲元素的實體數組
transient int size;//存放元素的個數
int threshold; //臨界值 當實際大小超過臨界值時，會進行擴容threshold = 加載因子*容量
final float loadFactor; //加載因子
transient int modCount;//被修改的次數
加載因子越大,填滿的元素越多,好處是,空間利用率高了,但:衝突的機會加大了.鏈表長度會越來越長,查找效率降低。
反之,加載因子越小,填滿的元素越少,好處是:衝突的機會減小了,但:空間浪費多了.表中的數據將過於稀疏（很多空間還沒用，就開始擴容了）
衝突的機會越大,則查找的成本越高.
-----------------------------------
本人現處廣州從事互聯網工作多年，資深技術人員、管理人員。願結識有互聯網業務的技術人員或企業人員。
閱讀更多 程序員的一些事 的文章
