2018年面试

java 面试总结

2017-08-27  本文已影响82人  Java旅行者

一、集合

1. ConcurrentHashMap 的实现原理

ConcurrentHashMap 在 JDK 1.6 和 1.7 都采用了相同的数据结构，即分段锁的技术来实现的。ConcurrentHashMap 内部有一个叫 Segment 的数组，里面存放的都是 Segment 对象。Segment 对象继承了 ReentrantLock，这样就使得每个段都有一把锁。 Segment 里面有一个被 volatile 修饰的 HashEntry 的数组。（在 ConcurrentHashMap 初始化的时候，创建了 Segment 数组，并初始化第一个元素。）

JDK 1.7

重要变量

static final class Segment<K,V> extends ReentrantLock implements Serializable {

    private static final long serialVersionUID = 2249069246763182397L;

    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;
}

static final class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K,V> next;

    HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

put 操作

  1. 判断 value 是否为 null， 如果 value 为 null 则抛出异常。

  2. 当用户调用 put 方法的时候，首先根据 key 的 hash 值找到具体的 Segment 在 table 中的位置。

  3. 如果这个位置上的 Segment 没有初始化，则进行初始化的操作。

  4. 最后委托给 Segment 的 put 方法。此方法中会根据计算出的 (tab.length - 1) & hash 的 index 定位到 HashEntry， 如果这个位置上的节点为null，则新建一个 HashEntry并返回 。如果不为 null，则遍历 HashEntry 的每一个节点，如果有相同的 key 存在则更新 value， 如果没有则新建一个 HashEntry 放入链表头部的位置。

  5. 如果 ConcurrentHashMap 内存放的元素个数超过了阈值，那么需要对其进行扩容。整个操作都是加锁的。

get 操作

get 操作的时候没有对 ConcurrentHashMap 进行上锁，

  1. 根据 key 的 hash 值计算出在哪个 Segment 上，再根据 hash 值计算出在哪个 HashEntry 上

  2. 然后遍历 HashEntry 的所有节点，如果找到 key，那么就返回对应的 value，如果 key 没有找到，就返回 null。

remove 操作

  1. 根据 key 的 hash 值找到在哪个 Segment 上

  2. 然后调用 Segment 的 remove 方法，根据 int index = (tab.length - 1) & hash; 计算出 index 并找到对应的 HashEntry

  3. 遍历 HashEntry 的所有节点，找到相同的 key（调用 key 的 equals 和 hashCode 方法）并删除，并且返回 value。

扩容操作（具体步骤还没找到）

ConcurrentHashMap不会增加Segment的数量，而只会增加Segment中链表数组的容量大小，这样的好处是扩容过程不需要对整个ConcurrentHashMap做rehash，而只需要对Segment里面的元素做一次 resize 就可以了。

整个步骤如下：

  1. 创建一个大小为原来 HashEntry 两倍大小的数组，根据 hash 算法重新将老 table 中的元素放入到新 table 中去。

这里的重点就是：

首先找到一个lastRun，lastRun之后的元素和lastRun是在同一个桶中，所以后面的不需要进行变动。然后对开始到lastRun部分的元素，重新计算下设置到newTable中，每次都是将当前元素作为newTable的首元素，之前老的链表作为该首元素的next部分。

JDK 1.8

ConcurrentHashMap 在 JDK 1.8 中进行了大幅度的改进。取消了 Segment 分段锁的概念。采用了数组 + 链表 + 红黑树的数据结构实现。内部存放了一个 Node<K,V>[] table 的 table。 ConcurrentHashMap 在初始化的时候只是设置了一些变量值，并没有对整个 table 进行初始化，初始化的动作被放入到了第一次 put 元素的时候。

一些重要的变量

/**
 * races. Updated via CAS.
 * 记录容器的容量大小，通过CAS更新
 */
private transient volatile long baseCount;

/**
 * 这个sizeCtl是volatile的，那么他是线程可见的，一个思考:它是所有修改都在CAS中进行，但是sizeCtl为什么不设计成LongAdder(jdk8出现的)类型呢？
 * 或者设计成AtomicLong(在高并发的情况下比LongAdder低效)，这样就能减少自己操作CAS了。
 *
 * 来看下注释，当sizeCtl小于0说明有多个线程正则等待扩容结果，参考transfer函数
 *
 * sizeCtl等于0是默认值，大于0是扩容的阀值
 */
