以下为HashMap（JDK 1.8）插入元素的流程图：
特点
继承
AbstractHashMap；
JDK 1.8之前采用数组 + 链表实现，后使用 数组+ 链表+ 红黑树实现；初始容量 16；初始扩容因子 0.75；增量 2n；
key和value都可以为null；
如果自己传入初始大小k，初始化大小为大于k的2的整数次方。
底层结构
线程安全
JDK 1.7
循环链表 + 节点覆盖。
举两个栗子：
A. 两个线程同时进行新增节点时，同时执行put()，且两个Key都指向一个Hash槽，则当前两个节点都进行头插法：
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e); // 节点覆盖
size++;
}B. 线程A和线程B，扩容时，调用resize()方法进行头插法：
void resize(int newCapacity)
{
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
......
Entry[] newTable = new Entry[newCapacity];
//数据迁移
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;// 并发情况下假设线程一执行到这儿即被挂起
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}参考自：https://www.cnblogs.com/chanshuyi/p/java_collection_hashmap_17_infinite_loop.html
正常的reHash过程
并发下的reHash过程
阶段一：（线程一挂起，线程二执行至完毕，此时e => 3， next => 7）
阶段二：（线程一继续执行，获取e => 3的索引i，newTable[i]获取当前Hash槽位置，e.next = newTable[i]表示3.next = newTable[i]，然后newTable[i]=e表示节点3为槽的首节点，e=next表示7为e指向的节点）
本轮结束后为下图二状态：
阶段三：（线程一继续执行，next = e.next表示next => 3，e.next=newTable[i]; newTable[i]=e;表示槽的首节点改为7，next则继续为3）
阶段四：出现环形链表
e.next = newTable[i] 导致key(3).next指向了 key(7)
JDK 1.8
节点覆盖（节点丢失）。
直接看源码吧：
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) // 当前Hash槽长度 == 0
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 当前Hash槽为null
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 遇到相同的hash（key）
e = p;
else if (p instanceof TreeNode) // 当前节点为TreeNode
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { // 当前节点为tail节点
p.next = newNode(hash, key, value, null); // 这一步在多线程环境下容易发生节点覆盖
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}Fail-fast（快速失败）
是java集合中的一种错误检测机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
HashMap用modCount进行并发控制：
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;以下是译文：
对该
HashMap进行结构修改的次数结构修改是指更改HashMap中的映射次数或以其他方式修改其内部结构（例如，重新哈希）的修改。 此字段用于使HashMap的Collection-view上的迭代器快速失败。 （请参见ConcurrentModificationException）。
原理
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。
每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
问题
什么是Hash？
把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；
这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。
但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
HashMap的Hash函数怎么设计？
hash函数是先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或（^）操作。
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}以下是译文：
计算
key.hashCode（）并将哈希的较高位扩展（逻辑异或）到较低位。 由于该表使用2的幂次掩码，因此仅在当前掩码上方的位中发生变化的哈希集将始终发生冲突。 （众所周知的示例是在小表中保存连续整数的Float键集。）因此，我们应用了一种将向下扩展较高位的影响的变换。 在速度，实用性和位扩展质量之间需要权衡。 由于许多常见的哈希集已经合理分布（因此无法从扩展中受益），并且由于我们使用树来处理容器中的大量冲突，因此我们仅以最便宜的方式对一些移位后的位进行逻辑异或，以减少系统损失， 以及合并最高位的影响，否则由于表范围的限制，这些位将永远不会在索引计算中使用。
为什么这么设计？
叫扰动函数，这么设计有二点原因：
- 一定要尽可能降低hash碰撞，越分散越好；
- 算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；
为什么HashMap的长度是2的幂次方？
HashMap为了存取高效，减少冲突，尽量将数据分配均匀，使用取模 (hash%(length-1)),计算机中hash&(length-1)效率更高，只有length是2的n次方时，hash%(length-1) == hash&(length-1)；
为什么采用hashcode的高16位和低16位异或能降低hash碰撞？hash函数能不能直接用key的hashcode？
因为key.hashCode() 函数调用的是key键值类型自带的哈希函数，返回int型散列值。
int值范围为-2147483648~2147483647，前后加起来大概40亿的映射空间。
只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
但问题是一个40亿长度的数组，内存是放不下的。
如果HashMap数组的初始大小才16，用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。
HashMap源码中模运算就是把散列值和数组长度-1做一个”与”操作，位运算比%运算要快。
初始阀值为啥为0.75？
根据==泊松分布==，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。
为什么HashMap的数组长度要取2的整数幂？
因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。
JDK1.7和JDK1.8区别？
将头插法变为尾插法（1.7头插；1.8尾插）
线程安全：
头插法，多线程成环；
尾插法，造成节点丢失；A线程在插入节点B，B线程也在插入，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环。
在插入时，1.7先判断是否需要扩容，再插入；
1.8先进行插入，插入完成再判断是否需要扩容；
1.7为数组+链表；
1.8为数组+链表+红黑树；防止发生hash冲突，链表长度过长，将时间复杂度由
O(n)降为O(logn);
HashMap为什么1.7采用头插？
- 效率问题，尾插需要多次遍历；
- 一贯的思维，新插入的节点要更可能被再次调用；
HashMap和HashTable的区别？
- 线程是否安全：
HashMap是非线程安全的HashTable是线程安全的
- 对
Null key和Null value的支持：HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null；HashTable中，put进的键值只要有一个为null，直接抛出NullPointerException；
- 初始容量大小和每次扩充容量大小的不同：
HashMap默认的初始化大小为==16==，每次扩充，容量变为原来的2倍。当初始给出大小后，HashMap会将其扩充到2的幂次方；HashTable初始的容量大小为==11==，每次扩容，容量变为原来的2n+1；
参考：
JDK 1.7 & 1.8 HashMap源码
