Java集合面试题汇总篇 (8)

① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。

② 创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂次方作为哈希表的大小,后面会介绍到为什么是2的幂次方。

底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。

HashMap的迭代器(Iterator)是fail-fast迭代器,但是 Hashtable的迭代器(enumerator)不是 fail-fast的。如果有其它线程对HashMap进行的添加/删除元素,将会抛出ConcurrentModificationException,但迭代器本身的remove方法移除元素则不会抛出异常。这条同样也是 Enumeration 和 Iterator 的区别。

ConcurrentHashMap

HashMap在多线程情况下,在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。

Hashtable,是线程安全的,它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table,这就意味着所有的线程都在竞争一把锁,在多线程的环境下,它是安全的,但是无疑是效率低下的。

JDK1.7 实现

Hashtable 容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有访问 Hashtable 的线程都必须竞争同一把锁,那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,,这就是ConcurrentHashMap所使用的锁分段技术。

在 JDK1.7版本中,ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成。Segment 数组的意义就是将一个大的 table 分割成多个小的 table 来进行加锁。每一个 Segment 元素存储的是 HashEntry数组+链表,这个和 HashMap 的数据存储结构一样。

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。
HashEntry 用来封装映射表的键值对,Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。每个 Segment 守护着一个 HashEntry 数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得它对应的 Segment 锁。

Segment 类

Segment 类继承于 ReentrantLock 类,从而使得 Segment 对象能充当可重入锁的角色。一个 Segment 就是一个子哈希表,Segment 里维护了一个 HashEntry 数组,并发环境下,对于不同 Segment 的数据进行操作是不用考虑锁竞争的。

从源码可以看到,Segment 内部类和我们上边看到的 HashMap 很相似。也有负载因子,阈值等各种属性。

static final class Segment<K,V> extends ReentrantLock implements Serializable { static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1; transient volatile HashEntry<K,V>[] table; transient int count; transient int modCount; //记录修改次数 transient int threshold; final float loadFactor; Segment(float lf, int threshold, HashEntry<K,V>[] tab) { this.loadFactor = lf; this.threshold = threshold; this.table = tab; } //put 方法会有加锁操作, final V put(K key, int hash, V value, boolean onlyIfAbsent) { HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); // ... } @SuppressWarnings("unchecked") private void rehash(HashEntry<K,V> node) { // ... } private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) { //... } private void scanAndLock(Object key, int hash) { //... } final V remove(Object key, int hash, Object value) { //... } final boolean replace(K key, int hash, V oldValue, V newValue) { //... } final V replace(K key, int hash, V value) { //... } final void clear() { //... } } HashEntry 类

HashEntry 是目前我们最小的逻辑处理单元。一个ConcurrentHashMap 维护一个 Segment 数组,一个Segment维护一个 HashEntry 数组。

static final class HashEntry<K,V> { final int hash; final K key; volatile V value; // value 为 volatie 类型,保证可见 volatile HashEntry<K,V> next; //... } ConcurrentHashMap 类

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyssfz.html