private transient volatile int sizeCtl;

/**
 *  自旋锁 （锁定通过 CAS） 在调整大小和/或创建 CounterCells 时使用。 在CounterCell类更新value中会使用，功能类似显示锁和内置锁，性能更好
 *  在Striped64类也有应用
 */
private transient volatile int cellsBusy;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    
    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
}

sizeCtl 变量

控制标识符，用来控制table初始化和扩容操作的，在不同的地方有不同的用途，其值也不同，所代表的含义也不同

put 操作

  1. 首先判断 key 和 value 是否为 null， 如果为 null 则抛出异常。

  2. 然后在判断 table 是否初始化，如果没有初始化则通过 CAS 操作将 sizeCtl 的值设置为 -1，并执行 table 的初始化操作。

  3. 根据 key 的 hash 定位到 key 所在 table 的位置，如果这个位置上没有元素，则直接插入元素后返回。

  4. 如果当前节点的 hash 值为 -1，说明当前的节点是 forwardingNode 节点，表示 table 正在扩容，当前线程需要帮助一起扩容。（上面的过程走完之后，说明当前的节点上有元素，需要对当前节点加锁然后操作）。

  5. 如果当前节点的 hash 值大于等于 0，说明是一个链表结构，则遍历链表，如果存在当前 key 节点则替换 value，否则插入到链表尾部。

  6. 如果 f 是 TreeBin 类型节点，则按照红黑树的方法更新或者增加节点。

  7. 若链表长度 > TREEIFY_THRESHOLD(默认是8)，则将链表转换为红黑树结构（并不是直接转的，还需要进一步判断，具体的在treeifyBin方法中）。

  8. 最后调用 addCount 方法，将 ConcurrentHashMap 的 size + 1，并判断是否需要执行扩容操作，整个 put 过程结束。

get 操作

get 操作的时候没有上锁，如果整个table 为空，则返回null，否则根据 key 的 hash 值找到 table 的 index 位置，然后根据链表或者树形方式找到相对应的节点，返回其 value 值。

remove 操作

源码最后调用的是 replaceNode() 方法。具体没有详细看。

红黑树转换

1. 什么时候转换?

链表的元素个数达到了阈值 8 ，则会调用 treeifyBin 方法把链表转换成红黑树，不过在结构转换之前，会对数组长度进行判断。如果数组长度n小于阈值 MIN_TREEIFY_CAPACITY ，默认是64，则会调用 tryPresize 方法把数组长度扩大到原来的两倍，并触发 transfer 方法，重新调整节点的位置。

扩容操作

http://www.jianshu.com/p/487d00afe6ca

整个扩容操作分为两步：

  1. 构建一个nextTable，其大小为原来大小的两倍，这个步骤是在单线程环境下完成的。

  2. 将原来table里面的内容复制到nextTable中，这个步骤是允许多线程操作的，所以性能得到提升，减少了扩容的时间消耗。

并发扩容的具体步骤如下：

  1. 为每个内核分任务，并保证其不小于16

  2. 检查nextTable是否为null，如果是，则初始化 nextTable，使其容量为 table 的两倍。然后死循环遍历节点，直到finished。节点从 table 复制到 nextTable 中，支持并发，思路如下：

  3. 如果节点 f 为 null，则插入 ForwardingNode（采用 Unsafe.compareAndSwapObject 方法实现），这个是触发并发扩容的关键

  4. 如果 f 为链表的头节点（fh >= 0）,则先构造一个反序链表，然后把他们分别放在nextTable的 i 和 i + n位置，并将 ForwardingNode 插入原节点位置，代表已经处理过了

  5. 如果 f 为 TreeBin 节点，同样也是构造一个反序链表 ，==同时需要判断是否需要进行 unTreeify() 操作==，并把处理的结果分别插入到 nextTable 的 i 和 i+n 位置，并插入 ForwardingNode 节点

  6. 所有节点复制完成后，则将 table 指向 nextTable，同时更新 sizeCtl = nextTable 的 0.75 倍，完成扩容过程。

在多线程环境下，ConcurrentHashMap 用两点来保证正确性：ForwardingNode 和 synchronized。当一个线程遍历到的节点如果是 ForwardingNode，则继续往后遍历，如果不是，则将该节点加锁，防止其他线程进入，完成后设置 ForwardingNode 节点，以便要其他线程可以看到该节点已经处理过了，如此交叉进行，高效而又安全。

