在JDK1.8中，HashMap的改进是一个很大的亮点，其源码也多次被提及，今天就让我们来聊一下它！
HashMap内部的数据结构是什么
HashMap的数据结构是哈希表，哈希表采用开放地址法和链地址法等来解决冲突问题，HashMap用的是链地址法，即数组加链表。每个数组元素上有一个链表结构，数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。另外，JDK1.8新增了红黑树，当链表过长时会将链表转成红黑树以实现O(logn)时间复杂度内查找。
HashMap的put方法执行过程是怎样的
在JDK1.8中，put方法的性能得到了大幅提升，我们这里以JDK1.8为例进行讲解：
-
判断键值对数组table是否为null或长度为0，如果是，执行resize()进行扩容
Node是HashMap的内部类，实现了Map.Entry接口，本质就是一个键值对，table是一个元素为键值对的数组，如果执行put操作时判断table为空或长度为0，则调用resize()函数进行扩容。
resize()函数主要是负责初始化数组或将数组的容量扩展到原来的两倍，其具体实现和源码解析如下：
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; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 没超过最大值，则扩充为原来的两倍 newThr = oldThr << 1; } else if (oldThr > 0) // 用可容纳键值对极限threshold表示初始容量，可通过构造函数设置threshold newCap = oldThr; else { // threshold的初始值为0时，采用默认初始容量，即16 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } 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) { 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 { // 保留顺序 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; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }HashMap的table长度要求为2的n次方，这是非常规设计，常规是把桶大小设计为素数，素数导致冲突的概率小于合数，证明可参考这里。HashMap采用这种非常规设计，主要是为了取模和扩容时做优化。
-
根据key计算hash值得到插入索引i，如果table[i]还没有节点，新建节点添加并跳到第6步，否则执行下一步
在JDK1.8中，HashMap的hash函数如下：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }HashMap只允许一条记录的键为null，允许多条记录的值为null。对于key为null的情况，hash的结果为0，如果key不为null，hash函数则是先取key的hashCode值，再通过移位异或运算得到hash值。
-
判断table[i]的首个元素是否和key相同，如果相同直接覆盖，否则执行下一步
这里的相同指的是hashCode以及equals两个方法同时满足相同条件，也就是说，即使两个hashCode值相同的key，也可以被同时存储到HashMap中。
-
判断table[i]是否为treeNode，即table[i]是否为红黑树，如果是则在树中插入键值对，否则执行下一步
-
遍历table[i]，判断链表长度是否大于8，大于8则把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作。遍历过程中若发现key已存在直接覆盖value即可
HashMap将键值对划分到不同桶，桶数量通常比记录数稍大，这样每个桶的值会较少（最好是一个）。当通过key查找时，可以在O(1)内定位到某桶以及要找的对象。最坏情况下，所有key都映射到同个桶中，这样HashMap退化成了链表，查找时间从O(1)变成了O(n)。如果某个桶中的记录过大的话（我们设置阀值TREEIFY_THRESHOLD为8），HashMap会动态地将它替换成一个红黑树。这样会将时间复杂度从O(n)降为O(logn)。
-
插入成功后，判断实际存在的键值对数量size是否超过最大容量threshold，如果超过，进行扩容
HashMap和Hashtable有什么区别
- HashMap可以接受为null的key和value，而Hashtable不行
- HashMap是非线程安全的，而Hashtable是是线程安全的
- HashMap的迭代器Iterator是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所谓fail-fast，就是其他线程不能修改正被Iterator遍历的集合里的对象
- Hashtable是线程安全的，所以单线程下比HashMap要慢。如果只需单一线程，那么使用HashMap好过Hashtable
- HashMap不能保证随着时间的推移Map中的元素次序是不变的
事实上，Hashtable是JDK1.0的产物，HashMap就是用来替代Hashtable的，所以在这两者之间优先选择HashMap。
HashMap和ConcurrentHashMap有什么区别
- ConcurrentHashMap是线程安全的，并发环境下不要额外同步，而HashMap是非线程安全的
- 可以用
Collections.synchronizedMap(HashMap)包装HashMap作为同步容器，这时它的作用几乎与Hashtable一样，每次对Map做修改时都会锁住Map对象，而ConcurrentHashMap会基于并发等级划分Map达到线程安全，它只会锁操作的那段数据而不是整个Map - ConcurrentHashMap在多线程下性能比做了同步的HashMap要好，但在单线程下，HashMap更好一点