如果用一句话总结的话：HashMap 由“数组 + 链表/红黑树”组合而成，初始容量为16，扩容方式为“新容量 = 原容量*2”，负载因子为 0.75，支持一个 null 键和多个 null 值，链表和红黑树之间的转换边界为 6 和 8，线程不安全。
1.基本框架
HashMap作为Map家族的代表，它的其他几个“亲戚”都是基于HashMap在一定程度上的模仿、修改得来的，简单认识一下即可。
（01）WeakHashMap：把HashMap的键从强引用变为弱引用，当某个键不再被使用后，WeakHashMap同该键产生的「引用联系」并不阻止垃圾回收器的回收。
（02）HashTable：把HashMap的方法用synchronized关键字包装一遍，通过牺牲大部分性能来实现线程同步。
（03）LinkedHashMap：把HashMap的底层从数组改为双向链表。
（04）IdentityHashMap：允许键相等（即equals方法返回true而用==符号则返回false）的HashMap。
不过TreeMap比较特殊，它的共同点就只是储存元素都为键值对罢了。
2.深入源码
2.1 底层结构
2.1.1 龙骨
如果把HashMap比作一头喷火龙，那这个名为table的Node型数组就是它的“龙骨”了。Node是定义在HashMap内部的一个静态类，它除了可以存储键值对，还可以很方便地拓展成一条链表（通过Node<K,V> next）。
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
..
}
2.1.2 龙翼
当发生哈希冲突时，HashMap采用“拉链法”将这些带有相同键的Node对象们保存在table的同一个位置，准确地说是把它们保存在该位置上的Node链表中串起来，就像一条展开的“龙翼”。
2.2 创建HashMap对象
HashMap的构造函数围绕初始容量initialCapacity和负载因子loadFactor的有无共设计了三个方法，它们的共同目的都是为了确定该HashMap对象的阈值上限threshold。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
}
仔细分析代码后会发现，默认构造函数其实什么也没干只是把负载因子初始化为默认的0.75f，而另外两个构造方法抛开边界检测和参数合法性检测不谈，核心其实是最后那句tableSizeFor方法的调用，而这也是构造阶段最有价值的东西。
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int tableSizeFor(int cap) {
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;
}
tableSizeFor其实是一个寻找大于或等于给定参数，同时还是2的高次幂的最小值的算法，比如参数5、6、7或8则都返回8，而参数9则返回16，其中>>>符号是不分正负的右移符（高位始终用0进位）。
其中，先减1后加1是为了让原本就是2的幂次方的数能够返回自己，最好是自己手动实现一遍就明白算法的原理了。
2.3 添加元素
当我们添加元素到HashMap中的时候，会先判断table数组或者说“龙骨”是否有初始化，因为HashMap的构建函数只负责确定threshold，这样当添加第一个元素时，还应该负责table数组的初始化。
之后，我们先计算哈希值，并根据哈希值找到对应位置（hashKey(key)）。这时候，根据前面的理论，这个位置可能是空的，也有可能是一条单链表，还有可能是一颗红黑树，不同情况对应不同的操作，而它们的抉择过程全都被放在了putVal方法中。
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 检测是否为空或长度为0，如果是则resize（要掌握resize）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算对应下标并检测是否已经有人占坑了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 判断节点p（tab[i]的第一个节点）是否同输入节点相同，是就让e=p（此时e！=null）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判断p是不是红黑树，是就用putTreeVal方式插入（putTreeVal要掌握）
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果都不是，那p就是单链表的头节点
else {
for (int binCount = 0; ; ++binCount) {
//到尾巴了，进行插入节点操作，并检测节点长度是否大于8（7=8-1是下标位置）
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在遍历过程中遇到相同节点（==或者equals）就返回（此时e！=null）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果e！=null表示存在对应映射的键，应执行覆盖操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2.3.1 resize()方法
可以看到，在获取table数组长度时，如果table数组为空或者长度为零，将会对HashMap对象进行resize操作，从而初始化table数组。
在resize方法里，我们首先要判断是被谁调用的从而选择后序执行的操作，如果table数组的长度为空或者长度为零，那显然是要对数组进行初始化操作，而如果长度大于0，则是进行数组扩容操作。
在resize方法中，我们主要目的是用一个具有新容量capacity和新阈值threshold的数组去替换旧数组。而替换必然伴随着值传递，我们对旧数组进行遍历，对里面的每个table[i]依照类型（null、链表、红黑树）作不同的复制。对于链表，我们先将头节点复制到新数组哈希计算后的对应位置，然后将其原来节点设置为空，若它还有后继节点则用do-while循环这一过程。
static final int MAXIMUM_CAPACITY = 1 << 30;
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) {
// 旧容量超过了最值1 << 30，则容量不变
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 设新容量为旧容量的两倍，如果旧容量的两倍小于最值1 << 30并且旧容量大于等于16，则阈值翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 第一次添加元素，但不是用的默认构造函数HashMap（），而是设置了capacity的
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 第一次添加元素，而且还是用的默认构造函数HashMap（）
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新阈值还是0，即如果第一次添加且预设capacity或者不是第一次添加，且新容量大于最值
// 或者旧容量小于16
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])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;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
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;
}
2.3.2 putTreeVal()方法
了解putTreeVal()方法前，我们需要学习红黑树算法相关知识。
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
// 判断哈希值
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
// 哈希值相等后则判断是否equals，是则说明找到该点了
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 看不懂了。。爷太难了
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
// 创建新结点进行插入
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
2.4 获取元素
相比之下，获取元素可就简单多了。我们只需要传入键，get方法通过哈希函数计算出对应哈希值，再根据哈希值找到对应数组位置。
哈希函数是对键对象的哈希码（一个32位的二进制数）和其右移16位后的“自己”进行异或操作，让哈希码高位参与运算的原因同对应数组位置映射有关。HashMap中哈希值与数组位置的映射关系是(n - 1) & hash，其本质是hash % (n - 1)，而又由于HashMap在构造函数中就将n限定为2的幂次方，因此n - 1的二进制形式必然是高位全为0，低位全为1。现在，再回头审视这个映射关系，会发现其结果等于哈希值的低位数值，而这个低位位数由table数组长度决定。因此，我们有了答案，让哈希码高位参与运算的原因是为了使对象在table上的分布更分散。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
getNode内部逻辑也很简单，其核心是寻找键对象相等的节点，即哈希值相等，键对象相等（这里的相等指equals返回为true），如果没有找到对应节点则返回null值。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果数组不为空或长度为零，且键对象对应数组下标节点不为空
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;
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;
}
3.HashMap的遍历
3.1 遍历HashMap的键值对
第一步：根据entrySet()获取HashMap的“键值对”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
// 获取key
key = (String)entry.getKey();
// 获取value
integ = (Integer)entry.getValue();
}
3.2 遍历HashMap的键
第一步：根据keySet()获取HashMap的“键”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
// 获取key
key = (String)iter.next();
// 根据key，获取value
integ = (Integer)map.get(key);
}
3.3 遍历HashMap的值
第一步：根据values()获取HashMap的“值”的集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}