更多关于 ConcurrentHashMap 的问题在这里罗列

  1. 为什么 ConcurrentHashMap 的 table 大小是 2 的次幂?

    参见扩容机制的描述。

  1. ConcurrentHashMap JDK 8 在什么样的情况下会扩容?

    (1) 当前容量超过阈值时扩容

    (2) 当链表中元素个数超过默认设定（8个），当数组的大小还未超过64的时候，此时进行数组的扩容，如果超过则将链表转化成红黑树。

  1. ConcurrentHashMap JDK 8 如何实现线程安全?

    使用 CAS + Synchronized 来保证并发更新的安全。

  1. HashMap 的 hash 算法

    参见扩容机制的描述。

  2. ConcurrentHashMap 的弱一致性

    (1) 在 JDK 1.6 的时候，一个线程在 ConcurrentHashMap 里 put 元素时写 count，另一个线程 get 数据的时候不会得到最新的实时数据。这是因为源码中 put 操作的写 new HashEntry 和 get 操作的 getFirst() 存在 happened-before 关系。具体可以查看笔记。

    (2) 貌似在 JDK 1.7 的时候也存在同样的问题。

2. HashMap 实现原理

JDK 1.7

HashMap 在 JDK 7 中的数据结构是数组 + 链表的实现。 HashMap 中存储了一个 Entry[] 类型的数组，里面存储了 Entry 对象。Entry 对象的结构如下：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
}

put

  1. 当调用 put 方法的时候，会根据 key 的 hash 值定位到 key 要存到 table 的哪个 index 上

  2. 如果 key 为 null，那么就 put 到链表的头结点上。

  3. 如果 key 不为 null，那么遍历 index 上的链表，如果存在相同的 key，那么就更新 value。

  4. 如果不存在相同的 key，那么将 key 存到链表的头结点中。

get

  1. 根据 key 的 hash 值计算出 key 在 table 的哪个 index 上。遍历 index 上的链表，找到相同的 key，并返回 value。

  2. 如果 key 不存在则返回 null。

扩容

什么时候扩容?

当 HashMap 内的容量数超过了阈值（默认 12 个）的时候会触发扩容。整个扩容过程如下：

  1. 新建一个比原来数组两倍大的新数组。

  2. 重算 key 的 hash 值来得到在新数组的位置，并将 key 放入新数组中。

死循环问题

主要是多线程同时put时，如果同时触发了rehash操作，会导致HashMap中的链表中出现循环节点，进而使得后面get的时候，会死循环。而且还会丢失元素。

主要重现过程可以看： http://blog.csdn.net/xuefeng0707/article/details/40797085

JDK 1.8

在 JDK 1.8 中， HashMap 重新设计了实现。放弃 1.7 中的数组 + 链表的存储结构，改为了数组 + 链表 + 红黑树的实现。

put

  1. 根据 key 的 hash 值，计算出 table 中的 index。

  2. 如果 index 上没有元素，那么直接插入元素。

  3. 如果 index 上有元素的话，并且是链表结构的话，就遍历链表，判断是否有相同的 key 存在，如果存在则替换 value，如果不存在则新建 Node ==放入链表尾部==。同时判断当前链表是否过长，如果超过 TREEIFY_THRESHOLD 的话，则需要将链表转换成红黑树。

  4. 如果 index 上的节点是 TreeNode 类型的话，则用红黑树的方式添加元素。

  5. 最后判断 HashMap 中的元素是否超过了阈值，如果超过了需要进行 resize 扩容。

get

  1. 根据 key 的 hash 值定位到 table 中的 index。

  2. 如果 index 上没有元素，则返回 null。

  3. 如果 index 上有元素，那么根据节点类型的不同，调用链表或红黑树的方式获取 value。

扩容

在 JDK 1.8 的实现中，优化了高位运算的算法，通过 hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

image

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

image

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图

image

有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。

红黑树转换

如果链表上的元素大于 8 个，那么需要转换成红黑树。不过在结构转换之前，会对数组长度进行判断。如果数组长度n小于阈值 MIN_TREEIFY_CAPACITY ，默认是64，则会调用 tryPresize 方法把数组长度扩大到原来的两倍，并触发 transfer 方法，重新调整节点的位置。

二、多线程

上一篇下一篇

猜你喜欢

热点阅读