HashMap

HashMap是由数组和链表组合构成的数据结构，数组插入键值对，当遇到哈希值相等的节点时，即在该节点上形成链表。当新的节点插入链表时，java8之前是头插法，java8之后变为尾插法，主要防止哈希表扩容时，头插法易形成循环链表。

为何JAVA8之后改为尾插法？

首先来看看HashMap的扩容机制：

数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize.

一般有两个因素：Capacity–HashMap当前长度 LoadFactor–负载因子，默认值0.75f

即假设当前的容量大小为100，当存进第76个元素的时候，判断发现需要对哈希表进行resize。

具体扩容分为两步进行：

扩容：创建一个新的空数组，长度是原数组的2倍

rehash：遍历原数组，把所有节点重新Hash到新数组

为何要重新hash节点插入？直接复制更快？

因长度扩容之后，数组长度改变，Hash的规则也会随之改变

具体到为什么改为尾插法更好，使用头插法，容量为2的容器，某一节点上链表A-B-C在不同线程扩容插入A,B,C时，可能会形成B-A-B的回环，而使用尾插不会改变链表上的顺序，扩容时即不会出现链表成环问题。由此JAVA8不会出现像JAVA7在多线程操作哈希表时的死循环问题。

但这并不说明JAVA8可以任意把哈希表使用在多线程中，通过源码可知put/get方法均没有加同步锁，还是无法保证上一秒put的值，下一秒get还是原值，即线程安全还是无法保证。

哈希表的默认初始化长度是16 为经验值

为何重写equals方法要重写hashCode方法？

java中所有的对象都是继承于Object类，而Ojbect类中有两个比较两个对象是否相等的方法：equals和hashCode。

而哈希表找到数组同一节点上的链表时，使用equals比较链表上不同的值，也就是说我们一定要对hashCode进行重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

HashMap为何是线程不安全的

jdk1.7中HashMap

原因一：扩容造成死循环

在对哈希表进行扩容时，扩容函数将原数据转移到新表中，也会使用头插法，造成链表顺序翻转，多线程情况下这里是形成死循环的关键点。

原因二：扩容造成数据丢失

在扩容时，也可能造成数据丢失，数据指向自己，形成自环

jdk1.8中的HashMap

在jdk1.8中对HashMap进行了优化，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程的情况下仍然不安全。诸如不同线程的put相互覆盖的情况。

如何处理HashMap在线程不安全的情况

一般使用HashTable或者CurrentHashMap。

虽然Hashtable和HashMap相比是线程安全的，但其在对数据操作时都会上锁，存在效率问题。另外Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。

ConcurrentHashMap如何保证线程安全？

ConcurrentHashMap的存值put步骤如下：

1. 根据 key 计算出 hashcode 。

2. 判断是否需要进行初始化。

3. 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。

4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。

5. 如果都不满足，则利用 synchronized 锁写入数据。

6. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

ConcurrentHashMap的取值get步骤如下：

1. 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
2. 如果是红黑树那就按照树的方式获取值。
3. 就不满足那就按照链表的方式遍历获取值。

何为CAS，何为自旋？

CAS 是乐观锁的一种实现方式，为一种轻量级的锁，认为并发操作并不总会发生。

具体流程为：线程在读取数据时不进行加锁，在准备写回数据时，比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。

但其不能检测ABA问题，即A被某线程修改为B，再被某线程修改回A。乐观锁CAS无法检测。

synchronized底层原理

synchronized锁升级策略