文章单纯记录学习，答案不一定正确，大多从网上查阅，有错误望指正

一、HashMap底层数据结构以及扩容

HashMap的底层实现：JDK1.7是数组+链表；JDK1.8是数组+链表/红黑树

1. 扩容的条件：答：JDK1.7版：当要添加新Entry对象时发现（1）size达到threshold（阈值）（2）table[index]!=null时，两个条件同时满足会扩容

JDK1.8版：当要添加新Entry对象时发现（1）size达到threshold（阈值）（2）当table[index]下的结点个数达到8个但是table.length又没有达到64。两种情况满足其一都会导致数组扩容

而且数组一旦扩容，不管哪个版本，都会导致所有映射关系重新调整存储位置。

扩容：

2. put(key,value) -JDK1.7

（1）当第一次添加映射关系时，数组初始化为一个长度为16的HashMap$Entry的数组，这个HashMap$Entry类型是实现了java.util.Map.Entry接口

（2）特殊考虑：如果key为null，index直接是[0]

（3）在计算index之前，会对key的hashCode()值，做一个hash(key)再次哈希的运算，这样可以使得Entry对象更加散列的存储到table中

（4）计算index = table.length-1 & hash;

（5）如果table[index]下面，已经有映射关系的key与我要添加的新的映射关系的key相同了，会用新的value替换旧的value。

（6）如果没有相同的，会把新的映射关系添加到链表的头，原来table[index]下面的Entry对象连接到新的映射关系的next中。

（7）添加之前先判断if(size >= threshold  &&  table[index]!=null)如果该条件为true，会扩容

if(size >= threshold  &&  table[index]!=null){

①会扩容

②会重新计算key的hash

③会重新计算index

}

3.put(key,value) -JDK1.8

（1）当第一次添加映射关系时，数组初始化为一个长度为16的HashMap$Node的数组，这个HashMap$Node类型是实现了java.util. Map.Entry接口

（2）在计算index之前，会对key的hashCode()值，做一个hash(key)再次哈希的运算，这样可以使得Entry对象更加散列的存储到table中

> JDK1.8关于hash(key)方法的实现比JDK1.7要简洁， key.hashCode() ^ key.Code()>>16;（异或其高16位）

（3）计算index = table.length-1 & hash;

（4）如果table[index]下面，已经有映射关系的key与我要添加的新的映射关系的key相同了，会用新的value替换旧的value。

（5）如果没有相同的，

①table[index]链表的长度没有达到8个，会把新的映射关系添加到尾部

②table[index]链表的长度达到8个，但是table.length没有达到64，会先对table进行扩容，然后再添加

③table[index]链表的长度达到8个，并且table.length达到64，会先把该分支进行树化，结点的类型变为TreeNode，然后把链表转为一棵红黑树

④table[index]本来就已经是红黑树了，那么直接连接到树中，可能还会考虑考虑左旋右旋以保证树的平衡问题

（6）添加完成后判断if(size > threshold ){

①会扩容

②会重新计算key的hash

③会重新计算index

}

二、HashMap的各种参数

阈值 = size（数组大小）* loadFactory（加载因子）

初始化大小size为16，加载因子为0.75,JDK1.8链表长度为8，数组长度大于等于64，进行树化

（1）1. HashMap的负载因子是多少，为什么？

a) 0.75；

b) 因为定的太大，比如为1，就意味着数组的空位都需要填满，如果一直等到数组填满才扩容，虽然达到了最大的数组空间利用率，但会产生大量的哈希碰撞，同时产生更多的链表，显然不符合我们的要求；

c) 但如果设置的太小，比如0.3，这样一来保证了数组空间很充足，减少了哈希碰撞，这种情况下查询效率很高，但是消耗浪费了大量的空间。

d) 所以我们需要在时间和空间上做一个折中，选择最合适的负载因子以保证最优化，0.75。

2. HashMap的数组长度是2的指数次幂，为什么。

i. 通过tableSizeFor()方法让最高位1的后面全变为1，在让结果n+1，即得到了2的整数次幂。

ii. 因为添加元素时索引的下标可以通过取模运算获得，但是取模的效率低于乘法，所以要避免频繁的取模运算。有因为在我们HashMap中他要通过取模去定位我们的索引，并且hashmap是在不断的扩容的，数组一旦达到容量阈值时就需要进行扩容，那么扩容就意味着要进行数组元素的移动，每一次移动都要重新计算索引，这个过程中牵扯大量的元素移动，就需要频繁的取模运算，就会大大影响效率。

iii. 那么如果我们直接使用与运算，这个效率就远高与取模运算。利用与运算的就需要规定好数组的长度n，将n-1就会得到最高位为0，后面全1的二进制数，与任何数相与得到的范围在0~n-1。

