摘要
Java中Map是开发中经常使用的一个类，它主要用于存放键值对映射；在查询时，根据对应的key获取value；使用非常简单，但是其中的知识点一点不少，并且是面试中必问的！博主希望通过这篇博客能帮助读者深入了解HashMap的底层原理；
介绍
基于哈希表实现Map接口。 该实现提供了所有可选的映射操作，并允许null值和null键。 (HashMap类大致相当于Hashtable，只是它是不同步的，并且允许为空。) 这个类不保证map的顺序; 特别是，它不能保证顺序会随着时间的推移保持不变。
这个实现为基本操作(get和put)提供了恒定时间的性能表现，前提是散列函数将元素适当地分散到存储桶中。遍历集合视图所需的时间与HashMap实例的“容量”(桶的数量)加上它的大小(键值映射的数量)成正比。 因此，如果迭代性能很重要，那么初始容量不要设置得太高(或者负载因子太低)是非常重要的。
HashMap实例有两个参数影响其性能: 初始容量和负载因子。 capacity为哈希表中桶的数量，初始容量为哈希表创建时的容量。 负载因子是在哈希表容量自动增加之前允许达到的满度的度量。 当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表为rehash(即重新构建内部数据结构)，因此哈希表的桶数大约是原来的两倍。
一般来说，默认的负载因子(0.75)在时间和空间成本之间提供了一个很好的权衡。 较高的值会减少空间开销，但会增加查找成本(反映在HashMap类的大多数操作中，包括get和put)。 在设置map的初始容量时，应该考虑map中预期的条目数量及其负载因子，以尽量减少rehash操作的数量。 如果初始容量大于最大条目数除以负载因子，则不会发生重hash操作。
如果要在HashMap实例中存储许多映射，那么使用足够大的容量创建它将使映射能够更有效地存储，而不是让它根据需要执行自动重散列以增长表。 注意，这个实现不是同步的。 如果多个线程并发访问一个哈希映射，并且至少有一个线程在结构上修改了这个映射，那么它必须在外部进行同步。 (结构修改是添加或删除一个或多个映射的任何操作; 仅仅改变与实例已经包含的键相关联的值并不是结构上的修改。) 这通常通过对自然封装映射的某些对象进行同步来完成。 如果不存在这样的对象，则应该使用 Collections.synchronizedMap方法 “包装”映射。 这最好在创建时完成，以防止意外的对map的不同步访问: Map m = Collections.synchronizedMap(new HashMap(...));
这个类的所有“集合视图方法”返回的迭代器都是快速失败的:如果在迭代器创建后的任何时间映射在结构上被修改，除了通过迭代器自己的remove方法之外的任何方式，迭代器都会抛出ConcurrentModificationException。 因此，在面对并发修改时，迭代器会快速而干净地失败，而不是冒着在未来某个不确定的时间发生任意的、不确定的行为的风险。
请注意，迭代器的快速失败行为不能得到保证，因为一般来说，在存在非同步的并发修改时，不可能做出任何硬保证。 快速失败迭代器尽可能抛出ConcurrentModificationException。 因此，编写依赖此异常来保证其正确性的程序是错误的:迭代器的快速失败行为应该只用于检测错误。
这个类是Java集合框架的成员。
源码分析
(1)、类定义
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{
...
}
可以看出，HashMap继承了AbstractMap，实现Map、Cloneable、Serializable接口。
(2)、Cloneable实现
我们从类定义上面了解到HashMap实现Cloneable克隆，源码如下：
/**
* 返回这个HashMap实例的浅副本:键和值本身没有被克隆。
*/
public Object clone() {
HashMap<K,V> result = null;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
if (result.table != EMPTY_TABLE) {
result.inflateTable(Math.min(
(int) Math.min(
size * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY),
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
return result;
}
(3)、HashMap变量
/**
* 默认初始容量—必须是2的幂。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
*最大容量，如果一个较大的值由带参数的构造函数中的任何一个隐式指定，则使用该值。 必须是2的幂，<= 1<<30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 当表没有膨胀时共享的空表实例。
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* 根据需要调整表的大小。 长度必须永远是2的幂。
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* 此映射中包含的键值映射的数量。
*/
transient int size;
/**
* size扩容的阈值，要调整表容量大小的下一个size值(容量*负载因子)。
* @serial
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;
/**
* 哈希表的负载因子
* @serial
*/
final float loadFactor;
/**
* 结构化修改指的是改变HashMap中映射的数量或修改其内部结构(如rehash)。 该字段用于使HashMap的集合视图上的迭代器快速失败。
* (见 ConcurrentModificationException)。
*/
transient int modCount;
/**
* map容量的默认阈值，超过这个阈值将对String键使用替代散列。 由于字符串键的弱哈希码计算，可选哈希减少了碰撞的发生率。
*
* 这个值可以通过定义系统属性来重写
* {@code jdk.map.althashing.threshold}。 属性值{@code 1}强制使用备选哈希，而{@code -1}值确保备选哈希从未使用。
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
(4)、静态内部类Holder
/**
* holds values which can't be initialized until after VM is booted.
*/
private static class Holder {
/**
* 要切换到使用可选散列的表容量。
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// 如果-1禁用替代哈希
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
(5)、HashMap构造
/**
* 使用指定的初始容量和加载因子构造一个空的HashMap。
*
* @param initialCapacity the initial capacity 初始容量
* @param loadFactor the load factor 负载因子
* @throws IllegalArgumentException 初始容量为负值或负载因子为非正值
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
/**
* 构造一个空的HashMap，使用指定的初始容量和默认的负载因子(0.75)。
*
* @param initialCapacity 初始容量。
* @throws IllegalArgumentException 如果初始容量为负。
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造一个空的HashMap，使用默认的初始容量(16)和默认的负载因子(0.75)。
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 构造一个新的HashMap，具有与指定的Map相同的映射。 HashMap是用默认负载因子(0.75)创建的，
* 并且初始容量足够容纳指定的<tt>Map</tt>中的映射。
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
//子类的初始化钩子。 在HashMap初始化之后，插入任何条目之前，在所有构造函数和伪构造函数(clone, readObject)中调用此方法。
//(在没有这个方法的情况下，readObject将需要子类的显式知识。)
void init() {
}
/**
* 膨胀 the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
/**
* Initialize the hashing mask value. We defer initialization until we
* really need it.
*/
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
(6)、内部类Entry
该类是用来代表HashMap中的一个键值对类型.
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//键
V value;//值
Entry<K,V> next;//相同hash槽位上的链表的下一个Entry
int hash;//键的hash值
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
(7)、put(K key, V value) 方法
该方法是HashMap的核心方法之一，用来向HashMap中存入一个键值对；
public V put(K key, V value) {
//空表膨胀
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//key为null的键值对存入
if (key == null)
return putForNullKey(value);
//key不为null,对key进行hash
int hash = hash(key);
//通过Key的hash和hash表的长度定位key的槽位
int i = indexFor(hash, table.length);
//用hash表上该槽位的链表遍历，如果存在key相同,则替换value
for (Entry<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++;
//新增entry
addEntry(hash, key, value, i);
return null;
}
看了上面的这段源码，详细大家已经比较清楚put方法的主流程：
- 首先判断是否hash表是否为空表（第一次膨胀）;如果是空表，则使用容量阈值进行膨胀。
- 判断key是否为空，如果为空，则调用putForNullKey(value)方法进行保存，并返回旧的value值/null
- 对key进行hash，并通过key的hash值和hash表长度定位槽位
- 用hash表上该槽位的链表遍历，如果存在key相同,则替换value并返回旧的值
- 否则，在该槽位上新增加一项，返回null
我们接着上面进行源码分支分析：
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
通过上面这段源码，可以了解到，当put传入的key键为空时，HashMap首先遍历hash表中，槽位为0的Entry链表，如果存在key为null的entry，则替换值并返回旧值;如果不存在key为null的值，则将key键为null的新键值对添加到槽位为0的hash槽链表上。
/**
* 将具有指定键、值和哈希码的新条目添加到指定的桶中。 这个方法负责在适当的时候调整表的大小。
*
* 子类重写它以改变put方法的行为。
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//当hash表中的键值对大于扩容的阈值、并且当前hash槽位非空，则进行扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容为原来hash表长度的2倍
resize(2 * table.length);
//hash重新定位槽位
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//插入到指定槽位
createEntry(hash, key, value, bucketIndex);
}
/**
* 与addEntry类似，不同的是这个版本在创建条目作为Map构造或“伪构造”(克隆、反序列化)的一部分时使用。 这个版本不需要担心调整表的大小。
*
* 子类重写它来改变HashMap(Map)、clone和readObject的行为。
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//在链表头部插入新的键值对
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
通过以上这段插入键值对的逻辑，我们可以了解到比较重要的三点（当然此处是HashMap1.7版本的逻辑）：
- HashMap空键entry存放在hash表的下标为0的槽位的链表里
- HashMap以2倍的速度进行扩容
- HashMap插入新的entry时，使用的是链表头部插入方法
扩容逻辑源码：
/**
* 将此映射的内容重新散列到具有更大容量的新数组中。 当此映射中的键数达到其阈值时，将自动调用此方法。
*
* 如果当前容量为MAXIMUM_CAPACITY，此方法不会调整映射的大小，而是将阈值设置为Integer.MAX_VALUE。 这具有防止未来调用的效果。
*
* @param newCapacity 新容量，必须是2的幂; 必须大于当前容量，除非当前容量为MAXIMUM_CAPACITY(此时值无关)。
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 将当前表中的所有项转移到newTable。
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
/**
* 返回哈希码h的索引。相当于h%length
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
从以上代码我们可以看出HashMap在resize的时候，hash表槽位上链表会发生倒置；在多线程扩容时，就有可能某一瞬间会产生环状，访问进入死循环；
/**
* 检索对象哈希代码，并对结果哈希应用一个补充哈希函数，以防止低质量的哈希函数。 这是至关重要的，因为HashMap使用两次方长度的哈希表，否则会 *遇到hashcode在较低位没有差异的冲突。 注意:空键总是映射到散列0，因此索引0。
*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 这个函数确保hashcode在每个位位置上的差异仅为常数倍，冲突的次数是有限制的(默认负载因子约为8)。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
从上面的源码可以了解到，当key为string的时候，系统会使用sun.misc.Hashing.stringHash32来进行hash； 特别注意的是，当k为非String且不等0的时候，该方法会调用k对象的hashCode方法，然后进行后续优化计算；因此，如果使用hashMap存的键值对key自定义对象时候，我们一般需要重写hashCode方法;
(8)、get(Object key) 方法
/**
* 返回指定键映射到的值，如果这个映射不包含该键的映射，则返回{@code null}。
*
* 更正式地说，如果这个map包含一个从键{@code k}到值{@code v}的映射，
* 这样{@code (key==null ? K ==null: key.equals(K))}，然后这个方法返回{@code v}; 否则返回{@code null}。 (最多只能有一个这样的映射。)
*
* {@code null}的返回值不一定表示映射不包含该键的映射; 也有可能映射显式地将键映射为{@code null}。
* {@link #containsKey containsKey}操作可以用来区分这两种情况。
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
/**
* 查找空键的get()的卸载版本。 空键映射到索引0。 为了在两个最常用的操作(get和put)中提高性能，这个空的情况被拆分为单独的方法，
* 但在其他操作中与条件合并。
*/
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
//返回HashMap中与指定键关联的条目。 如果HashMap不包含键的映射，则返回null。
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
通过以上源码，我们可以知道；HashMap的get逻辑：如果键为null，则直接去下标为0的槽位上的entry链表查找；否则，通过indexFor方法hash%table.length来定位槽位；然后在该槽位的链表上循环搜索key。
(9)、remove(Object key) 方法
/**
* 如果存在，则从该映射中移除指定键的映射。
*
*@param key key的映射将被从映射中移除
*@返回以前与键关联的值，如果键没有映射的话，返回null。
* (一个null返回也可以表明先前关联null与键的映射。)
*/
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
* 删除并返回HashMap中与指定键关联的条目。 如果HashMap不包含此键的映射，则返回null。
*/
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
(10)、clear() 方法
/**
* 从该映射中删除所有映射。 这个调用返回后，映射将为空。
*/
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}
该方法通过使用Arrays.fill对Hash表进行控制填充来达到清空HashMap的效果；
JDK1.7 HashMap底层数据结构
通过上面的源码分析，相信大家已经对JDK1.7中HashMap的底层数据结构非常清晰； 
