概述
HashMap是基于哈希表的 Map 接口的实现。数据以键值对的形式存储，和HashTab的差别在于HashMap可以以null作为键值，但是HashMap是线程不安全的。如果要实现线程同步可以使用：
- Map map = Collections.synchronizedMap(new HashMap());
- ConcurrentHashMap
HashMap的数据结构
HashMap是通过数组和链表（散列链表）来实现数据存储的。之所以HashMap查询速度很快，是因为它是通过散列码来决定存储位置。通过获取key的hashcode和数组的长度的&值来确定存储的位置，如果有相同的key的hashcode，那么就是所谓的hash冲突，就添加到对应的链表结构的数据中。
紫色代表数组代表哈希表，也称为哈希数组，绿色代表链表。数组存储具有相同key值hashcode的链表的表头。数组的元素和链表的节点都是Entry对象。
HashMap源码分析（Android中的源码）
- HashMapEntry对象：
/** HashMapEntry是单向链表。
* 它是 “HashMap链式存储法”对应的链表。
* 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数
**/
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就是一个单向链表，每个节点包含了key、value、hash值、和下一个节点。
- 重要属性：
private static final int MINIMUM_CAPACITY = 4;//最小的容量，也是默认的初始容量
static final float DEFAULT_LOAD_FACTOR = .75F;//默认的加载因子
transient HashMapEntry<K, V>[] table;//哈希表
transient int modCount;//被修改的次数
transient int size;//存放元素的个数
private transient int threshold;//阈值，当前的元素个数查过阈值进行扩容，阈值 = 加载因子*总容量
加载因子在Android 的源码中被阉割了，固定为0.75，这是和在jdk中不同的地方
public HashMap(int capacity, float loadFactor) {
this(capacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor: " + loadFactor);
}
/* 加载因子固定为3/4
* Note that this implementation ignores loadFactor; it always uses
* a load factor of 3/4. This simplifies the code and generally
* improves performance.
*/
}
加载因子表示HashMap填充的程度，加载因子越大，HashMap填充的越满才进行扩容，空间利用率越高，造成的问题是存放的数据越多，hash冲突的可能性越大，查找的效率越低。反之亦反。这是一个空间和效率的之间的取舍。一般用默认的就行了。
- put方法：
public V put(K key, V value) {
if (key == null) {
//存放null的key值，则将该键值对添加到table[0]中。
return putValueForNullKey(value);
}
//对key的hashcode值进行再次计算得到hash。
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
//通过hash值和数组长度来确定数组的下标，这里的值不是随便取的
int index = hash & (tab.length - 1);
//遍历对应的数组下标的链表，如果存在相同的key值就替换原来的value
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++;
//否则加载列表的头部（也就是数组对应的位置）
//在添加新的数据之前检查是否需要扩容。如果数据的大小超过阈值，数组的容量就扩大到原来的2倍
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
//把数据添加到表头
addNewEntry(key, value, hash, index);
return null;
}
hash & (tab.length - 1)的算法来取到数组的下标值，这个方式即可实现均匀的散列，还可以使数组不越界。那为什么扩容需要2的次幂呢，因为hash & (tab.length - 1)中，如果括号中的结果数奇数的话最后一位为1，hash&xx最后的接口有可能是奇数也有可能是偶数；如果括号中的值是偶数的话，那最后的结果也只能是偶数，那么数组存放的值只能存放在偶数下标中，浪费了一般的资源，如果是2的倍数减一，刚好能够控制能过取到所有的下标值。因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
扩容：
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;
}
新建了一个数组，是原来数组容量的两倍，然后重新计算hashcode在数组中的位置，并且存放在数组中。
那为什么扩容呢？随着HashMap存放的数据越来越多，hash冲入产生的概率就越来越大，造成查找效率越来越低，所以进行扩容，但是扩容需要把所有的元素遍历重新赋值，还要新建一个数组，这是HashMap很消耗资源的地方。
在达到阈值的时候开始扩容，如：现在的容量大小为8,8*0.75 = 6，当HashMap中的元素个数达到6的时候就开始扩容。
