上圖可以看到，HashMap繼承了AbstractMap，實作的接口有，Map、Cloneable、Serializable。
HasMap的核心資料類型是連結清單或紅黑樹的數組，數組和List結構一樣可以實作擴容。并且有實作相對應的用于通過計算key對象的hash值定位數組索引位置的hash()方法，當數組同一位置的連結清單長度大于觸發門檻值的時候，連結清單會轉化為紅黑樹，提高周遊的效率。HashMap的資料結構如下圖。
Node
HashMap最基本的資料結構單元，核心的資料結構就是Node數組（Node<K, V> table）
TreeNode
當HashMap的核心資料結構table數組在同一個位置的連結清單長度，大于樹化觸發門檻值的時候，同一個位置的連結清單将會變成紅黑樹的結構。他們的都是Map.Entry<K,V>的實作類
KeySet
KeySet是提供給外部用于疊代通路Map的鍵的通路器類型
Values
Values是提供給外部用于疊代通路Map的值的通路器類型
EntrySet
EntrySet是提供給外部用于疊代通路Map健值對的通路器類型
上面三個分别和下面的三個疊代器類型配合使用
KeyIterator
ValueIterator
EntryIterator
疊代器類的主要作用是提供給HashMap的使用者可以通過循環通路的方式疊代通路HashMap的每個存放的元素。顧名思義，KeyIterator是用于疊代通路Map類型的鍵值，在HashMap中KeyIterator沒有直接的暴露給外部調用，而是給KeySet
類内部使用，來通路Map的鍵。同理，valueIterator是給Values類使用的，用于疊代通路Map的值。EntryIterator是給EntrySet類提供的内部類，用于疊代通路Map的健值對。
KeySpliterator
ValueSpliterator
EntrySpliterator
作用普通的的疊代器是相同的，但是分割疊代器是用于在多線程的情況下，同時周遊通路同一個HashMap對象。
桶：table數組同一個位置的一組以連結清單或紅黑樹形式存在的元素集合
判斷目前容量是否觸發擴容，如果大于容量的負載因子，進行擴容
通過HashMap的hash()方法取得hashCode
通過 (n -1) & hashCode，擷取table數組的索引位置，n為table的length
如果目前元素的位置是空的話，直接存入。
如果位置不為空，判斷kv對的hash值與已存在的元素的是否相同，如果相同，則進行覆寫處理，不相同進行生成連結清單
如果相同位置的連結清單長度符合樹化門檻值，則将連結清單轉化為紅黑樹
可以看到HashMap用于定位數組索引的方法是<code>(n -1) & hash</code>，原理同十進制的取模運算。位運算直接對記憶體資料進行操作，不需要轉成十進制，是以位運算要比取模運算的效率更高，是以HashMap在計算元素要存放在數組中的index的時候，使用位運算代替了取模運算。之是以可以做等價代替，前提是要求HashMap的容量一定要是2^n。至于為什麼不是2，4，8而是16。因為2，4，8的容量太小，造成過早的擴容，而16以上32太大，浪費記憶體空間。
之前是連結清單結構，搜尋的時間複雜度是O(N)，之後的紅黑樹結構的搜尋時間複雜度是O(logN)明顯的紅黑樹的搜尋效率更高。
在上面的問題中已經說明，為了提高運算效率，不需要再轉成十進制來運算。
《JavaGuide》
沐風的原創文章