iv. 结论：首先使用与运算来加快计算的效率，而要使用与运算，就需要数组长度n-1与hash值保证其在数组范围内，只有当数组的长度为2的指数次幂时，其计算出来的值才能和取模算法的值相等，并且保证能取到数组中的每一位，减少哈希碰撞，不浪费大量数组资源。

3. 为什么链表长度大于8时转成红黑树？

涉及泊松分布，以下是通过泊松分布计算出来的链表中元素个数和概率的对照表，链表中元素个数为8的概率非常小。

另外，红黑树平均查找长度是log(n),长度为8时，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，才有转换为树的必要。

三、并发下HashMap安全吗？为什么？

线程不安全，因为在多线程下，transfer方法将原table的值赋值给新的table，而transfer使用的是头插法，也就是链表的顺序会翻转，从而可能形成循环链表。

解决方法 ： https://blog.csdn.net/javageektech/article/details/103724851

第一种方法，使用Hashtable线程安全类；

第二种方法，使用Collections.synchronizedMap方法，对方法进行加同步锁；

第三种方法，使用并发包中的ConcurrentHashMap类；

前两种方法都是通过给加全表锁来保证安全，在竞争激烈的多线程环境下性能非常差，所以不推荐使用！

，因为hashMap 是数组 + 链表的数据结构，如果我们把数组进行分割多段，对每一段分别设计一把同步锁，这样在多线程访问不同段的数据时，就不会存在锁竞争了，这样是不是可以有效的提高性能？

四、ConcurrentHashMap底层实现及其安全机制

好文：https://blog.csdn.net/javageektech/article/details/103724851

Jdk1.7实现方式：ConcurrentHashMap类所采用的正是分段锁的思想，将HashMap 进行切割，把HashMap 中的哈希数组切分成小数组，每个小数组有n 个HashEntry 组成，其中小数组继承自ReentrantLock（可重入锁），这个小数组名叫Segment。

Jdk1.8实现方式：JDK1.8中 ConcurrentHashMap 类取消了Segment 分段锁，采用CAS+synchronized来保证并发安全，数据结构跟 jdk1.8 中 HashMap 结构类似，都是数组 + 链表（当链表长度大于 8 时，链表结构转为红黑二叉树）结构。

ConcurrentHashMap 中synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！

一、Jdk1.7源码分析：

1、 HashEntry和HashMap中的 Entry非常类似，唯一的区别就是其中的核心数据如value ，以及next都使用了volatile关键字修饰，保证了多线程环境下数据获取时的可见性！

2、 Segment 这个静态内部类继承了ReentrantLock类，ReentrantLock是一个可重入锁。

3、 理论上 ConcurrentHashMap 支持 concurrentLevel（通过 Segment 数组长度计算得来，默认为16） 个线程并发操作，每当一个线程独占一把锁访问 Segment 时，不会影响到其他的 Segment 操作，效率大大提升！

4、 Put方法的流程：

第一步，尝试获取对象锁，如果获取到返回 true，否则执行scanAndLockForPut方法，这个方法也是尝试获取对象锁；

第二步，获取到锁之后，类似 hashMap 的 put 方法，通过 key 计算所在 HashEntry 数组的下标；

第三步，获取到数组下标之后遍历链表内容，通过 key 和 hash 值判断是否 key 已存在，如果已经存在，通过标识符判断是否覆盖，默认覆盖；

第四步，如果不存在，采用头插法插入到 HashEntry 对象中；

第五步，最后操作完整之后，释放对象锁；

上述提到的scanAndLockForPut方法，操作也是分以下几步：

 当前线程尝试去获得锁，查找 key 是否已经存在，如果不存在，就创建一个 HashEntry 对象；

 如果重试次数大于最大次数，就调用lock()方法获取对象锁，如果依然没有获取到，当前线程就阻塞，直到获取之后退出循环；

 在这个过程中，key 可能被别的线程给插入，所以在第 5 步中，如果 HashEntry 存储内容发生变化，重置重试次数；

通过scanAndLockForPut()方法，当前线程就可以在即使获取不到segment锁的情况下，完成需要添加节点的实例化工作，当获取锁后，就可以直接将该节点插入链表即可。

这个方法还实现了类似于自旋锁的功能，循环式的判断对象锁是否能够被成功获取，直到获取到锁才会退出循环，防止执行 put 操作的线程频繁阻塞，这些优化都提升了 put 操作的性能。

5、 remove方法：

1) 先获取对象锁；

2) 计算 key 的 hash 值在 HashEntry[]中的角标；

3) 根据 index 角标获取 HashEntry 对象；

4) 循环遍历 HashEntry 对象，HashEntry 为单向链表结构；

5) 通过 key 和 hash 判断 key 是否存在，如果存在，就移除元素，并将需要移除的元素节点的下一个，向上移；

