HashMap区别
JDK7和JDK8中的HashMap底层数据结构有什么区别?
1
2
3
| JDK7:数组 + 链表
JDK8:数组 + 链表 + 红黑树
链表包括单向链表和双向链表，双线链表主要是为了链表操作方便，在插入、扩容链表转红黑树的过程中使用
|
JDK8中的HashMap为什么要使用红黑树？
1
2
3
4
5
6
7
| 当元素个数小于一个阈值时，链表在整体效率上要高于红黑树，当元素个数大于此阈值时，链表整体的查询效率要低于红黑树，此阈值在HashMap中为8。转换成红黑树可以平衡插入和查询效率。
链表查询效率：O(N)
链表插入效率：O(1)
红黑树查询效率：O(logN)
红黑树插入效率：O(logN)
|
JDK8中的HashMap什么时候将链表转化成红黑树？
1
2
| 当链表中的元素大于8，并且数组的长度大于等于64时，才会将链表转化成红黑树。
当数组的长度低于64时，通过扩容数组大小来缩小链表的长度。
|
JDK8中的HashMap的put方法的实现过程？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 1.根据Key生成HashCode
2.判断当前HashMap对象中的数组是否为空，如果为空则初始化数组
3.根据逻辑与运算，算出HashCode基于当前数组对应的数组下标i
4.判断数组的第i个位置的元素(tab[i])是否为空
a.如果为空，则将key,value封装为Node对象赋值给tab[i]
b.如果不为空：
I.如果put方法传入进来的key等于tab[i].key，那么存在相同的key
II.如果不等于tab[i].key，则:
1.如果tab[i]的类型是TreeNode，插入红黑树之前判断树中是否存在相同的key,然后Key和Value插入到红黑树中
2.如果tab[i]的类型不是TreeNode，则表示当前是个链表，遍历寻找相同的key，找不到则插入，然后判断是否Size大于8，大于则树化。
III.如果上诉步骤发现相同的key，则更新value值，返回oldValue
5.modCount++
6.HashMap的元素个数size + 1
7.如果size大于扩容阈值，则进行扩容
|
JDK8中HashMap的get方法的实现过程?
1
2
3
4
5
6
7
8
9
10
| 1.根据Key生成HashCode
2.如果数组为空，则直接返回空
3.如果数组不为空，则利用HashCode&（数组长度-1）计算Key所对应的数组下标i
4.如果数组的第i个位置上没有元素，则直接返回空
5.如果数组的第1个位置上的元素key等于get方法传进来的key，则返回该元素，并取该元素的value
6.如果不等于则判断该元素有没有下一个元素，如果没有，返回空
7.如果有则判断该元素的类型是链表节点还是红黑树节点
a.如果是链表则遍历链表
b.如果是红黑树则遍历红黑树
8.找到则返回元素，没找到则返回空
|
JDK7与JDK8中HashMap的不同点?
1
2
3
4
5
6
7
| 1.JDK8使用了红黑树
2.JDK7中链表插入使用的头插法，但是会造成循环链表CPU100%的问题，JDK8使用尾插法
3.JDK7的Hash算法比JDK8复杂，散列性更好能提高链表查询效率，而JDK8增加红黑树查询性能得到保障，所以简化了Hash算法
4.扩容的过程JDK7可能会对Key进行reHash(和Hash种子有关)，而JDK8=的Key没有reHash的过程
5.JDK8中的扩容条件和JDK7不同，在JDK7中，若tab[i]为空，则不进行扩容，而JDK8移除了该条件
6.JDK8增加了API：putIfAbsent(Key,Value)
7.扩容过程转移元素的逻辑不同，JDK7是一次转移一个元素，JDK8是算出尾部同一个位置的数组直接头结点迁移
|
ConcurrentHashMap区别
JDK7中的ConcurrentHashMap是怎么保证并发安全的？
1
2
3
4
5
6
7
8
9
10
| 利用 Unsafe操作 + ReentrantLock + 分段思想
Unsafe操作：
1.compareAndSwapObject : CAS方式修改对象的属性
2.putOrderedObject : 并发安全的给数组的某个位置赋值
3.getObjectVolatile ： 并发安全的获取数组某个位置的元素
分段思想是为了提高ConcurrentHashMap的并发量，分段越高则支持的最大并发量越高。
并发量根据concurrencyLevel参数指定，内部类Segment表示一个段。
每个Segment是一个小型的HashMap，Segment类继承ReentrantLock，所以自带重入锁，put方法时加锁，再插入值，然后解锁。
|
JDK7中的ConcurrentHashMap的底层原理?
1
2
3
4
5
6
7
8
| ConcurrentHashMap底层是由两层嵌套数组实现的：
1.ConcurrentHashMap对象中有一个属性segments，类型Segment[]
2.Segment对象中有一个属性table,类型HashEntry[]
当调用put方法时，根据Key计算出Segment[]数组下标，若为空，则初始化Segment对象，然后调用Segment对象的put方法.
Segment对象的put方法会先加锁，然后根据Key计算出HashEntry[]数组下标，并放到链表中。
加锁过程是通过CAS加锁，超过一定次数就会阻塞等待加锁。
|
JDK8中的ConcurrentHashMap是怎么保证并发安全的？
1
2
3
4
5
6
7
| 利用 Unsafe操作 + synchronized关键字
Unsave操作的使用和JDK7中的类似，主要负责并发安全的修改对象的属性活数组某个位置的值。
synchronized主要负责对tab[i]元素时进行加锁(该位置不为空)，若该位置为空，则采用CAS赋值tab[i]
tab[i]若是链表，则是链表头结点，若是红黑树，则是TreeBin对象。
JDK8中也有分段锁的思想，只不过JDK7中段数是可以控制的，而JDK8中针对数组的每一个位置(tab[i]元素)
|
JDK8中的ConcurrentHashMap的put方法的实现流程？
1
2
3
4
5
6
7
8
9
| 当向ConcurrentHashMap中put一个Key,Value时：
1.首先根据Key计算对应的数组下标，如果该位置没有元素，则通过CAS去赋值该位置
2.如果该位置有元素，则synchronized加锁
3.加锁成功后，判断该元素的类型
a.如果是链表，则将新节点添加到链表中
b.如果是红黑树，则将新节点添加到红黑树中
4.添加成功后，判断是否需要进行树化
5.addCount，并发安全地对ConcurrentHashMap元素个数 + 1(采用了LongAdder思想)，然后判断是否需要扩容
6.同时线程在put时如果发现当前ConcurrentHashMap正在进行扩容(tab[i]=FWD类型的对象)，则会去帮助扩容(并发扩容)。
|
JDK7和JDK8中，统计元素个数的实现逻辑有什么区别？
1
2
3
4
5
6
7
8
9
10
11
| JDK7:
1.第一次遍历累加Segment[]数组中的count属性
2.第二次遍历累加Segmeng[]数组中的count属性
3.如果在两次遍历过程中，结果不相等，则再遍历第三次累加，和第二次的结果对比，若相等则返回
4.若还是不等，则对Segment数组的上的所有元素加锁，然后计算
JDK8：
1.有一个baseCount的属性，供以CAS操作，并借鉴了LongAdder的设计思想
2.当baseCount在CAS竞争激烈时，使用CounterCell[]数组提供多个篮子进行资源分散
3.只要能对篮子中的值CAS成功后，即可
4.最终统计时，通过累加baseCount + CounterCell[] 得到结果。
|
JDK7和JDK8中，都支持多线程并发扩容吗？
1
2
3
4
5
| 都支持多线程扩容。
在JDK7中，扩容只是针对一个Segment对象中的HashEntry[]对象，所以能够达到多个线程同时扩容不同的Segment对象。
在JDK8中，每个线程迁移指定步长下标的元素，并发操作，达到多线程同时扩容一个tab数组。
JDK8的扩容性能更高，因为JDK8对任意一个线程都可以帮助扩容，而JDK7一个线程扩容一个Segment。
|