JavaSE基础面试题-HashMap

HashMap、CurcurrentHashMap原理

HashMap

HashMap根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，所以HashMap具有很快的访问速度 但是遍历顺序却不是固定的

HashMap 最多只允许一条记录的健值为null,允许多条记录的值为null
HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据不一致
如果想保证线程安全，可以使用Collections的 synchronizedMap 方法使HashMap具有线程安全的能力或者使用ConcurrentHashMap
Java7 HashMap
HashMap 里面是一个数组，数组中每个元素是单向链表。如上图所示每个绿色的实体是嵌套类的实例，Entry包含四个属性（key、value、hash值、用于单向链表的next）

● capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
● loadFactor：负载因子，默认为 0.75。
● threshold：扩容的阈值，等于 capacity * loadFactor

Java8 HashMap

Java 8对HashMap 进行了修改。新增红黑树，结构由数组+链表+红黑树组成; 查询时，通过hash值可以快速定位数组下标，之后则需要顺着链表一个个比较下去才能找到具体值，时间复杂度取决于链表的长度O(n).
为了这部分开销，在Java8中，当链表中的元素超过8个后，会将链表自动转成红黑树，在这些位置查询时可以降低时间复杂度O(logN).

ConcurrentHashMap原理

Segment段

ConcurrentHashMap和HashMap思路差不多，但是因为它是并发操作，所以需要复杂一些。ConcurrentHashMap由一个个HashMap组成，Segment代表部分或者分段的意思，所以一般都称为分段锁

线程安全（Segment继承ReentrantLock加锁）

简单理解就是，ConcurrentHashMap 是?个 Segment 数组，Segment 通过继承ReentrantLock 来进?加锁，所以每次需要加锁的操作锁住的是?个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。

Java7 ConcurrentHashMap结构

并行度 （默认16）concurrencyLevel:并行级别、并发数、Segment数默认16，就是ConcurrentHashMap有16个Segment。所以理论上ConcurrentHashMap支持16线程并发写，只要他们操作在不同的Segment上这个值可以在初始化的时候设置为其他值，但是?旦初始化以后，它是不可以扩容的。再具体到每个 Segment 内部，每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全，所以处理起来比较麻烦。

Java8 ConcurrentHashMap也是引进了红黑树