关于HashMap的一些问题

参考文章：
java-并发-ConcurrentHashMap高并发机制-jdk1.8
HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你！
HashMap的一些问题

1. 什么是 HashMap 的 resize ？

HashMap在put的时候会先检查当前数组的length,如果插入新的值的时候使得length > 0.75f * size（f 为加载因子，可以在创建hashMap时指定）的话，会将数组进行扩容为当前容量的2倍。 扩容之后必定要将原有hashMap 中的值拷贝到新容量的hashMap 里面，HashMap 默认的容量为16，加载因子为0.75， 也就是说当HashMap 中Entry的个数超过 16 * 0.75 = 12时, 会将容量扩充为 16 * 2 = 32，然后重新计算元素在数组中的位置，这是一个非常耗时的操作，所以我们在使用HashMap的时候如果能预先知道Map中元素的大小，预设其大小能够提升其性能。

2. HashMap 进行resize的时候为什么扩容的大小都是原来的 2^n ?

在 n 为 2次幂的情况下时，(n - 1) & hash ≈ hash % n ,因为2进制的运算速度远远高于取模，所以就使用了这种方式，所以要求为2的幂。

3. put 的时候出现 hashCode 相同时会怎么办？

hashMap 里面存储的 Entry 对象是由数组和链表组成的，当 key 的 hashCode 相同时，数组上这个位置存储的结构就是链表，这时会将新的值插入链表的表头。进行取值的时候会先获取到链表，再对链表进行遍历，通过 key.equals() 方法获取到值。(hashcode 相同不代表对象相同)所以申明作 final 的对象，并且采用合适的 equals() 和 hashCode() 方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的 hashcode，这能够提高多去对象的速度，使用String,Interger这样的包装类作为键是非常好的选择。

4. 什么情况下会出现循环链表

在多线程下，进行put操作会导致 HashMap 死循环，原因是 HashMap 的扩容方法 resize() 方法。由于扩容是新建一个数组，复制原数据到数组。由于数组下标挂有链表，所以需要复制链表，但是多线程操作有可能导致还行链表。复制链表过程如下：
以下模拟 2 个线程同时扩容。假设，当前 HashMap 的空间为2（临界值为1），hashCode 分别为 0 和 1，在散列地址 0 处有元素 A 和 B，这时需要添加C，经过hash运算，得到散列地址为1，这时候由于超过了临界值，需要 resize 进行扩容，在多线程条件下，会出现条件竞争，过程如下：

线程一：读取到当前的 HashMap 情况，在准备扩容时，线程二介入

线程二：读取 HashMap，进行扩容（头插法）

线程一：继续执行

注意：继续执行时，线程二的扩容并未完成，A.next 还没有被修改为 null

这个过程为，先将 A 复制到新的 hash 表中，然后接着复制 B 到链头（A 的前边：B.next=A），本来 B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将 B.next=A，所以，这里继续复制A，让 A.next=B，由此，环形链表出现：B.next=A; A.next=B

如何正确使用 HashMap 提高性能

在使用 HashMap 的时候指定其容量的大小，减少其 resize 的过程

JDK1.8 对 HashMap 做了哪些优化

jdk1.8在对hash冲突的key时，如果此bucket位置上的元素数量在8以下时，还是和原来一样使用链表来进行存储，这时寻址的时间复杂度为O(n),当元素数量超过8时，使用红黑树进行代替，这时寻址的时间复杂度为O(n)

HashMap 与 HashTable、ConcurrentHashMap 有什么区别

1. HashTable 的方法是同步的，在方法前都有 synchronized 来同步，HashMap 未经同步，所以在多线程场合需要手动同步
2. HashTable 不允许有 null 值，HashMap 允许
3. HashTable有一个contains(Object value)功能和containsValue(Object value)功能一样。
4. HashTable 使用 Enumeration 进行遍历，HashMap 使用 Iterator 进行遍历
5. HashTable 中 hash 数组默认大小是11，扩容方式是 old*2+1. HashMap中 hash 数组的默认大小是16，而且扩容一定是2的指数。
6. 哈希值的使用不同，HashTable直接使用对象的hashCode，而HashMap重新计算hash值
7. CurrentHashMap 也是线程安全的集合类，他和 HashTable 的主要区别是加锁的粒度以及如何加锁，ConcurrentHashMap 的加锁粒度要比 HashTable 更细一点。将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据的时候，其他段的数据也能被其他线程访问。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构

JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

实现线程安全的方式

在 jdk1.7 的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段（Segment），每一把锁只锁容器其中一部分数据，多线程访问容器里不同的数据段的数据，就不会存在锁竞争，提高并打访问效率。（默认分配16个Segment，比HashTable效率提高16倍）到了 jdk1.8 的时候已经摒弃了 Segment 的概念，而是直接使用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。（jdk1.6 之后对 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的HashMap，虽然 jdk1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。