HashMap底层实现
1.HashMap结构
紫色部分代表哈希表，就是一个数组，数组的每个元素都是一个单链表的头结点，链表是用来解决hash地址冲突的。 如果不同的key映射到数组的同一个位置，就将其放进单链表中保存。
2.HashMap有四个构造方法，其中有两个很重要的参数：初始容量，加载因子
01）这两个参数是影响HashMap性能的重要参数。容量代表哈希表中槽的数量，即：哈希数组的长度，初始容量是创建哈希表时的容量（默认为16）。
02）加载因子是哈希表实际容量和当前长度的比值，当哈希表中的条目数超出了哈希表的长度和加载因子的乘积，则要对哈希表进行提前扩容。
03）如果加载因子过大，空间的利用更充分，但查询效率会降低，因为链表的长度会越来越长；如果加载因子过小，那么表中数据太稀松，很多空间没用就扩容。
04）JDK开发者规定默认的加载因子为0.75f,因为这是一个理想值。
05）无论指定初始容量为多少，构造方法会将实际哈希表长度设为不小于指定容量的2的幂次方，且最大不超过2的30次方。
3.put方法
流程：
调用put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
间接调用hash()方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
又间接调用key类的hashCode()方法，所以重写equals方法的时候，一定要重写hashCode方法，因为key是基于hashCode来处理的。
当key为null时返回0，即putValue中的hash为0
put()实际是调用putVal()方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
其中：
01)if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
放入第一个元素时table为空，触发resize方法（初始化长度为16的数组，但逻辑长度为0）
02）if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
n为hash数组长度，hash是传过来的，i为计算出来的数组下标，用&（位运算符）计算出i的值，当hash为0时，&0得0，
即：当key为null时，计算出来的i为0（即put的元素放在数组的第一个）
p为坐标i数组的元素，如果这个元素为Null，就用Key Value构造一个Node对象放入数组下标为i的位置
注：实际HashMap就是存放Node对象的数组
put
4.put方法中，计算出来的数组下标相同时
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
......
......
p = e;
}
计算出来的i相同时，且不满足覆盖（覆盖后面讲解），
此时就new一个新的Node对象，并把当前i位置上的next指向该新Node对象，即转成了单向链表。
当后面继续添加元素i相同时，遍历链表，直到找到next为空的Node对象，new一个新Node对象,找到的Node对象next指向该新对象。
static final int TREEIFY_THRESHOLD = 8;
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
当遍历链表次数到达7次，即链表长度到达8，将链表转化为红黑树来处理。【红黑树未知？】
5.put方法中的覆盖
01）不是在链表中找到符合覆盖value要求的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
计算出i找到数组中的元素p，p的hash等于put新元素的hash并且（key相等或者key的equals相等）
则符合覆盖要求。
02）在链表中找到符合覆盖的value要求的key
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
遍历链表找到匹配的key
用新的value替换旧的value，返回旧的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
6.put方法中计算出来的i对应的是树结构（覆盖和添加新节点）
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
其中 putTreeVal(this, tab, hash, key, value)方法
for (TreeNode p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
......
......
if ((p = (dir <= 0) ? p.left : p.right) == null) {
......
......
for循环遍历树
其中：
01）else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
如果put的key==或equals节点的key，即：在树中存在符合覆盖value条件的Key,返回该节点，就会执行上述覆盖value的操作。
02）if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node xpn = xp.next;
TreeNode 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)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
遍历完后还是没有找到key，就在树中添加新节点，返回null，不会执行覆盖操作
和链表类似，循环遍历树的节点，如果找到节点就返回节点，如果循环完整个树都找不到相应的key就添加新节点。
7.总结
01）计算key的hash值，为null则为0，i=(n-1)&hash，i为数组下标。
02）满足hash值相等，key==或equals的结果为true，满足这两个条件即满足替换value。
03）get（）方法和覆盖差不多，计算出来i，为单个对象就判断，为链表就遍历链表，为树就遍历树，三种情况判断条件就是判断覆盖的条件。
