Java HashMap完成原理 源碼分析。本站提示廣大學習愛好者：（Java HashMap完成原理 源碼分析）文章只能為提供參考，不一定能成為您想要的結果。以下是Java HashMap完成原理 源碼分析正文
HashMap是基於哈希表的Map接口完成，提供了一切可選的映射操作，並允許運用null值和null建，不同步且不保證映射順序。上面記載一下研討HashMap完成原理。
HashMap外部存儲
在HashMap外部，經過維護一個 瞬時變量數組table (又稱：桶) 來存儲一切的鍵值對關系，桶 是個Entry對象數組，桶 的大小可以按需調整大小，長度必需是2的次冪。如下代碼：
/**
* 一個空的entry數組，桶 的默許值
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* 桶，按需調整大小，但必需是2的次冪
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
初始容量與負載因子
HashMap有兩個參數影響功能，初始容量和負載因子。容量是哈希表中 桶 的數量，初始容量只是哈希表在創立時的容量，負載因子是哈希表在其容量自動添加之前可以到達多滿的一種尺度。當哈希表中條目數超出了負載因子與以後容量的乘積時，則要對該Hash表停止rehash操作（即重建外部數據構造），重建時以以後容量的兩倍數目新建。可以經過結構器設置初始容量與負載因子，默許初始容量是16個條目，最大容量是2^30次方個條目，默許負載因子是0.75
桶 好像一個存水的水桶，它默許的初始存水容量是16個單位的水，默許在灌水灌到16*0.75時，在下次添加數據時會先擴大容量，擴大到32單位。0.75就是負載因子，初始容量與負載因子可以經過創立水桶的時分停止設置。水桶最大的容量是2的30次方個單位的水。現在始容量設置的數量大於最大容量時，以最大容量為准。當擴展時假如大於等於最大容量時則直接前往。
如下為HashMap的局部源碼，定義了默許初始容量、負載因子及其他一些常量：
/**
* 默許初始化容量，必需為2的次冪The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量，假如經過結構函數參數中傳遞初始化容量大於該最大容量了，也會運用該容量為初始化容量* 必需是2的次冪且小於等於2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默許的負載因子，可以經過結構函數指定
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 一個空的數組表，當 桶沒有初始化的時分
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* 桶 , 存儲一切的鍵值對條目，可以按需調整大小，長度大小必需為2的次冪
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* Map中鍵值對的數量，在每次新增或刪除的時分都會對size停止+1或許-1操作.
*/
transient int size;
/**
* 負載值，需求調整大小的臨界值，為：(capacity * load factor).在每次調整大小後會運用新的容量計算一下
* @serial
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;
/**
* 負載因子，假如結構函數中沒有指定，則采用默許的負載因子，
*
* @serial
*/
final float loadFactor;
/**
* HashMap構造修正次數，構造修正時改動HashMap中的映射數量或修正其外部構造（例如，* rehash辦法，重建外部數據構造），此字段用於在 * HashMap的集合視圖上生成的迭代器都處置成疾速失敗的
*/
transient int modCount;
初始容量與負載因子功能調整
通常，默許負載因子（0.75）在時間和空間本錢上尋求一種折中。負載因子過高雖然增加了空間開支，但同時也添加了查詢本錢（在大少數HashMap類的操作中，包括get和put操作，都反映了這一點）。在設置初始容量時應該思索到映射中所需的條目數及其負載因子，以便最大限制的增加rehash操作次數。假如初始容量大於最大條目數除以加載因子，則不會發作rehash操作。
假如很多映射關系要存儲在HashMap實例中，則絕對於按需執行自動的rehash操作以增大表的容量來說，運用足夠大的初始容量創立它將使得映射關系能更無效的存儲。
如下為重建HashMap數據構造的代碼：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { // 假如容量已達最大限制，則設置下負載值後直接前往
threshold = Integer.MAX_VALUE;
return;
}
// 創立新的table存儲數據
Entry[] newTable = new Entry[newCapacity];
// 將舊table中的數據轉存到新table中去，這一步會破費比擬多的時間
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
// 最後設置下下次調整大小的負載值
threshold = (int) Math.min(newCapacity * loadFactor,
MAXIMUM_CAPACITY + 1);
}
HashMap結構辦法
第四個結構辦法是以曾經存在的Map創立一個新的HashMap，稍後再說，前三個結構辦法，其實最終調用的都是第三個帶兩個參數的辦法，假如沒有傳遞參數則運用默許的數值,代碼如下：
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
由上可以看出，在結構函數中，假如初始容量給的大於最大容量，則直接以最大容量替代。
put辦法
接上去就看看HashMap中比擬重要的局部
/**
* 在此映射中關聯指定值與指定建。假如該映射以前包括了一個該鍵的映射關系，則舊值被交換
*
* @param 指定將要關聯的鍵
* @param 指定將要關聯的值
* @return 與key關聯的舊值，假如key沒有任何映射關系，則前往null（前往null還能夠表示該映射之前將null與key關聯）
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
/**
* Entry結構辦法，創立一個新的Entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
由於新增條目的時分，需求計算hash值，長度不夠時需求調整長度，當計算的存儲地位已有元素的時分需求停止鏈表式的存儲，所以運用HashMap新增操作的效率並不是太高。
get辦法
首先看下get辦法的源碼：
/**
* 前往指定鍵所映射的值；假如關於該鍵來說，此映射不包括任何映射關系，則前往null
* 前往null值並不一定標明該映射不包括該鍵的映射，也能夠改映射將該鍵顯示的映射為null，可運用containsKey操作來區分這兩種狀況
* @see #put(Object, Object)
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
get辦法完成較復雜，以下是幾個步驟：
經過檢查get的源碼可以發現，get辦法經過key的哈希值與桶的長度計算存儲地位，根本上一下就能定位到要找的元素，即便再遍歷幾個反復哈希值的key，也是很疾速的，由於哈希值絕對獨一，所以HashMap關於查找功能是十分快的。
自定義對象作為HashMap的鍵
class User {
// 身份證號碼
protected int idNumber;
public User(int id){
idNumber = id;
}
}
public class TestUser{
public static void main(String[] args) {
Map<User, String> map = new HashMap<User, String>();
for (int i=0; i<5; i++) {
map.put(new User(i), "姓名: " + i);
}
System.out.println("User3 的姓名：" + map.get(new User(3)));
}
}
輸入： User3 的姓名：null
如上代碼，經過自定義的User類實例作為HashMap的對象時，在打印的時分是無法找到User3的姓名的，由於User類自動承繼基類Object，所以這裡會自動運用Object的hashCode辦法生成哈希值，而它默許是運用對象的地址計算哈希值的。因而new User(3)生成的第一個實例的哈希值與生成的第二個實例的哈希值是不一樣的。但是假如只需求復雜的掩蓋hashCode辦法，也是無法正常運作的，除非同時掩蓋equals辦法，它也是Object的一局部。HashMap運用equals()判別以後的鍵能否與表中存在的鍵相反，可以參考下面的get或put辦法。
正確equals()辦法必需滿足下列5個條件：---參考《Java編程思想》—489頁
再次強調：默許的Object.equals()只是比擬對象的地址，所以一個new User(3)並不等於另一個new User(3)。因而，假如要運用自己的類作為HashMap的鍵，必需同時重載hashCode()和equals().
如下代碼可以正常運作：
class User {
// 身份證號碼
protected int idNumber;
public User(int id){
idNumber = id;
}
@Override
public int hashCode() {
return idNumber;
}
@Override
public boolean equals(Object obj) {
return obj instanceof User && (idNumber==((User)obj).idNumber);
}
}
public class TestUser{
public static void main(String[] args) {
Map<User, String> map = new HashMap<User, String>();
for (int i=0; i<5; i++) {
map.put(new User(i), "姓名: " + i);
}
System.out.println("User3 的姓名：" + map.get(new User(3)));
}
}
輸入：
User3 的姓名：姓名: 3
下面只是復雜的在hashCode中前往了idNumber作為獨一的判別，用戶也可以依據自己的業務虛現自己的辦法。在equals辦法中，instanceof會悄然的反省對象能否為null，假如instanceof右邊的參數為null，則會前往false，假如equals()的參數不為null且類型正確，則基於每個對象中的實踐的idNumber停止比擬。從輸入可以看出，如今的方式是正確的。
參考：
《Java編程思想》
JDK API協助文檔
JDK源碼
