HashMap是基于<key,value>的键值对，key可以为null，但是key不会重复，HashMap是无序且线程不安全的集合。HashMap底层的实现是数组和引用的结合，一个HashMap对应一个HashMapEntry数组，数组的每一项又分别是链表，因此，HashMap被称为"链表散列"。本文基于android-23源码分析。
源码解析
先看看HashMap类的实现关系：
public class HashMap<K, V> extends AbstractMap<K, V> implements Cloneable, Serializable {}
在这里我们可以看到HashMap<K,V>继承了AbstractMap，而AbstractMap是实现了于Map接口。此外我们还可以看到实现了Cloneable，Serializble接口：
private static final int MINIMUM_CAPACITY = 4;
//数组最大的容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
//空的数组
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];
///加载因子
static final float DEFAULT_LOAD_FACTOR = .75F;
transient HashMapEntry<K, V>[] table;
transient HashMapEntry<K, V> entryForNullKey;
transient int size;
transient int modCount;
//扩容临界点（size>=threshold就会扩容）
private transient int threshold;
// Views - lazily initialized
private transient Set<K> keySet;
private transient Set<Entry<K, V>> entrySet;
private transient Collection<V> values;
这里需要注意的是:
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[])：是HashMapEntry类型的数组，HashMap用这个来维护内部的数据结构，它的长度由容量决定 。
加载因子 ：是哈希表在其容量自动增加之前可以达到多满的一种尺度。它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。
当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
接下来看看HashMap的构造函数：
@SuppressWarnings("unchecked")
public HashMap() {
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}
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 {
//roundUpToPowerOfTwo返回一个不大于capacity的2的整数次幂
capacity = Collections.roundUpToPowerOfTwo(capacity);
}
makeTable(capacity);
}
public HashMap(int capacity, float loadFactor) {
this(capacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor: " + loadFactor);
}
}
public HashMap(Map<? extends K, ? extends V> map) {
this(capacityForInitSize(map.size()));
constructorPutAll(map);
}
HashMap（）会创建一个table，并且会把threshold置为-1，关于table上面的介绍也说明了，HashMap用它来维护内部的数据结构。
如果构造函数中，capacity值>0,那么他还会调用makeTable方法：
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
@SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
= (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
table = newTable;
threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
return newTable;
}
如果构造函数里面，传递的参数类型是Map，那么就会额外调用constructorPutAll方法：
final void constructorPutAll(Map<? extends K, ? extends V> map) {
if (table == EMPTY_TABLE) {
doubleCapacity(); // Don't do unchecked puts to a shared table.
}
for (Entry<? extends K, ? extends V> e : map.entrySet()) {
constructorPut(e.getKey(), e.getValue());
}
}
当table是空的时候会调用doubleCapacity（）方法，现在看看它的具体实现：
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++) {
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;
}
最后在constructorPutAll方法中，会循环调用constructorPut（）方法：
private void constructorPut(K key, V value) {
if (key == null) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
entryForNullKey = constructorNewEntry(null, value, 0, null);
size++;
} else {
entry.value = value;
}
return;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
HashMapEntry<K, V> first = tab[index];
for (HashMapEntry<K, V> e = first; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
e.value = value;
return;
}
}
// No entry for (non-null) key is present; create one
tab[index] = constructorNewEntry(key, value, hash, first);
size++;
}
此外，HashMap的构造函数中，多次出现HashMapEntry这个类：
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;
}
}
HashMapEntry是HashMap的一个内部类，它也是维护着一个key-value映射关系，除了key和value，还有next引用（该引用指向当前table位置的链表），hash值（用来确定每一个Entry链表在table中位置）
HashMap添加元素
最基本的put(K key,V value)方法实现:
@Override public V put(K key, V value) {
//key运行为null
if (key == null) {
return putValueForNullKey(value);
}
//获取hash值
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
//index是拿hash值和tab的长度-1做&运算
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++;
//size>threshold的时候，需要扩容
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
//
addNewEntry(key, value, hash, index);
return null;
}
上面的代码会先去判断key是否为null，如果为null，就添加一个key为null的元素，由此，可以验证，HashMap是可以key为null的。然后通过index下标去获取table的元素，而index是由hash值和tab的长度做&运算得到的。接下来，循环遍历table中是否有相同的hash值和key相同的元素，有则替换值并返回。接下来如果有size>threshold的时候，就调用doubleCapacity（）方法扩容，并计算index的值，最后调用addNewEntry添加一个新的元素。
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}
接下来看看另外一个添加方法，putAll（）：
@Override public void putAll(Map<? extends K, ? extends V> map) {
ensureCapacity(map.size());
super.putAll(map);
}
private void ensureCapacity(int numMappings) {
int newCapacity = Collections.roundUpToPowerOfTwo(capacityForInitSize(numMappings));
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (newCapacity <= oldCapacity) {
return;
}
if (newCapacity == oldCapacity * 2) {
doubleCapacity();
return;
}
// We're growing by at least 4x, rehash in the obvious way
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
if (size != 0) {
int newMask = newCapacity - 1;
for (int i = 0; i < oldCapacity; i++) {
for (HashMapEntry<K, V> e = oldTable[i]; e != null;) {
HashMapEntry<K, V> oldNext = e.next;
int newIndex = e.hash & newMask;
HashMapEntry<K, V> newNext = newTable[newIndex];
newTable[newIndex] = e;
e.next = newNext;
e = oldNext;
}
}
}
}
HashMap移除
remove():
@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;
}
现在看看removeMapping（）方法的实现：
private boolean removeMapping(Object key, Object value) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null || !Objects.equal(value, e.value)) {
return false;
}
entryForNullKey = null;
modCount++;
size--;
postRemove(e);
return true;
}
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 (!Objects.equal(value, e.value)) {
return false; // Map has wrong value for key
}
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
modCount++;
size--;
postRemove(e);
return true;
}
}
return false; // No entry for key
}
HashMap get
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;
//比较key和hash值
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
HashMap获取元素的方法，也是通过hash&table.length-1获取index下标，然后遍历table[index]中的单链表中的值，找到匹配的就返回值。
HashMap的HashIterator
看看HashInterator的内部实现：
private abstract class HashIterator {
int nextIndex;
HashMapEntry<K, V> nextEntry = entryForNullKey;
HashMapEntry<K, V> lastEntryReturned;
int expectedModCount = modCount;
//当调用keySet().iterator()时，调用
HashIterator() {
if (nextEntry == null) {
HashMapEntry<K, V>[] tab = table;
HashMapEntry<K, V> next = null;
//从哈希表数组从上到下，查找第一个不为null的节点，并把next引用指向该节点
while (next == null && nextIndex < tab.length) {
next = tab[nextIndex++];
}
nextEntry = next;
}
}
public boolean hasNext() {
return nextEntry != null;
}
//nextEntry
HashMapEntry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == null)
throw new NoSuchElementException();
HashMapEntry<K, V> entryToReturn = nextEntry;
HashMapEntry<K, V>[] tab = table;
HashMapEntry<K, V> next = entryToReturn.next;
while (next == null && nextIndex < tab.length) {
next = tab[nextIndex++];
}
nextEntry = next;
return lastEntryReturned = entryToReturn;
}
public void remove() {
if (lastEntryReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
HashMap.this.remove(lastEntryReturned.key);
lastEntryReturned = null;
expectedModCount = modCount;
}
}
HashMap遍历时，按哈希表的每一个索引的链表从上往下遍历，由于HashMap的存储规则，最晚添加的节点都有可能在第一个索引的链表中，这也就是我们开始说的HashMap是无序的。
