摘要：通過鏈表法解決沖突問題，每個都有一個指針指向下一個，沖突元素不是鍵相同，而是值相同會構成一個鏈表。并且最新插入的鍵值對始終位于鏈表首部。
哈希表定義：根據設定的hash函數和處理沖突的方式（開放定址、公共溢出區、鏈地址、重哈希...）將一組關鍵字映射到一個有限的連續的地址集上（即bucket數組或桶數組），并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表稱為hash表；這一映射過程稱為散列，所得存儲位置稱為哈希地址或散列地址。
一、定義
HashMap實現了Map接口，繼承AbstractMap。其中Map接口定義了鍵映射到值的規則，而AbstractMap類提供 Map 接口的骨干實現，以最大限度地減少實現此接口所需的工作。
public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable
二、構造函數
HashMap提供了三個構造函數：
HashMap()：構造一個具有默認初始容量 (16) 和默認加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：構造一個帶指定初始容量和默認加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：構造一個帶指定初始容量和加載因子的空 HashMap。
容量表示哈希表中桶的數量，初始容量是創建哈希表時的容量； 裝載因子：loadfactor = 表中填入的記錄數/哈希表的長度
所以loadfactor標志著哈希表的裝滿程度，直觀的看，裝載因子越小，發生沖突的概率越?。ㄒ驗橥爸羞€沒裝幾個數據，就需要擴容），也就是查找性能越好，但同時浪費的空間就變大。相反，裝載因子越大，發生沖突的概率越大（等到桶快填滿時才能擴容，比如，采用鏈表法處理沖突，在此種情況下，會導致鏈表過長），查找性能越差，同時浪費的空間會減少。
三、數據結構
我們知道在Java中最常用的兩種結構是數組和模擬指針(引用)，幾乎所有的數據結構都可以利用這兩種來組合實現，HashMap也是如此。實際上HashMap是一個“鏈表散列”（數組和鏈表的結合體）。
可見，HashMap底層實現還是數組（橫行），只是數組的每一項（縱列）都是一條鏈。Entry為HashMap的內部類，它包含了鍵key、值value、下一個節點next，以及hash值，這是非常重要的，正是由于Entry才構成了table數組的項為鏈表。
總結
*1.HashMap的默認大小為16，即桶數組的默認長度為16；
2.HashMap的默認裝載因子是0.75；
3.HashMap內部的桶數組存儲的是Entry對象，也就是鍵值對對象。
4.構造器支持指定初始容量和裝載因子，為避免數組擴容帶來的性能問題，建議根據需求指定初始容量。裝載因子盡量不要修改，0.75是個比較靠譜的值。
5.桶數組的長度始終是2的整數次方（大于等于指定的初始容量），這樣做可以減少沖突概率，提高查找效率。（可以從indexfor函數中看出，h&(length-1),若length為奇數，length-1為偶數那么h&(length-1)結果的最后一位必然為0，也就是說所有鍵都被散列到數組的偶數下標位置,這樣會浪費近一半空間。另外，length為2的整數次方也保證了h&(length-1)與h%length等效）.
6.HashMap接受null鍵；
7.HashMap不允許鍵重復，但是值是可以重復的。若鍵重復，那么新值會覆蓋舊值。
8.HashMap通過鏈表法解決沖突問題，每個Entry都有一個next指針指向下一個Entry，沖突元素（不是鍵相同，而是hash值相同）會構成一個鏈表。并且最新插入的鍵值對始終位于鏈表首部。
9.當容量超過閾值（threshold）時,會發生擴容，擴容后的數組是原數組的兩倍。擴容操作需要開辟新數組，并對原數組中所有鍵值對重新散列，非常耗時。我們應該盡量避免HashMap擴容。
10.HashMap非線程安全。*
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66106.html