6) 最后就是释放对象锁，以便其他线程使用；

二、 jdk1.8源码分析

1、 JDK1.8 中的 ConcurrentHashMap 对节点Node类中的共享变量，和 JDK1.7 一样，使用volatile关键字，保证多线程操作时，变量的可见行！

2、 Put方法流程：

 首先会判断 key、value 是否为空，如果为空就抛异常！

 接着会判断容器数组是否为空，如果为空就初始化数组；

 进一步判断，要插入的元素f，在当前数组下标是否第一次插入，如果是就通过 CAS 方式插入；

 在接着判断f.hash == -1是否成立，如果成立，说明当前f是ForwardingNode节点，表示有其它线程正在扩容，则一起进行扩容操作；

 获得该位置下的锁，把新的Node节点按链表或红黑树的方式插入到合适的位置；

 节点插入完成之后，接着判断链表长度是否超过8，如果超过8个，就将链表转化为红黑树结构；

 最后，插入完成之后，进行扩容判断；

3、 initTable 初始化数组，当第一次插入时，内部容器数组为空，该方法进行初始化

其中sizeCtl 是一个对象属性，使用了 volatile 关键字修饰保证并发的可见性，默认为 0，当第一次执行 put 操作时，通过Unsafe.compareAndSwapInt()方法，俗称CAS，将 修改为 -1，有且只有一个线程能够修改成功，接着执行 table 初始化任务。

如果别的线程发现sizeCtl<0，意味着有另外的线程执行 CAS 操作成功，当前线程通过执行Thread.yield()让出 CPU 时间片等待 table 初始化完成。

4、 helpTransfer 帮组扩容，当f.hash =-1时，说明当前f是一个forwardingNode节点，意味着其他线程正在扩容，则一起进行扩容操作。

这个过程，操作步骤如下：

 第 1 步，对 table、node 节点、node 节点的 nextTable（新table）进行数据校验；

 第 2 步，根据数组的 length 得到一个标识符号；

 第 3 步，进一步校验 nextTab、tab、sizeCtl 值，如果 nextTab 没有被并发修改并且 tab 也没有被并发修改，同时 sizeCtl < 0，说明还在扩容；

 第 4 步，对 sizeCtl 参数值进行分析判断，如果不满足任何一个判断，将sizeCtl + 1, 增加了一个线程帮助其扩容;

5、 addCount扩容判断

这个过程，操作步骤如下：

 第 1 步，利用 CAS 将方法更新 baseCount 的值

 第 2 步，检查是否需要扩容，默认 check = 1，需要检查；

 第 3 步，如果满足扩容条件，判断当前是否正在扩容，如果是正在扩容就一起扩容；

 第 4 步，如果不在扩容，将 sizeCtl 更新为负数，并进行扩容处理；

总结：

为解决HashMap在多线程环境下操作不安全的问题，java为我们提供了ConcurrentHashMap类，保证了多线程下hashMap操作安全。

在jdk1.7中，ConcurrentHashMap采用了分段锁策略，将一个HashMap切割成Segment数组，而Segment存储n个HashEntry,类似HashMap，不同的是Segment继承自ReetrantLock(可重入锁)，在操作的时候给Segment赋予一个对象锁，从而保证了多线程环境下并发操作安全。

但是jdk1.7中，hashMap容易因为冲突链表长度过长，导致查询效率低。

在jdk1.8中，ConcurrentHashMap采用了jdk1.8中HashMap类似的存储结构（数组+链表/红黑树），但ConcurrentHashMap并没有采用分段锁的策略，而是在元素的节点上采用CAS+synchronized操作来保证并发的安全性。

五、 TreeMap和HashMap的区别

1、 HashMap中元素是无序的；TreeMap中所有元素都是有某一固定顺序的

2、 HashMap继承AbstractMap类，是基于hash表实现的；而TreeMap继承SortedMap类，是基于红黑树实现的。

3、 两者都是线程不安全的

4、 HashMap适用于Map插入、删除、定位元素；TreeMap适用于自然顺序或自定义顺序遍历键。

六、HashMap与Hashtable的区别

1、hashtable是线程安全的,即hashtable的方法都提供了同步机制，底层加了synchronized关键字；hashmap不是线程安全的,即不提供同步机制 

2、hashtable不允许插入空值,hashmap允许!

3、HashMap继承了AbstractMap，HashTable继承Dictionary抽象类，两者均实现Map接口。

4、HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。

5、HashMap扩容时是当前容量翻倍即:capacity*2，Hashtable扩容时是容量翻倍+1即:capacity*2+1。

6、HashMap和Hashtable的底层实现都是数组+链表结构实现。

7、两者计算hash的方法不同：

Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模：