HashMap::getNode的流程是:
.1 首先会判断数组是否不等于null,或者数组的长度是否大于0，如果不满足,就说明HashMap里没有数据，直接返回null。
.2 通过 hash & (table.length - 1)获取该key对应的数据节点的hash槽;
.3 判断首节点是否为空, 为空则直接返回空;
.4 再判断首节点.key 是否和目标值相同, 相同则直接返回(首节点不用区分链表还是红黑树);
.5 首节点.next为空, 则直接返回空;
.6 首节点是树形节点, 则进入红黑树数的取值流程, 并返回结果;
.7 进入链表的取值流程, 并返回结果;

HashMap中JDK1.7与JDK1.8的区别

1、数据结构
JDK 1.7之前使用链表+数组；JDK1.8之后，使用链表+数组+红黑树；当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN），提高了效率）
2，插入方式
头插与尾插：JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法，那么他们为什么要这样做呢？因为JDK1.7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。
3，扩容
JDK 1.7是先扩容后插入，JDK 1.8则是先插入后扩容
4，hash运算
JDK 1.7是4次位运算+5次异或，JDK 1.8是1次位运算+1次异或

JDK1.7与1.8的区别

HashMap在并发编程中存在什么问题？

多线程扩容，引起的死循环（JDK1.7），在JDK1.8中已经解决

(2) 多线程put的时候可能导致元素丢失

(3) put非null元素后get出来的却是null

处理冲突的方法

1. 开放寻址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

 （1） di=1,2,3,…, m-1，称线性探测再散列；

 （2）di=1^2, (-1)^2, 22,(-2)2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;

 （3）di=伪随机数序列，称伪随机探测再散列。 ==

 2. 再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

 3. 链地址法(拉链法)

 4. 建立一个公共溢出区

为什么扩容是2的次幂?

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算

&运算速度快，至少比%取模运算块

能保证 索引值 肯定在 capacity 中，不会超出数组长度，并且如果不是2的n次幂的话，就会出现重复索引的问题

(n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n

为什么为什么采用hashcode的高16位和低16位异或能降低hash碰撞?

当数组的长度很短时，只有低位数的hashcode值能参与运算。而让高16位参与运算可以更好的均匀散列，减少碰撞，进一步降低hash冲突的几率。并且使得高16位和低16位的信息都被保留了。

而在这里采用异或运算而不采用& ，| 运算的原因是 异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值的二进制会向1靠拢，采用|运算计算出来的值的二进制会向0靠拢

hash函数如何实现？

hash函数是先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或操作；

这个也叫扰动函数，这么设计有二点原因：

一定要尽可能降低hash碰撞，越分散越好；

算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

resize运算的步骤

先要得到扩容后的容量和阈值

• 散列表未初始化：默认初始化或根据指定容量阈值进行初始化

• 已初始化：判断是否达到最大容量：1. 已达到最大容量，不扩容，将最大阈值设为int最大值；2. 未达到最大容量，正常扩容，

2.通过得到的容量和阈值初始化新的散列表

• 循环旧的散列表：1. 桶位null，跳过 2. 桶只有一个元素Node.next = null,重新hash计算index 3. 桶为链表，遍历链表并通过e.hash & oldCap将链表分为高低位放入新散列表中,低位链位置index不变，高位连为index+oldTable 4. 桶位红黑树，将红黑树拆分分高低位链表，链表长度小于等于6，直接放入新桶，否则重新生成树入桶

六、volitile和synchronized的关键字

sychronized更加轻量级的同步锁

在访问volatile 变量时不会执行加锁操作，因此也就不会使执行线程阻塞，因此volatile 变量是一种比sychronized 关键字更轻量级的同步机制。volatile 适合这种场景：一个变量被多个线程共享，线程直接给这个变量赋值。

volitile关键字：

Volitile关键字：保证内存可见性，禁止指令重排序

内存可见性问题：在多线程环境下，读和写发生在不同的线程中，可能会出现：读线程不能及时的读取到其他线程写入的最新的值，这就是所谓的可见性问题。

从硬件层面：CPU/内存/IO设备之间存在读取速度的差距和存储大小的差异；为了减小各类型设备之间的读取效率差异，增加CPU的处理效率；CPU层面增加了高速缓存，但是带了缓存一致性问题，

缓存执行问题的两种解决方案：

总线锁，当其中一个处理器要对共享内存进行操作的时候，在总线上发出一个LOCK#的信号，这个信号使得其他CPU无法通过总线来访问到共享内存中的数据，总线锁定把CPU和内存之间的通信锁住了，在锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁的开销比较大，这种机制显然是不合理的。

缓存锁，最好的办法是控制控制锁的保护粒度，我们只需要保证对于被多个CPU缓存的同一份数据是一致的就行。在P6架构的CPU后，引入了缓存锁，如果当前数据已经被CPU缓存了，并且是要写回到主内存中的，就可以采用缓存锁来解决问题。MESI有四种状态，E独占，M修改，S共享，I无效，根据MESI，CPU某核（比如CPU1）的缓存行（包含变量x）是M、S或E的时候，如果总线嗅探到了变量x被其他核(比如CPU1)执行了写操作(remote write)，那么CPU0的缓存行会置于无效I（无效），在CUP0后续对该变量的操作的嘶吼发现是I状态，就会去主存中同步最新的值。

Store Bufferes（写缓冲区）

通过内存屏障禁止指令重排序

X86的memory barrier指令包括lfence(读屏障) sfence(写屏障) mfence(全屏障)

Store Memory Barrier(写屏障) ，告诉处理器在写屏障之前的所有已经存储在存储缓存(storebufferes)中的数据同步到主内存，简单来说就是使得写屏障之前的指令的结果对屏障之后的读或者写是可见的

Load Memory Barrier(读屏障) ，处理器在读屏障之后的读操作,都在读屏障之后执行。配合写屏障，使得写屏障之前的内存更新对于读屏障之后的读操作是可见的

Full Memory Barrier(全屏障) ，确保屏障前的内存读写操作的结果提交到内存之后，再执行屏障后的读写操作

JMM层面：

经过上面的分析，我们已经知道了volatile变量可以通过缓存一致性协议保证每个线程都能获得最新值，即满足数据的“可见性”。

除了显示引用volatile关键字能够保证可见性以外，在Java中，还有很多的可见性保障的规则。

从JDK1.5开始，引入了一个happens-before的概念来阐述多个线程操作共享变量的可见性问题。所以

我们可以认为在JMM中，如果一个操作执行的结果需要对另一个操作课件，那么这两个操作必须要存在

happens-before关系。这两个操作可以是同一个线程，也可以是不同的线程