数据结构
jdk1.7 ：数组 + 链表（单向）
jdk1.8 ：数组+链表（单向）+红黑树
概念：
数组：一段连续的节点组成的内存区域，在内存中连续存储
链表：一段非连续的节点组成的存储结构，分为单向链表（最后一个节点的next 指向null）和双向链表（两个指针，pre 指向上一个节点，next 指向下一个节点，第一个节点的pre 指向null，最后一个节点的next 指向null）。
单向循环链表：最后一个节点next 指向head
双向循环链表：最后一个节点next 指向head，第一个节点pre 指向最后一个节点，linkedList 采用的就是这种
而hashMap 采用单向链表就是为了避免循环引用
jdk 1.7 中的数据存储结构：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
}
put 操作
1.若数组不存在，会初始化一个默认容量（1<<4=16） 的一个数组
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
此处没有直接写16（10000），用的是位移，是为了增加效率
1.1. 由于数据长度为16，所以向数组中放入数据时，数组的下标index 应该为0-15。
- 取模：用key.hashCode%16 取模得到，但是取模运算比较耗时
- 位运算（& 与）：所以采用位运算与 (n - 1) & hash（直接对内存数据进行运算，不需要转成十进制，1&1 =1）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
为了让key更均匀的分布，对hash 做异或 ^，在高低16位
hash = key.hashCode^key.hashCode >>>16
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
初始容量和扩容为什么一定是2的整数次幂（面试点）
和与的计算有关，因为与操作是对应位置都为1 时，计算结果才为1，当hashmap 的容量为2的n 次幂时，n-1 的二进制才是1111***111，这样和添加的元素hash 与操作时才能更充分的散列，减少hash 碰撞，使添加的元素更均匀的分配的hashmap上。
2.如果存在，查找key 如果有值，替换原来的，并返回老的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
如果没有，将新插入的节点放到尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
头插法（1.7）和尾插法（1.8）的区别（面试点）
- 头插法：从链表头部插入，多线程会产生闭环，插入慢
- 尾插法：从链表尾部插入，不会产生闭环，插入快。
2.1 instanceof 方法会判断节点的类型是否为tree
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- 链表转红黑树：因为树节点所占空间是普通节点的两倍，所以只有当节点足够多(长度大于8，泊松分布)的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins.
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
3.2 转红黑树条件2 数组的长度大于64
static final int MIN_TREEIFY_CAPACITY = 64;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
3.3 当长度小于6时，在转为链表
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
扩容 resize
当数组的长度大于 默认值16* 加载因子0.75（泊松分布）时会扩容 ,最大值为2的30次幂
if (++size > threshold)
resize();
扩容完成后，新数组的长度为老数组的2倍，新数组的下标为老数组的下标+计算下标
hashmap 容量的设置（面试点）
当我们明确知道HashMap中元素的个数的时候，把默认容量设置成expectedSize / 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存。
