类前注释：
/**
* 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的一种常用实现。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。当实际大小超过当前容量*加载因子时进行扩容。实际上是由阈值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数组。注意这里也用了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;
阈值。当实际大小超过阈值时重新进行哈希。
/**
* 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的几个构造函数。不指定容量的情况下table指向EMPTY_TABLE；指定容量的情况下容量将被调整为大于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内部的数据结构。table是HashMapEntry数组，同时HashMapEntry有一个HashMapEntry类型的next指针。当数组哈希位置已经存在元素时将新元素加入到该位置的链表末位，这也就是哈希冲突处理方法中的拉链法。
/**
* 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二次哈希，与运算（相当于hash%length但是效率更高）得到index，然后遍历index对应的链表查找key相同的Entry，若有则替换之，若无则先判断是否需要扩容，再添加新Entry，将新Entry作为链表头并指向原来的链表头。如上文所说，这是拉链法的应用。
/**
* 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倍。难点是扩容之后重新哈希的这段颇为风骚的代码。倒是在行间注释里特地写一句“This is the most subtle and delicate code in the class”是几个意思www。这里是以(hash & oldCapacity) | j求出index，该结果和hash & newCapacity - 1的运算结果相等，可以作出证明：
(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呢？就运算步骤来说反而是多了一步或运算。关于这个问题，我依旧不得其解。
将链表头移动到新表后遍历链表，判断每个Entry是否需要移动，判断的依据是高位是否相等，相等说明该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环境下的HashMap进行了一定的优化，同时也推出了在一些场景下性能更好的替代品SparseArray和ArrayMap。另外若在多线程环境中，应使用ConcurrentHashMap而不是HashMap。
