刚学习完HashMap，对这几天的学习内容做个总结和记录。
首先HashMap底层数据结构由数组+链表组成，jdk1.8不一样的地方就是当Hash冲突多时，链表会自动装换为红黑树，当链表长度达到8时转换为红黑树，长度为6时转换为链表。HashMap的put操作中，。 当我们向HashMap 入一个键值对<key,value>时，首先将key通过hash函数计算出hash值，根据hash值将<key,value>存放至数组中，当再次传进来的<key2,value2>中key2的hash值和key1的hash值一致时，称为hash冲突，那就需要进一步通过equals比较key1和key2是否相等，因为hashcode相同时，equals不一定相等，相同则将value2覆盖原来的value1，不同在链表或者红黑树中新增节点存储value2，get操作为通过hashcode找到数组位置，后用equals查找对应链表上是否存在该数值，有则返回，没有返回null。
从性能和可靠性 这两方面来分析两者的区别。hashcode函数的性能要比equals的好，equals函数使用较为复杂的算法，来保证equals的高可靠性，而hashcode只是生成其对应的hash值进行比较即可，性能较好处理速度快，但可靠性较低，有可能两个不同的对象生成的hashcode相等，而equals不会出现这种问题。所以我们可以得出：equals相等的两个对象其hashcode一定相等，但hashcode 相等的两个对象其equals不一定相等。所以这就是为什么hashmap先用hashcode确定数值位置，后用equals再次判断数据的存储位置，因为通过hashcode可以快速高效的定位到数组位置，再用equals判断来保证可靠性，将数据存储至链表中。
1、为什么重写equals后一定要重写hashCode
java中规定，equals相等的两个对象hashCode一定相等。Object中默认的equals判断依据是根据两个对象的存放地址是否相等进行判断的，hashCode函数也是将对象内存地址进行一个hash运行得到的一个hash值。所以当你重写你的equals方法，通过判断对象的某个值而不是内存地址来判断两个对象是否相等 ，但是你的hashCode函数还是通过内存地址进行计算，所以这样会出现两个对象 equals相等但hashCode不等的情况。
2、什么时候要重写hashcode和equals
当你定义的类要把他的实例存入集合时需要重写，当你需要重新定义两个对象相等的方法时，默认会通过内存地址进行判断，但你的需求为通过两个对象的某个值进行判断，这时你需要重写。
3、为什么需要用到hashCode
因为 hashCode用来定位小的内存块，通过hashCode会比equals快。
首先来看一下HashMap的存储结构，由数值+链表+红黑树（jdk1.8引进）。
1、先查看一下Node类的源码（JDK1.8），上图的每个黑点就是一个Node对象。
static class Node<K,V> implements Map.Entry<K,V> { final int hash; //⽤来定位数组索引位置 final K key; V value; Node<K,V> next; //链表的下⼀个node Node(int hash, K key, V value, Node<K,V> next) { … } public final K getKey(){ … } public final V getValue() { … } public final String toString() { … } public final int hashCode() { … } public final V setValue(V newValue) { … } public final boolean equals(Object o) { … } }Node类为HashMap一个内部类，其 本质为键值对，实现了Map.Entry接口。
2、HashMap使用哈希表 进行存储，当出现哈希冲突时，java采用链表形式进行解决，就是数值的每个元素其实是一条链表。例如通过以下代码进行存储。
map.put("学校","学生")首先会根据“学校” 这个key的hashCode()计算出一个值， 将这个值进行高位运算与取膜运算后得到最终的hash值，根据这个hash值找到数组下标，有时key会都为到相同的位置，这时产生hash冲突，所以hash 函数设计得好的话可以减少hash冲突的概率，map的存取效率 就会提高。
在HashMap中，无论增加、删除、查找某个键值对，首先都需要计算其hash值来定位到哈希桶数组的位置 ，JDK1.8对hash函数进行了优化，使得hash函数更加的简单高效。
方法一： static final int hash(Object key) { //jdk1.8 & jdk1.7 int h; // h = key.hashCode() 为第一步 取hashCode值 // h ^ (h >>> 16) 为第⼆二步 ⾼高位参与运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 方法⼆： static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个⽅方法，但 是实现原理理一样的 return h & (length-1); //第三步 取模运算 }其中方法一主要为计算key的HashCode值，高位运算，方法二主要为取膜运算。
通过 hashCode可以将key转换为二进制值h，将h右移16位主要是利用h的高位参与h进行异或运算，这样的好处是能够保证哈希桶数组交小的时候，h的高位也能参与hash运算当中，提高散列程度。为什么数组长度小的话，h高位可能不参与hash运算呢，由下图可以看出，当n=8时，n-1的二进制值为...0000 1111，单n-1直接与h 进行&计算的话，因为n-1高位都是0，所以h的高位也全为0，所以应该为（n-1）&（h^(h >>> 16)）而不是（n-1）&（h）。并且JDK1.8中数值的长度必须为2的倍数，这样n-1的高位都为0，低位都为1，保证（n-1）&（h^(h >>> 16)）后的数值不超过数组长度n，并且&的运算效率比%效率高。
并且n设置为2的幂数这样在数值扩容时也有好处，例如n=8扩容后n=16（看下图），当n=8时（a），Key1和Key2计算出的Hash值都一样，当n=16时（b），Key1和没扩容前的key1hash一样，Key2比没扩容前的Key2大了8，也就是大了原来数组的长度，这样的话，原始数组中Key1和Key2本来处于同一条链表中，扩容后Key1和Key2要不就保留在数值原始的位置，要不就保留在原始位置+8的位置上，这样扩容后，可能使得原始哈希桶中的链表长度变短，变得更加散列，提高了HashMap的查询效率 。
以16扩容到32为例：
原始的Key要不保留位置，要不为原始位置+原始数组长度，如下图，hash值为15的元素中，扩容后hash值要不为15，要不为15+16=31，这样让原始的链表更短了。
既然前面提到了扩容机制，那就来看一下HashMap的扩容机制，我们知道，HashMap的主干为数值，数值一旦确定大小就无法修改其大小，如果需要扩大数值的大小，只能再新建一个数组，然后把久数组的元素迁移到新数组，这样就完成了扩容，HashMap的扩容也是如此。接下来分析一下JDK1.7中的resize函数源码，因为JDK1.8融入了红黑树，代码较为复杂，但是实现逻辑一致，后面再将其区别。
void resize(int newCapacity) { //传⼊入新的容量量 2 Entry[] oldTable = table; //引⽤用扩容前的Entry数组 3 int oldCapacity = oldTable.length; 4 if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大 (2^30)了 5 threshold = Integer.MAX_VALUE; //修改阈值为int的最⼤大值(2^31-1)，这样以 后就不不会扩容了 6 return; 7 } 8 9 Entry[] newTable = new Entry[newCapacity]; //初始化1个新的Entry数组 10 transfer(newTable);//！！将数据转移到新的Entry数组⾥里里 11 table = newTable;//HashMap的table属性引⽤用新的Entry数组 12 threshold = (int)(newCapacity * loadFactor);//修改阈值 13 }这个函数主要来评定数值是否满足了扩容需求以及阈值的更新，主要的扩容步骤在transfer函数里面。
void transfer(Entry[] newTable, boolean rehash) { //新table的容量 int newCapacity = newTable.length; //遍历原table for (Entry<K,V> e : table) { while(null != e) { //保存下一次循环的 Entry<K,V> Entry<K,V> next = e.next; if (rehash) { //通过e的key值计算e的hash值 e.hash = null == e.key ? 0 : hash(e.key); } //得到e在新table中的插入位置 int i = indexFor(e.hash, newCapacity); //采用链头插入法将e插入i位置，最后得到的链表相对于原table正好是头尾相反的 e.next = newTable[i]; newTable[i] = e; //下一次循环 e = next; } } }在扩容的数据迁移中，由于jdk1.7使用的是头插法，也就是hash碰撞后，新节点添加在链表的头部，所以原始链表为3、7、5，扩容后（加入扩容后还在同一链表，因为1.7的扩容会根据key重新计算hash值）为5、7、3.。jdk1.8中不是使用的头插法，所以扩容完不会倒序，jdk1.7扩容会重新计算hash值，而1.8只需要了解元素key的原始hash值更高一位bit是0还是1,0则保留元素hash值，1则元素hash值+数值长度。附上1.8的扩容源码。
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; } // 没超过最.大值，就扩充为原来的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 计算新的resize上限 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) { // 把每个bucket都移动到新的buckets中 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 { // 链表优化重hash的代码块 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; } // 原索引+oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 原索引放到bucket⾥里里 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 原索引+oldCap放到bucket⾥里里 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }对数组进行扩容，线程1执行到Entry next = e.next，这时e为3，next为7，打断点，然后让线程2执行完后放开线程1的断点，这时3的next为7,7的next为3，变成环形链表。
由代码可以绘制出put操作的大致流程图为：
