面试题总结 --HashMap、Volatile 相关

面试题总结--HashMap、Volatile 相关

HashMap 的相关面试题

HashMap 的底层数据结构

• JDK1.7 及之前是数组+链表

• JDK1.8 是数组+链表+红黑树

HashMap 的底层原理

Hash 算法

map.put(k,v);hash(k){h=k.hashCode() ^ h>>>16 }把 h 与 h 右移 16 位后的数做了一个异或的位运算，使 h 具备了高 16 位和低 16 的特征，让高 16 位 参与进寻址算法，降低了 hash 冲突的可能性。

Hash 寻址

(n-1) & hashCode() 在 n=2 的 n 次幂的情况下，（n-1）&hashCode()与取模寻址算法效果一样，并且效率更快。

Hash 冲突的机制

数组后面增加链表同一个位置的数组以链表的形式存在，链表长度超过 8 个以后，为了检索效率升级为红黑树（整体数组的容量大于 64 后也升级为红黑树）

HashMap 扩容机制

数组 2 倍扩容，重新寻址（reHash）hash&（n-1）判断二进制结果中是否多出一个 bit 的 1，如果没多，那么就是原来的 index，如果多了的话那么就是 index+oldCap，通过这个方式，就避免了 rehaash 的时候，对每一个 hash 进行取模操作，取模性能不高，位运算性能比较高。如果链表长度超过了 8 就自动转为黑红数查询时间复杂度从 On->Ologn

为什么使用红黑树

红黑树属于二叉查找树，有左小右大的特点，能够提升查询性能；但是普通的二叉树会有极端情况产生导致查询到 On，红黑树有很多条件限制能够自动重新找到平衡。

Volatile 相关面试题

volatile 硬件级别的原理图

JAVA 内存模型

重排序

JMM 对底层尽量减少约束，使其能够发挥自身优势。因此，在执行程序时，为了提高性能，编译器和处理器常常会对指令进行重排序。一般分为三种方式：

1. 编译器优化的重排序。编译器在不改变单线程程序语义的前提下，可以重新安排语句的执行顺序；

2. 指令级并行的重排序。现代处理器采用了指令级并行技术来将多条指令重叠执行。如果不存在数据依赖性，处理器可以改变语句对应机器指令的执行顺序；

3. 内存系统的重排序。由于处理器使用缓存和读/写缓冲区，这使得加载和存储操作看上去可能是在乱序执行的。

具体的定义为：如果两个操作访问同一个变量，且这两个操作有一个为写操作，此时这两个操作就存在数据依赖性这里就存在三种情况：1. 读后写；2.写后写；3. 写后读，者三种操作都是存在数据依赖性的，如果重排序会对最终执行结果会存在影响。编译器和处理器在重排序时，会遵守数据依赖性，编译器和处理器不会改变存在数据依赖性关系的两个操作的执行顺序

volatile 有序性

volatile 变量的所谓有序性也就是被声明为 volatile 的变量的临界区代码的执行是有顺序的，即禁止指令重排序。

happens-before 原则

程序顺序规则

一个线程中的每个操作，happens-before 于该线程中的任意后续操作。

监视器规则

对一个锁的解锁，happens-before 于随后对这个锁的加锁（相对于一个锁来说，解锁操作一定在加锁之后）

volatile 变量规则

对一个 volatile 变量域的鞋，happens-before 于任意后续对这个 volatile 域的读（volatile 修饰的属性，读操作一定发生在写操作之后）

传递性

如何 A happens-before B 且 B happens-before C，那么 A happens-before C （如果 A 在 B 之前发生过，B 在 C 之前发生过，那么 A 一定在 C 之前发生）

start 规则

如果线程 A 执行操作 ThreadB.start()（启动线程 B），那么 A 线程的 ThreadB.start()操作 happens-before 于线程 B 中的任意操作。

join 规则

如果线程 A 执行操作 ThreadB.join()并成功返回，那么线程 B 中的任意操作 happens-before 于线程 A 从 ThreadB.join()操作成功返回。

程序中断规则

对线程 interrupted()方法的调用先行于被中断线程的代码检测到中断时间的发生。

对象 finalize 规则

一个对象的初始化完成（构造函数执行结束）先行于发生它的 finalize()方法的开始。

原子性

这里 volatile 变量的原子性与 synchronized 的原子性是不同的，synchronized 的原子性是指只要声明为 synchronized 的方法或代码块儿在执行上就是原子操作的。而 volatile 是不修饰方法或代码块儿的，它用来修饰变量，对于单个 volatile 变量的读/写操作都具有原子性，但类似于 volatile++这种复合操作不具有原子性。所以 volatile 的原子性是受限制的。并且在多线程环境中，volatile 并不能保证原子性。

可见性

即当一个线程修改了声明为 volatile 变量的值，新值对于其他要读该变量的线程来说是立即可见的。而普通变量是不能做到这一点的，普通变量的值在线程间传递需要通过主内存来完成。

Lock 指令

volatile 两个原则：

1. volatile（底层 lock 指令）写时处理器会将缓存写回到主内存。

2. 一个处理器的缓存写回到内存会导致其他处理器的缓存失效。