HashMap是什么
HashMap是一个链表散列（数组和链表），存储是键值对（key-value）映射，HashMap很快（非synchronized）。
HashMap 是基于哈希表的Map接口的非同步实现。
实现提供所有可选的映射操作，并允许使用null值和null键（HashTable不能），键位置只能是一个null。
此类不保证映射的顺序，特别是不保证顺序永恒不变。
因JDK版本的变化
JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用==链表处理哈希冲突== （两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同），同一hash值的键值对会被放在同一个位桶里，当桶中元素较多时，通过key值查找的效率较低。
JDK1.8中，HashMap采用位桶+链表+红黑树实现，==当链表长度超过阈值（或红黑树的边界值，默认为8）并且当前数组的长度大于64时（小于64时对数组进行扩容），此时将链表转换为红黑树，具体查看 treeifBin 方法==；这样大大减少了查找时间，提高效率。
链表散列的优势
数组、链表单独使用时的优劣
数组：存储区间连续、占用内存严重，故空间复杂度很大。但数组的二分查找时间复杂度小，为O(1)。特点：寻址容易，插入、删除困难。
链表：存储区间离散，占用内存宽松，故空间复杂度很小。但时间复杂度很大，为O(N)。特点：寻址困难，插入、删除容易。
HashMap的结构 — 链表散列
链表散列（哈希表）是由数组+链表组成，可视作存储链表的数组。
数组的默认长度为16，可以自动变长。在构造HashMap的时候也可以指定一个长度。
//初始默认数组的大小 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //默认的负载因子 //表示当map集合中存储的数据达到当前数组大小的75%则需要进行扩容 static final float DEFAULT_LOAD_FACTOR = 0.75f;
数组里每个元素存储的是一个链表的头结点。而组成链表的结点其实就是HashMap内部定义的一个类：Entity。
Entity包含三个元素：key，value和指向下一个Entity的next。
HashMap的基本存储原理
设计一个哈希函数（也叫做散列函数）来获得每个元素的Key的函数值（即数组下标，hash值）相对应；数组存储的元素是一个Entry类，这个类有三个数据域（key、value（键值对）、next（指向下一个Entry））。
示例：
第一个键值对A进来，通过计算其 key 的 hash 得到的 index=0；只做：Entry[0] = A。
第二个键值对B进来，通过计算其 key 的 hash 得到的 index 也等于0，HashMap会将 B.next = A，Entry[0] = B。
第三个键值对C进来，通过计算其 key 的 hash 得到的 index 也等于0，那么HashMap将会是 C.next = B，Entry[0] = C。
此时可以看出index = 0 的位置实际上存储了 A、B、C 三个键值对，通过 next 这个属性链接在一起，这个位置称为桶。对于不同的元素，可能计算出了相同的函数值，这样就产生了“冲突”，这就需要解决冲突，“直接定址”与“解决冲突”是哈希表的两大特点。
HashMap的put、get方法详解
put方法详解
判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向第6步，如果table[i]不为空，转向第3步；
判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向第4步，这里的相同指的是hashCode以及equals；
判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向第5步；
遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
get方法详解
指定key 通过hash函数得到key的hash值 int hash=key.hashCode()；
调用内部方法 getNode()，得到桶号(一般都为hash值对桶数求模) int index =hash&(table.length-1)（table是HashMap数组）；
使用遍历方法比较桶的内部元素（Entry链表）是否与key相等，若都不相等，则没有找到。相等，则取出相等记录的value；
如果得到 key 所在的桶的头结点恰好是红黑树节点，就调用红黑树节点的 getTreeNode() 方法，否则就遍历链表节点。getTreeNode 方法使通过调用树形节点的 find()方法进行查找。由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高；
如果对比节点的哈希值和要查找的哈希值相等，就会判断 key 是否相等，相等就直接返回；不相等就从子树中递归查找。
HashMap中的碰撞探测（collision detection）、碰撞的解决方法
碰撞产生
当两个对象的hashcode相同时，它们的bucket位置相同，‘碰撞’会发生。
碰撞的解决
HashMap使用LinkedList存储对象，这个Entry（包含键值对的Map.Entry对象）会存储在LinkedList中；两个对象就算hashcode相同，但是它们可能并不相等。
减少碰撞的方法
当调用get()方法，HashMap会使用键对象的hashcode找到bucket位置； 遍历LinkedList，其中调用keys.equals()方法去找到LinkedList中正确的节点，直到找到值对象； 该值对象使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生、提高效率。 不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String、Integer这样的wrapper类作为键值是非常好的选择。
如何重新调整HashMap的大小
当HashMap的大小超过了负载因子（load factor）定义的容量，该如何处理
默认的负载因子大小是0.75； 即，当一个map填满了75%的bucket时，与其它集合类（如ArrayList等）一样，将会创建原来HashMap的大小两倍的bucket数组，来重新调用map的大小，并将原来的对象放入新的bucket数组中； 这个过程叫做rehashing，因为它调用hash方法找到新的bucket位置。
原文：https://juejin.cn/post/7100421697341227038