Map接口简要类图
HashMap是基于哈希表的Map接口的实现。此实现提供所有可选的映射操作，并且允许使用null键和null值。（除了是非同步的以及允许使用null之外，HashMap和Hashtable大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
为什么HashMap不保证映射的顺序呢？
因为在HashMap中，当桶中存储的元素大于某个值时，就会将链表式存储结构转换成红黑树存储结构。后面会详细介绍这一点。
先学习一下两个名词：
- 初始容量：容量指的是哈希表中桶的数量，初始容量即哈希表在创建时的容量。（如果在使用构造函数创建对象时没有指定容量的话，默认容量为DEFAULT_INITIAL_CAPACITY = 1 << 4，即16）
- 加载因子：加载因子用来衡量哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则对该哈希表进行rehash操作（即重新构建内部数据结构），从而哈希表将具有两倍的桶数。
当加载因子过高虽然可以减少空间开销，但是会增加查询成本。所以默认加载因子为0.75，为了在时间和空间成本上寻找一种折衷。
对HashMap进行简单地概括
- HashMap是对Map最简单的实现
- HashMap中的元素按照hash值分布在不同的桶(bin)中。如果散列特性较好，那么元素分布会比较均匀。
- 单个桶的尺寸过大时，桶的数据结构会由链式转换成一个红黑树
，以保证对其操作的时间复杂度为O（logN） - key类型推荐实现Comparable，以提高效率
- KeySet、Values、EntrySet三个视图集合只支持update/remove操作，不支持add
- 迭代子利用modCount属性来实现乐观锁，来如发生竞态的写操作，则迭代子将直接失效（fast-fail）
- 代码用了很多赋值表达式来精简代码量，但是略影响可读性
下面开始探究HashMap的源码（主要的入口方法实现）
/**
* <pre>
* 以哈希表方式实现的Map接口，允许key和value为null
* （除非线程安全及允许null值外，HashMap基本与Hashtable等价）
*
* 本类不保证元素的顺序，特别地，顺序也可能随时间改变
*
* 在散列特性较好（元素基本均匀分布于bucket）时，本类get和put操作均为O(1)量级
* 遍历整个map的时间正比于：HashMap的容量（capacity）+元素总数（注意不只是元素数）
* 因此最好不要把初始容量设置过高或负载因子（load factor）设置过低
*
* 容量指HashMap中桶的个数，负载因子指HashMap填充到多大比例时允许自动扩容
* 当size>load factor*capacity时, 哈希表将重组（rehashed），其内部结构会发生改变。rehash以后桶的数量将大致翻倍
* 根据经验，负载因子=0.75（默认值）时时空效率达到较好的平衡值
* 设置初始容量时，最好综合考虑元素数的估计值和负载因子，从而减少rehash的次数
*
* 注意如果很多key的hashCode相同必然会降低HashMap的速度
* 为改善这点，当key实现{@link Comparable}时，本类会利用Comparable的顺序来处理hashCode相同
*
* 本类不是线程同步的，如果多线程访问HashMap，且至少有一个线程进行了结构更改，那么这个需要在外层synchronize
* （结构更改指增删元素，不包含更新已有key的value值）
* 使用Collections.synchronizedMap(new HashMap(...)是另一种同步方式
*
* 本类返回的所有迭代子都是fail-fast的
* 即迭代子生成后如果发生任何结构更改（迭代子自身的remove方法除外），迭代子都会抛出{@link ConcurrentModificationException}
* 注意fail-fast特征并不能严格保证，而只是尽可能实现（有可能漏抛）
* 因此不能利用是否抛ConcurrentModificationException来保证程序的正确性，这个异常的作用是辅助发现bug
*
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*
* @author Doug Lea,Josh Bloch,Arthur van Hoff,Neal Gafter
* @see Object#hashCode(),Collection,Map,TreeMap,Hashtable
* @since 1.2
*/
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
/**
* 实现说明
*
* <pre>
* 本类通常是由桶组成的哈希表，然而当桶的尺寸过大时，会将节点重构为TreeNode（每个节点类似java.util.TreeMap）
* 大部分方法实现会判断节点的instanceof，如果是TreeNode，则会采取不同的实现方式
* TreeNode元素支持普通元素的所有操作（对外透明），但提供更快的查询速度
*
* 包含TreeNode的桶首先按hashCode排序，在tie时如果实现了Comparable，则会根据Comparable决定顺序
* （这里通过反射来判断，参见comparableClassFor方法）
* TreeNode机制使得在散列特性不好的情况下，也能保证最差O(log n)的时间性能
*
* 由于TreeNode的尺寸是常规节点大约2倍，因此仅当桶的尺寸大于TREEIFY_THRESHOLD时才会使用TreeNode
* 如果TreeNode的尺寸减小到一定程度（由于remove或resize），还会重新变回普通节点
* 如果散列值的随机性较好，则桶的尺寸与桶数大致服从Poisson分布，因此基本不会用到TreeNode
* (http://en.wikipedia.org/wiki/Poisson_distribution)
*
* 一个TreeNode桶的根节点通常是第一个节点，但有些时候（目前只有Iterator.remove）也会是其他元素
* but can be recovered following parent links (method TreeNode.root()).
*
* 所有具体实现的内部方法都包含hashcode参数（通常在调用public方法是生成），用以在互相调用时不必重新计算hashCode
* 大部分方法包含tab参数，其值大部分情况下就是当前的哈希表自身，但在resizing或converting时可能不同
*
* 当桶列表发生建树（treeify）、分裂、退化（untreeify）时，仍然维护其原先链结构(i.e., Node.next)
* 树结构中按照hash值、Comparator、tie-breakers三层优先方式进行排序
*
* 树结构与链结构的转换在子类LinkedHashMap中会更复杂一些，本类中预留了一些回调方法给LinkedHashMap
*/
// 一些常量/////////////////
// 默认的初始容量，必须是2的幂次
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 建树阈值，桶内元素大于这个数值时会转为TreeNode桶
// 这个数值至少为8以兼容remove操作时退化为普通节点的机制
static final int TREEIFY_THRESHOLD = 8;
// 退树阈值，TreeNode桶内元素小于这个数值时会退化为普通节点
// 数值必须小于TREEIFY_THRESHOLD，至少为6
static final int UNTREEIFY_THRESHOLD = 6;
// 最小的建树容量，这个数值不能小于4 * TREEIFY_THRESHOLD以免resize和treeify机制相互冲突
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 基础的桶节点（bin node），大部分Entry的实现类
*/
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@Override
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
@Override
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
@Override
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
// 一些静态辅助方法/////////////////////
/**
* 计算key的hashCode，并将高低16字节异或（注意不是直接key.hashCode()拿来用）
*
* 由于容量是2的幂次，仅高位不同的hashCode总会落到同一个桶（例如整数部分相同的若干浮点数）
* 这使得原始的hashCode很可能造成不好的散列特性，因此通过xor操作将高位的影响扩散到低位
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 通过反射判断对象x是否实现Comparable<C>接口
*
* @return 如果实现了Comparable，返回x的实际类型，也就是Class<C>，否则返回null.
*/
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c;
Type[] ts, as;
Type t;
ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType)
&& ((p = (ParameterizedType) t).getRawType() == Comparable.class)
&& (as = p.getActualTypeArguments()) != null && as.length == 1
&& as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
/**
* 如果x实际类型是kc，则返回k.compareTo(x)，否则返回0
*
* @param kc 必须实现Comparable
* @param k 类型为kc
* @param x 类型无限制
*/
@SuppressWarnings({ "rawtypes", "unchecked" })
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x));
}
/**
* 返回不小于cap的最小的2的幂次
*/
static final int tableSizeFor(int cap) {
// 低位全部用1填充
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
// 上下限
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 实例属性/////////////////////
// 实际数据的存储结构，尺寸可能变更
transient Node<K, V>[] table;
// entrySet()缓存
transient Set<Map.Entry<K, V>> entrySet;
// 实际元素个数
transient int size;
// HashMap发生结构变更的计数器，结构变更包括增删元素、rehash等，这个属性为实现迭代子的fast-fail特性
transient int modCount;
// 下一个resize的元素个数 (capacity * load factor).
int threshold;
// 负载因子
final float loadFactor;
// public方法/////////////////////
/**
* 含参构造函数
*
* @param initialCapacity
* @param loadFactor
* @throws IllegalArgumentException initialCapacity<0或loadFactor<=0
*/
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;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 根据已有Map构造一个新的HashMap，负载因子取默认值，初始容量根据m.size()确定
*
* @throws NullPointerException if m==null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 将m的所有元素放入本对象，实现Map.putAll和构造函数
*
* @param m the map
* @param evict 初始化调用为false，否则为true
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) {
// 初始化情形，根据m.size初始化threshold
float ft = (s / loadFactor) + 1.0F;
int t = ((ft < MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
} else if (s > threshold) {
// 非初始化，如果m.size已经超过threshold，则立刻resize
// 注意不包含现有元素，putVal()还有尺寸操作
resize();
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
/**
* 返回key对应的value，如果没有返回null
*
* 是否包含通过key.equals()确定
*
* @return 注意返回null不一定代表key不存在，有可能对应的value就是null。如需区分可使用{@link #containsKey containsKey}
* @see #put(Object, Object)
*/
@Override
public V get(Object key) {
Node<K, V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* get的实现
*
* @param hash
* @return the node 不存在返回null
*/
final Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab; // table的快照
Node<K, V> first, e;
int n;
K k;
// first = tab[(n - 1) & hash]是hash对应桶的第一个元素
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) {
return first; // 第一个equal就直接返回了
}
// 否则如果是TreeNode就调用TreeNode的get，不是就直接根据.next遍历桶
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
/**
* 是否包含，这个实际逻辑与get基本是一样的
*/
@Override
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
/**
* 放入一个kv对，如果key已经存在，则value被替换
*
* @return 如果原先包含key，则返回旧的value，否则返回null
*/
@Override
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* put的实现
*
* @param hash
* @param onlyIfAbsent true表示仅当key不存在的情况才执行put（不修改已存在的值）
* @param evict false表示创建过程中
* @return 如果原先包含key，则返回旧的value，否则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化情况
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// key对应的桶不存在情况（key也必然不存在），new一个新node就行了
tab[i] = newNode(hash, key, value, null);
else { // 桶存在情况
Node<K, V> e; // 表示key的（可能有的）现有节点
K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 第一个就是，直接拿过来
else if (p instanceof TreeNode) {
// TreeNode情况
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
} else {
// 非TreeNode，循环遍历桶
for (int binCount = 0;; ++binCount) {
if ((e = p.next) == null) { // 确实没有，new一个新node
p.next = newNode(hash, key, value, null);
// 如果桶的尺寸超过了TREEIFY_THRESHOLD，这个桶要转化为树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; // 找到了，退出循环
p = e;
}
}
if (e != null) { // 所有的已存在情况，更新value并返回旧value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 子类回调
return oldValue;
}
}
// 到这说明新加了节点，modCount+1
// 注意这里只处理增加节点，如果触发resize或者treeify，会在对应方法里继续维护modCount
++modCount;
if (++size > threshold) // size超过阈值，触发resize
resize();
afterNodeInsertion(evict); // 子类回调
return null;
}
/**
* 初始化或扩容
*
* 由于容量是2的幂次，resize后元素下标或者不变，或者增加2的幂次
*
* @return 扩容后的表
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 扩容情况
if (oldCap >= MAXIMUM_CAPACITY) { // 超过上限了就不能再扩容了
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY // 扩容，容量*2
&& oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // 初始化情况
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 更新threshold
if (newThr == 0) {
float ft = newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY ? (int) ft
: Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({ "unchecked" })
Node<K, V>[] newTab = new Node[newCap]; // 新表
table = newTab;
if (oldTab != null) { // 移动旧表的元素
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 旧表置null以便空间快速回收
if (e.next == null) { // 只有一个元素的桶，直接扔到新的桶（新桶一定是空的）
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) { // 处理TreeNode分裂
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
} else { // 普通的桶，逐个处理
Node<K, V> loHead = null, loTail = null; // 原桶的首位指针
Node<K, V> hiHead = null, hiTail = null; // 新桶(+oldCap)的首位指针
Node<K, V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 保持不动
if (loTail == null) {
loHead = e;
} else {
loTail.next = e;
}
loTail = e;
} else { // 挪到新桶
if (hiTail == null) {
hiHead = e;
} else {
hiTail.next = e;
}
hiTail = e;
}
} while ((e = next) != null);
// 把更新后的两个桶放到表里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
/**
* 将指定的桶转化为TreeNode
*/
final void treeifyBin(Node<K, V>[] tab, int hash) {
int n, index;
Node<K, V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize(); // 如果容量小于MIN_TREEIFY_CAPACITY，则直接扩容
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K, V> hd = null, tl = null;
do { // 先把Node链表转成TreeNode链表
TreeNode<K, V> p = replacementTreeNode(e, null); // 当前节点生成的TreeNode
if (tl == null) {
hd = p;
} else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 然后将TreeNode链表转成树
if ((tab[index] = hd) != null) {
hd.treeify(tab);
}
}
}
/**
* 批量put
*/
@Override
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
/**
* 删除对应Key的元素
*
* @param key 注意是Object，类型不要传错
* @return 如果key存在，返回删除前的value，否则返回null
*/
@Override
public V remove(Object key) {
Node<K, V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
/**
* 删除节点实现
*
* @param hash
* @param key
* @param value 如果matchValue=true，表示匹配的value，否则无作用
* @param matchValue true表示仅当key对应value等于matchValue时才删除
* @param movable false表示不移动其他元素（迭代子使用）
* @return 如果删了，返回被删的元素，否则返回null
*/
final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue,
boolean movable) {
Node<K, V>[] tab;
Node<K, V> p;
int n, index;
if ((tab = table) != null && (n = tab.length) > 0
&& (p = tab[index = (n - 1) & hash]) != null) {
Node<K, V> node = null, e; // node为待删元素
K k;
V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p; // 第一个就匹配，直接就他了
else if ((e = p.next) != null) {
if (p instanceof TreeNode) // 如果是TreeNode，从TreeNode取key的元素
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
else { // 否则遍历链表找
do {
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null
&& (!matchValue || (v = node.value) == value || (value != null && value
.equals(v)))) { // 这条件表示确实要删
// TreeNode就按TreeNode删，否则在链表删
if (node instanceof TreeNode) {
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
} else if (node == p)
tab[index] = node.next;
else {
p.next = node.next;
}
++modCount; // 删除元素造成的结构变更
--size;
afterNodeRemoval(node); // 子类回调
return node;
}
}
return null;
}
/**
* 清空（全部删除）
*/
@Override
public void clear() {
Node<K, V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i) { // 所有的桶都置为null
tab[i] = null;
}
}
}
/**
* 包含（一个或多个）value。因为没有倒排，这个方法要遍历全表，慎用
*
* @param value
*/
@Override
public boolean containsValue(Object value) {
Node<K, V>[] tab;
V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) { // 遍历表
for (Node<K, V> e = tab[i]; e != null; e = e.next) {
// 遍历桶。注意TreeNode还是维持打平的链表关系，所以不用特别处理
if ((v = e.value) == value || (value != null && value.equals(v)))
return true;
}
}
}
return false;
}
参考博客：http://distantlight1.iteye.com/blog/2256651
（因为觉得人家总结得非常好，所以就搬了很多东西来，打算一边阅读源码一边参照别人的博客然后进行完善。）
