構(gòu)造函數(shù)
HashMap 提供了三個(gè)構(gòu)造函數(shù)和一個(gè)拷貝構(gòu)造函數(shù)：
public HashMap(int initialCapacity, float loadFactor);
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m);
構(gòu)造函數(shù)
/**
* 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;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
threshold = initialCapacity;
init();
}
這個(gè)構(gòu)造方法需要提供兩個(gè)參數(shù)，initialCapacity 和 loadFactor 嚷炉。
- 第一個(gè)參數(shù)表示 hashMap 的初始化大小哟旗，默認(rèn)值為
static final int DEFAULT_INITIAL_CAPACITY = 4;碟联，且 初始化大小的值必須是 2 的整數(shù)次冪脑豹。 - 第二個(gè)參數(shù)表示 todo
在構(gòu)造方法中抗愁，首先對(duì)初始化大小 initialCapacity 進(jìn)行校正馁蒂，校正范圍是 4(默認(rèn)初始化大小) ~ 2^30(最大容量)。
HashMapEntry
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
HashMapEntry<K,V> next;
int hash;
}
HashMapEntry 中保存著一個(gè) Key 和 Value 蜘腌，并持有下一個(gè) HashMapEntry 远搪，很明顯這是一個(gè) <K-V> 鍵值對(duì)鏈表。
數(shù)據(jù)結(jié)構(gòu)
put 方法
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<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;
}
- 從上面代碼可以看出逢捺，HashMap 的 Key 是可以為 null 的，在
key == null的情況下癞季，調(diào)用putForNullKey()方法特殊處理
- 正常的情況下劫瞳，現(xiàn)根據(jù) key 的值計(jì)算出 hash 值，并計(jì)算出該 hash 值在隊(duì)列中的 index绷柒。在 table 數(shù)組中取出 HashMapEntry 的鏈表志于，并進(jìn)行遍歷，如果 hash 值相同且 Key 也相同废睦，說(shuō)明新插入的 Key 在 鏈表中存在伺绽，需要覆蓋舊值，并返回舊值嗜湃。如果沒(méi)有找到奈应，說(shuō)明這個(gè) Key 并不存在，需要調(diào)用
addEntry添加在 HashMapEntry 的鏈表中购披。
**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
從 addEntry 方法的實(shí)現(xiàn)可以看出杖挣，當(dāng)此時(shí) hashmap 的 size 大于等于閾值時(shí)，需要將 table 的長(zhǎng)度擴(kuò)大一倍刚陡，并調(diào)用 createEntry() 方法根據(jù)新 Key 的 hash 值 存儲(chǔ)在 table 中惩妇。
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
將 table 中 index = bucketIndex 的 HashMapEntry 作為新節(jié)點(diǎn)的下一個(gè) Entry 株汉，并將 table[bucketIndex] 指向新節(jié)點(diǎn)。
get 方法
get 方法的思想就是利用 key 的 hash 值獲得在 table 中所處的 index 歌殃，并對(duì)其進(jìn)行遍歷乔妈，比較 Key 將對(duì)應(yīng)的 Value 取出。
