類前注釋：
/**
* HashMap is an implementation of {@link Map}. All optional operations are supported.
*
* <p>All elements are permitted as keys or values, including null.
*
* <p>Note that the iteration order for HashMap is non-deterministic. If you want
* deterministic iteration, use {@link LinkedHashMap}.
*
* <p>Note: the implementation of {@code HashMap} is not synchronized.
* If one thread of several threads accessing an instance modifies the map
* structurally, access to the map needs to be synchronized. A structural
* modification is an operation that adds or removes an entry. Changes in
* the value of an entry are not structural changes.
*
* <p>The {@code Iterator} created by calling the {@code iterator} method
* may throw a {@code ConcurrentModificationException} if the map is structurally
* changed while an iterator is used to iterate over the elements. Only the
* {@code remove} method that is provided by the iterator allows for removal of
* elements during iteration. It is not possible to guarantee that this
* mechanism works in all cases of unsynchronized concurrent modification. It
* should only be used for debugging purposes.
*
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*/
HashMap是Map的一種常用實現(xiàn)讹弯。HashMap中的元素排列無序橙凳，如果需要有序排列丘损，請用LinkedHashMap啤它。
/**
* Min capacity (other than zero) for a HashMap. Must be a power of two
* greater than 1 (and less than 1 << 30).
*/
private static final int MINIMUM_CAPACITY = 4;
JDK中HashMap的初始容量是16奕筐，而此處為4。
/**
* An empty table shared by all zero-capacity maps (typically from default
* constructor). It is never written to, and replaced on first put. Its size
* is set to half the minimum, so that the first resize will create a
* minimum-sized table.
*/
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];
空HashMap持有的空表变骡，大小為2（擴容后變成4）离赫。
/**
* The default load factor. Note that this implementation ignores the
* load factor, but cannot do away with it entirely because it's
* mentioned in the API.
*
* <p>Note that this constant has no impact on the behavior of the program,
* but it is emitted as part of the serialized form. The load factor of
* .75 is hardwired into the program, which uses cheap shifts in place of
* expensive division.
*/
static final float DEFAULT_LOAD_FACTOR = .75F;
加載因子固定為0.75。當(dāng)實際大小超過當(dāng)前容量*加載因子時進(jìn)行擴容塌碌。實際上是由閾值threshold控制渊胸。
/**
* The hash table. If this hash map contains a mapping for null, it is
* not represented this hash table.
*/
transient HashMapEntry<K, V>[] table;
保存Entry的table數(shù)組。注意這里也用了transient 修飾符台妆，原理同ArrayList（見前一篇）翎猛。
/**
* The entry representing the null key, or null if there's no such mapping.
*/
transient HashMapEntry<K, V> entryForNullKey;
保存key為空的Entry胖翰。
/**
* The table is rehashed when its size exceeds this threshold.
* The value of this field is generally .75 * capacity, except when
* the capacity is zero, as described in the EMPTY_TABLE declaration
* above.
*/
private transient int threshold;
閾值。當(dāng)實際大小超過閾值時重新進(jìn)行哈希切厘。
/**
* Constructs a new empty {@code HashMap} instance.
*/
@SuppressWarnings("unchecked")
public HashMap() {
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}
/**
* Constructs a new {@code HashMap} instance with the specified capacity.
*
* @param capacity
* the initial capacity of this hash map.
* @throws IllegalArgumentException
* when the capacity is less than zero.
*/
public HashMap(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("Capacity: " + capacity);
}
if (capacity == 0) {
@SuppressWarnings("unchecked")
HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
table = tab;
threshold = -1; // Forces first put() to replace EMPTY_TABLE
return;
}
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
} else if (capacity > MAXIMUM_CAPACITY) {
capacity = MAXIMUM_CAPACITY;
} else {
capacity = Collections.roundUpToPowerOfTwo(capacity);
}
makeTable(capacity);
}
HashMap的幾個構(gòu)造函數(shù)萨咳。不指定容量的情況下table指向EMPTY_TABLE；指定容量的情況下容量將被調(diào)整為大于4的2的某次方值迂卢。
static class HashMapEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
@Override public final boolean equals(Object o) {
if (!(o instanceof Entry)) {
return false;
}
Entry<?, ?> e = (Entry<?, ?>) o;
return Objects.equal(e.getKey(), key)
&& Objects.equal(e.getValue(), value);
}
@Override public final int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
@Override public final String toString() {
return key + "=" + value;
}
}
Entry類某弦，HashMap內(nèi)部的數(shù)據(jù)結(jié)構(gòu)。table是HashMapEntry數(shù)組而克，同時HashMapEntry有一個HashMapEntry類型的next指針靶壮。當(dāng)數(shù)組哈希位置已經(jīng)存在元素時將新元素加入到該位置的鏈表末位，這也就是哈希沖突處理方法中的拉鏈法员萍。
/**
* Maps the specified key to the specified value.
*
* @param key
* the key.
* @param value
* the value.
* @return the value of any previous mapping with the specified key or
* {@code null} if there was no such mapping.
*/
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
/**
* Creates a new entry for the given key, value, hash, and index and
* inserts it into the hash table. This method is called by put
* (and indirectly, putAll), and overridden by LinkedHashMap. The hash
* must incorporate the secondary hash function.
*/
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}
增腾降。對key二次哈希，與運算（相當(dāng)于hash%length但是效率更高）得到index碎绎，然后遍歷index對應(yīng)的鏈表查找key相同的Entry螃壤，若有則替換之，若無則先判斷是否需要擴容筋帖，再添加新Entry奸晴，將新Entry作為鏈表頭并指向原來的鏈表頭。如上文所說日麸，這是拉鏈法的應(yīng)用寄啼。
/**
* Doubles the capacity of the hash table. Existing entries are placed in
* the correct bucket on the enlarged table. If the current capacity is,
* MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which
* will be new unless we were already at MAXIMUM_CAPACITY.
*/
private HashMapEntry<K, V>[] doubleCapacity() {
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
int newCapacity = oldCapacity * 2;
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
if (size == 0) {
return newTable;
}
for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry<K, V> e = oldTable[j];
if (e == null) {
continue;
}
int highBit = e.hash & oldCapacity;
HashMapEntry<K, V> broken = null;
newTable[j | highBit] = e;
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
return newTable;
}
擴容。擴容大小是固定的2倍代箭。難點是擴容之后重新哈希的這段頗為風(fēng)騷的代碼墩划。倒是在行間注釋里特地寫一句“This is the most subtle and delicate code in the class”是幾個意思www。這里是以(hash & oldCapacity) | j求出index嗡综，該結(jié)果和hash & newCapacity - 1的運算結(jié)果相等乙帮，可以作出證明：
(hash & oldCapacity) | j
= (hash & oldCapacity) | (hash & (oldCapacity - 1))
= hash & (oldCapacity | (oldCapacity - 1))
因為容量capacity為2的某次冪，如4（0100）极景，8（1000）察净，形為除了第n位為1其他位為0；capacity - 1形為從第1位到第n - 1位為1其他位為0盼樟；則capacity | (capacity - 1)形為從第1位到第n位為1其他位為0塞绿，即capacity * 2 - 1也就是newCapacity - 1。
運算如此巧妙以至于讓人初見如墜五里云霧恤批。然而為什么要如此這番而不是直接使用hash & newCapacity - 1呢？就運算步驟來說反而是多了一步或運算裹赴。關(guān)于這個問題喜庞，我依舊不得其解诀浪。
將鏈表頭移動到新表后遍歷鏈表，判斷每個Entry是否需要移動延都，判斷的依據(jù)是高位是否相等雷猪，相等說明該Entry與上一Entry位于同一鏈表。
broken的作用是移動Entry之后將原鏈表上被移走的部分截掉晰房。
/**
* Removes the mapping with the specified key from this map.
*
* @param key
* the key of the mapping to remove.
* @return the value of the removed mapping or {@code null} if no mapping
* for the specified key was found.
*/
@Override public V remove(Object key) {
if (key == null) {
return removeNullKey();
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index], prev = null;
e != null; prev = e, e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
modCount++;
size--;
postRemove(e);
return e.value;
}
}
return null;
}
刪求摇。原理和put類似。若刪除的Entry是鏈表頭則將下一Entry作為鏈表頭殊者，否則將上一Entry的next指向刪除Entry的next与境。
/**
* Returns the value of the mapping with the specified key.
*
* @param key
* the key.
* @return the value of the mapping with the specified key, or {@code null}
* if no mapping for the specified key is found.
*/
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
查。與上面類似的原理猖吴。
谷歌對Android環(huán)境下的HashMap進(jìn)行了一定的優(yōu)化摔刁，同時也推出了在一些場景下性能更好的替代品SparseArray和ArrayMap。另外若在多線程環(huán)境中海蔽，應(yīng)使用ConcurrentHashMap而不是HashMap共屈。
