HashMap
必备知识——哈希表
数组的特点：寻址容易，插入和删除困难
链表的特点：寻址困难，插入和删除容易
HashMap就是将数组和链表组合在一起
源码：
p instanceof TreeNode
instanceof 严格来说是Java中的一个双目运算符，用来测试一个对象是否为一个类的实例
哈希表
哈希表就是数组，哈希表中关键码就是数组的索引下标，然后通过索引直接访问数组中的元素，
哈希表都是用来快速判断一个元素是否出现集合里
哈希函数
把数组中的元素映射为哈希表上的索引
为了保证HashCOde映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。
哈希碰撞
如果元素的数量大于哈希表的大小，此时就算哈希函数计算的再均匀，也避免不了会有几个元素同时映射到哈希表同一个索引下表的位置。
解决办法
1. 拉链法
要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间
2. 线性探测法
使用线性探测法，一定要保证tableSize大于dataSize。依靠哈希表中的空位来解决碰撞问题。
HashMap详解
数据结构：
jdk1.7：数组+链表 保存的值hash、key、Value
jdk1.8：数组+链表+红黑树
红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。
数组：存放(key—Value) 别名：Entry(Java7),Node(Java8)
put插入时根据key的hash去计算一个index值
初始化长度：16
位运算，默认长度16
DEFAULT_INITIAL_CAPACITY = 1 << 4;
jdk7、jdk8的区别
1. jdk1.7：Entry采用头插法，新来的值会取代原有的值，原有的值就顺推到链表中去，后来的值查询可能性更大一点，提升查询效率。在多线程操作HashMap时可能引起死循环原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。。
jdk1.8：Node采用尾插法。避免jdk1.7头插法会出现环形链表。put/get方法都没有加同步锁，无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。
hashmap的扩容机制
数组容量是有限的，数据多次插入，到达一定的数量就会扩容
两个因素：
1.capacity：HashMap当前长度
2.LoadFactor：负载因子，默认0.75
步骤：
长度扩大后，Hash的值也随之改变，所以不能直接复制
1.扩容：创建一个新的Entry空数组，长度是原数组的两倍
2.ReHash：遍历Entry数组，把所有的Entry重新hash到新数组
为啥初始容量是16
实现均匀分布
Hash公式 index = HashCode(Key) & (Length-1)
因为在使用不是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值,只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
i = (n - 1) & hash
为啥重写equals()方法需要重写HashCode方法
对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。
equals:
1.对于值对象，==比较的是两个对象的值
2.对于引用对象，比较的是两个对象的地址
对equals方法进行了重写，建议一定要对hashCode方法重写，保证相同的对象返回相同的hash值，同的对象返回不同的hash值。
HashSet保证元素不重复
HashSet底层数据结构是哈希表, 哈希表能保证元素的唯一性。
add()方法调用的是hashMap的put方法
private transient HashMap<E,Object> map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
