前言
基于 Map 接口实现的一种键-值对<key,value>的存储结构，允许 null 值，同时非有序，非同步(即线程不安全)。
底层实现是数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分）。
它存储和查找数据时，是根据键 key 的 hashCode 的值计算出具体的存储位置。
增删改查等常规操作都有不错的执行效率，是 ArrayList 和 LinkedList 等数据结构的一种折中实现。
结构
核心组成部分
int size： HashMap 实际存储元素的个数；float loadFactor：负载因子（默认是 0.75，此属性后面详细解释）。int threshold: 下一次扩容时的阈值，达到阈值便会触发扩容机制 resize（阈值 threshold = 容器容量 capacity * 负载因子 load factor）。Node<K,V>[] table: 底层数组，充当哈希表的作用(1.7使用的是Entry数组)，用于存储对应 hash 位置的元素 Node<K,V>，此数组长度总是 2 的 N 次幂。（具体原因后面详细解释）
哈希表结构
final int hash: 元素的哈希值，决定元素存储在 哈希表中位置;final K key: 键，由 final 修饰可知，当 key 的值确定后，就不能再修改。V value: 值Node<K,V> next: 记录下一个元素结点(单链表结构，用于解决 hash 冲突)
hash值的计算？
对于key的hashCode：Java7 做了 4 次 16 位右位移异或混合，Java 8 中这步已经简化了，只做一次 16 位右位移异或混合，而不是四次，但原理是不变的。
hash冲突？
得到的hash值与哈希表长度取模，得到具体的存储位置，而多个元素取模运算的值可能相同，这种现象称为hash冲突或hash碰撞。
hash冲突的避免？
右位移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
hash冲突的解决？
HashMap是使用链地址法解决hash冲突的，当有冲突元素放进来时，会将此元素插入至此位置链表的最后一位，形成单链表。但是由于是单链表的缘故，每当通过hash % length找到该位置的元素时，均需要从头遍历链表，通过逐一比较hash值，找到对应元素。如果此位置元素过多，造成链表过长，遍历时间会大大增加，最坏情况下的时间复杂度为O(N)，造成查找效率过低。所以当存在位置的链表长度 大于等于 8 时，HashMap会将链表 转变为 红黑树，红黑树最坏情况下的时间复杂度为O(logn)。以此提高查找效率。
HashMap 的容量为什么一定要是 2 的 n 次方？
运算效率高？
具体确定此元素的位置是通过
hash值%模上 哈希表Node<K,V>[] table的长度hash % length计算的。但是”模”运算的消耗相对较大，通过位运算h & (length-1)也可以得到取模后的存放位置，而位运算的运行效率高，但只有 length 的长度是 2 的 n 次方时，h & (length-1)才等价于h % length。分布均匀？
而且当数组长度为 2 的 n 次幂的时候，不同的
key算出的index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
HashMap里的size属性到底指的是数组实际长度还是键值总数?
HashMap里的size属性指的就是键值总数，因为哪怕新加的元素和旧元素hash值相等而equals结果不同，会处于同一链表中，size一样会加一，而size大小最终决定了是否要进行扩容。
HashMap的负载因子初始值为什么是0.75？
负载因子过大，哈希冲突增加，虽然空间利用率上去了，但是时间效率降低了。
负载因子过小，虽然时间效率提升了，但是空间利用率降低了。
负载因子是0.75的时候，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。
增删改查
put
判断哈希表
Node<K,V>[] table是否为空或者null，是则执行resize()方法进行扩容（初始化）。计算储存位置，如果存储位置没有元素存放，则将新增结点存储在此位置
table[i]。如果存储位置已经有键值对元素存在，则判断该位置元素的
hash值和key值是否和当前操作元素一致，一致则证明是修改value操作，覆盖value即可。当前存储位置即有元素，又不和当前操作元素一致，则证明此位置
table[i]已经发生了hash冲突，则通过判断头结点是否是treeNode，如果是treeNode则证明此位置的结构是红黑树，已红黑树的方式新增结点。- 如果不是红黑树，则证明是单链表，将新增结点插入至链表的最后位置，随后判断当前链表长度是否 大于等于 8，是则将当前存储位置的链表转化为红黑树。遍历过程中如果发现
key已经存在，则直接覆盖value。 - 插入成功后，判断当前存储键值对的数量 大于 阈值
threshold是则扩容。
- 如果不是红黑树，则证明是单链表，将新增结点插入至链表的最后位置，随后判断当前链表长度是否 大于等于 8，是则将当前存储位置的链表转化为红黑树。遍历过程中如果发现
get
计算储存位置，判断储存位置是否有元素存在。
- 如果存储位置有元素存放，则首先比较头结点元素，如果头结点的
key的hash值 和 要获取的key的hash值相等，并且 头结点的key本身 和要获取的key相等，则返回该位置的头结点。 - 如果存储位置没有元素存放，则返回
null。 - 如果存储位置有元素存放，但是头结点元素不是要查找的元素，则需要遍历该位置进行查找。
- 如果存储位置有元素存放，则首先比较头结点元素，如果头结点的
先判断头结点是否是
treeNode，如果是treeNode则证明此位置的结构是红黑树，以红色树的方式遍历查找该结点，没有则返回null。如果不是红黑树，则证明是单链表。遍历单链表，逐一比较链表结点，链表结点的
key的hash值 和 要获取的key的hash值相等，并且 链表结点的key本身 和要获取的key相等，则返回该结点，遍历结束仍未找到对应key的结点，则返回null。
删除 remove
计算储存位置，判断储存位置是否有元素存在。
- 如果存储位置有元素存放，则首先比较头结点元素，如果头结点的 key 的 hash 值 和 要获取的 key 的 hash 值相等，并且 头结点的 key 本身 和要获取的 key 相等，则该位置的头结点即为要删除的结点，记录此结点至变量 node 中。
- 如果存储位置没有元素存放，则没有找到对应要删除的结点，则返回 null。
- 如果存储位置有元素存放，但是头结点元素不是要删除的元素，则需要遍历该位置进行查找。
先判断头结点是否是
treeNode，如果是treeNode则证明此位置的结构是红黑树，以红色树的方式遍历查找并删除该结点，没有则返回null。如果不是红黑树，则证明是单链表。遍历单链表，逐一比较链表结点，链表结点的
key的hash值 和 要获取的key的hash值相等，并且 链表结点的key本身 和要获取的key相等，则此为要删除的结点，记录此结点至变量node中，遍历结束仍未找到对应key的结点，则返回null。如果找到要删除的结点
node，则判断是否需要比较value也是否一致，如果value值一致或者不需要比较value值，则执行删除结点操作，删除操作根据不同的情况与结构进行不同的处理。- 如果当前结点是树结点，则证明当前位置的链表已变成红黑树结构，通过红黑树结点的方式删除对应结点。
- 如果不是红黑树，则证明是单链表。如果要删除的是头结点，则当前存储位置
table[i]的头结点指向删除结点的下一个结点。 - 如果要删除的结点不是头结点，则将要删除的结点的后继结点
node.next赋值给要删除结点的前驱结点的next域，即p.next = node.next;。
HashMap当前存储键值对的数量- 1，并返回删除结点。
替换 replace
先调用
hash(key)方法计算出key的hash值随后调用
getNode方法获取对应key所映射的value值 。记录元素旧值，将新值赋值给元素，返回元素旧值，如果没有找到元素，则返回
null。
java7 和 java8
链表成环
java7使用头插,java8使用尾插。
- Java7 在多线程操作 HashMap 时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
- Java8 在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。
Entry数组和Node数组
其实这两者没有多大区别，叫Node可能更准确，也与红黑树的加入（TreeNode)相呼应。
红黑树
JDK7中HashMap采用的是位桶+链表的方式。而JDK8中采用的是位桶+链表/红黑树的方式，当某个位桶的链表的长度超过8的时候，这个链表就将转换成红黑树。
默认链表长度大于8时，转为红黑树。红黑树桶数量小于6时，转为链表。
当哈希表中的容量大于64时，表中的桶才能进行树形化，否则只是扩容解决。
扩容
jdk7里hashmap resize时对每个位桶的链表的处理方式（transfer方法），整体过程就是先新建两倍的新数组，然后遍历旧数组的每一个entry，直接重新计算新的索引位置然后头插法往拉链里填坑。
jdk8又不一样，因为我们使用的是 2 次幂的扩展(指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。我们在扩充
HashMap的时候，不需要重新计算hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引+oldCap”。这个设计确实非常的巧妙，既省去了重新计算
hash值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
您能说说 HashMap 和 HashTable 的区别吗？
- Hashtable 继承了 Dictionary 类，而 HashMap 继承的是 AbstractMap 类。
- HashMap允许null键null值，hashTablle的key和value都不能为null。
- hashMap初始容量为16，hashTable初始容量为11。
- hashTable线程安全，hashMap不是线程安全的。
注：Hashtable是一个遗留容器，如果我们不需要线程同步，则建议使用HashMap，如果需要线程同步，则建议使用ConcurrentHashMap。
容器整体结构
HashMap的key和value都允许为null，HashMap遇到key为null的时候，调用putForNullKey方法进行处理，而对value没有处理。Hashtable的key和value都不允许为null。Hashtable遇到null，直接返回NullPointerException。
初始化容量和扩容机制
HashMap默认初始化容量为 16，并且容器容量一定是 2 的 n 次方，扩容时，是以原容量 2 倍 的方式 进行扩容。Hashtable默认初始化容量为 11，扩容时，是以原容量 2 倍 再加 1 的方式进行扩容。即int newCapacity = (oldCapacity << 1) + 1;。
- 迭代方式不同
HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。
- 线程安全（最重要）
HashMap不是线程安全，如果想线程安全，可以通过调用synchronizedMap(Map<K,V> m)使其线程安全。但是使用时的运行效率会下降，所以建议使用ConcurrentHashMap容器以此达到线程安全。Hashtable则是线程安全的，每个操作方法前都有synchronized修饰使其同步，但运行效率也不高，所以还是建议使用ConcurrentHashMap容器以此达到线程安全。
因此，
谈谈 HashMap 线程不安全的体现
put丢失数据。
put和get并发时，可能导致get为null。
jdk7 resize方法可能造成死循环。