关于java:Java集合面试题2021最新版

本文收录于《面试小抄》系列，Github 地址(可下载 pdf）：https://github.com/cosen1024/… 国内 Gitee(可下载 pdf）：https://gitee.com/cosen1024/J…

明天给大家带来了 Java 汇合的常考面试题，包含 Arraylist、LinkedList、HashMap、Hashtable、ConcurrentHashMap 等。

这是本期的 Java 汇合面试题目录，不会的快快查漏补缺~

1. 常见的汇合有哪些？

Java 汇合类次要由两个根接口 Collection 和Map派生进去的，Collection 派生出了三个子接口：List、Set、Queue（Java5 新增的队列），因而 Java 汇合大抵也可分成 List、Set、Queue、Map 四种接口体系。

留神：Collection 是一个接口，Collections 是一个工具类，Map 不是 Collection 的子接口。

Java 汇合框架图如下：

图中，List 代表了有序可反复汇合，可间接依据元素的索引来拜访；Set 代表无序不可反复汇合，只能依据元素自身来拜访；Queue 是队列汇合。

Map 代表的是存储 key-value 对的汇合，可依据元素的 key 来拜访 value。

上图中淡绿色背景笼罩的是汇合体系中罕用的实现类，别离是 ArrayList、LinkedList、ArrayQueue、HashSet、TreeSet、HashMap、TreeMap 等实现类。

2. 线程平安的汇合有哪些？线程不平安的呢？

线程平安的：

• Hashtable：比 HashMap 多了个线程平安。
• ConcurrentHashMap: 是一种高效然而线程平安的汇合。
• Vector：比 Arraylist 多了个同步化机制。
• Stack：栈，也是线程平安的，继承于 Vector。

线性不平安的：

• HashMap
• Arraylist
• LinkedList
• HashSet
• TreeSet
• TreeMap

3. Arraylist 与 LinkedList 异同点？

• 是否保障线程平安： ArrayList 和 LinkedList 都是不同步的，也就是不保障线程平安；
• 底层数据结构： Arraylist 底层应用的是 Object 数组；LinkedList 底层应用的是双向循环链表数据结构；
• 插入和删除是否受元素地位的影响： ArrayList 采纳数组存储，所以插入和删除元素的工夫复杂度受元素地位的影响。 比方：执行 add(E e) 办法的时候，ArrayList 会默认在将指定的元素追加到此列表的开端，这种状况工夫复杂度就是 O(1)。然而如果要在指定地位 i 插入和删除元素的话（add(int index, E element)）工夫复杂度就为 O(n-i)。因为在进行上述操作的时候汇合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作。LinkedList 采纳链表存储，所以插入，删除元素工夫复杂度不受元素地位的影响，都是近似 O（1）而数组为近似 O（n）。
• 是否反对疾速随机拜访： LinkedList 不反对高效的随机元素拜访，而 ArrayList 实现了 RandmoAccess 接口，所以有随机拜访性能。疾速随机拜访就是通过元素的序号疾速获取元素对象 (对应于get(int index) 办法)。
• 内存空间占用： ArrayList 的空 间节约次要体现在在 list 列表的结尾会预留肯定的容量空间，而 LinkedList 的空间破费则体现在它的每一个元素都须要耗费比 ArrayList 更多的空间（因为要寄存间接后继和间接前驱以及数据）。

4. ArrayList 与 Vector 区别？

• Vector 是线程平安的，ArrayList 不是线程平安的。其中，Vector 在关键性的办法后面都加了 synchronized 关键字，来保障线程的安全性。如果有多个线程会拜访到汇合，那最好是应用 Vector，因为不须要咱们本人再去思考和编写线程平安的代码。
• ArrayList 在底层数组不够用时在原来的根底上扩大 0.5 倍，Vector 是扩大 1 倍，这样 ArrayList 就有利于节约内存空间。

5. 说一说 ArrayList 的扩容机制？

ArrayList 扩容的实质就是计算出新的扩容数组的 size 后实例化，并将原有数组内容复制到新数组中去。默认状况下，新的容量会是原容量的 1.5 倍。

以 JDK1.8 为例阐明:

public boolean add(E e) {
    // 判断是否能够包容 e，若能，则间接增加在开端；若不能，则进行扩容，而后再把 e 增加在开端
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将 e 增加到数组开端
    elementData[size++] = e;
    return true;
    }

// 每次在 add()一个元素时，arraylist 都须要对这个 list 的容量进行一个判断。通过 ensureCapacityInternal()办法确保以后 ArrayList 保护的数组具备存储新元素的能力，通过解决之后将元素存储在数组 elementData 的尾部

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果传入的是个空数组则最小容量取默认容量与 minCapacity 之间的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
  private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 若 ArrayList 已有的存储能力满足最低存储要求，则返回 add 间接增加元素；如果最低要求的存储能力 >ArrayList 已有的存储能力，这就示意 ArrayList 的存储能力有余，因而须要调用 grow(); 办法进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


private void grow(int minCapacity) {
        // 获取 elementData 数组的内存空间长度
        int oldCapacity = elementData.length;
        // 扩容至原来的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 校验容量是否够
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 若预设值大于默认的最大值，查看是否溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 调用 Arrays.copyOf 办法将 elementData 数组指向新的内存空间
         // 并将 elementData 的数据复制到新的内存空间
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

6. Array 和 ArrayList 有什么区别？什么时候该应 Array 而不是 ArrayList 呢？

• Array 能够蕴含根本类型和对象类型，ArrayList 只能蕴含对象类型。
• Array 大小是固定的，ArrayList 的大小是动态变化的。
• ArrayList 提供了更多的办法和个性，比方：addAll()，removeAll()，iterator() 等等。

7. HashMap 的底层数据结构是什么？

在 JDK1.7 和 JDK1.8 中有所差异：

在 JDK1.7 中，由“数组 + 链表”组成，数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的。

在 JDK1.8 中，由“数组 + 链表 + 红黑树”组成。当链表过长，则会重大影响 HashMap 的性能，红黑树搜寻工夫复杂度是 O(logn)，而链表是蹩脚的 O(n)。因而，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到肯定条件会进行转换：

• 当链表超过 8 且数据总量超过 64 才会转红黑树。
• 将链表转换成红黑树前会判断，如果以后数组的长度小于 64，那么会抉择先进行数组扩容，而不是转换为红黑树，以缩小搜寻工夫。

8. 解决 hash 抵触的方法有哪些？HashMap 用的哪种？

解决 Hash 抵触办法有: 凋谢定址法、再哈希法、链地址法（拉链法）、建设公共溢出区。HashMap 中采纳的是 链地址法。

• 凋谢定址法也称为 再散列法 ，根本思维就是，如果p=H(key) 呈现抵触时，则以 p 为根底，再次 hash，p1=H(p), 如果 p1 再次出现抵触，则以 p1 为根底，以此类推，直到找到一个不抵触的哈希地址 pi。因而凋谢定址法所须要的 hash 表的长度要大于等于所须要寄存的元素，而且因为存在再次 hash，所以 只能在删除的节点上做标记，而不能真正删除节点。
• 再哈希法 (双重散列，多重散列)，提供多个不同的 hash 函数，当R1=H1(key1) 发生冲突时，再计算R2=H2(key1)，直到没有抵触为止。这样做尽管不易产生堆集，但减少了计算的工夫。
• 链地址法(拉链法)，将哈希值雷同的元素形成一个同义词的单链表, 并将单链表的头指针寄存在哈希表的第 i 个单元中，查找、插入和删除次要在同义词链表中进行。链表法实用于常常进行插入和删除的状况。
• 建设公共溢出区，将哈希表分为公共表和溢出表，当溢出产生时，将所有溢出数据对立放到溢出区。

9. 为什么在解决 hash 抵触的时候，不间接用红黑树？而抉择先用链表，再转红黑树?

因为红黑树须要进行左旋，右旋，变色这些操作来保持平衡，而单链表不须要。当元素小于 8 个的时候，此时做查问操作，链表构造曾经能保障查问性能。当元素大于 8 个的时候，红黑树搜寻工夫复杂度是 O(logn)，而链表是 O(n)，此时须要红黑树来放慢查问速度，然而新增节点的效率变慢了。

因而，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是节约性能的。

10. HashMap 默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8？

答复这个问题前，咱们来先看下 HashMap 的默认构造函数：

     int threshold;             // 包容键值对的最大值
     final float loadFactor;    // 负载因子
     int modCount;  
     int size;  

Node[] table 的初始化长度 length(默认值是 16)，Load factor 为负载因子(默认值是 0.75)，threshold 是 HashMap 所能包容键值对的最大值。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能包容的键值对个数越多。

默认的 loadFactor 是 0.75，0.75 是对空间和工夫效率的一个均衡抉择，个别不要批改，除非在工夫和空间比拟非凡的状况下：

• 如果内存空间很多而又对工夫效率要求很高，能够升高负载因子 Load factor 的值。
• 相同，如果内存空间缓和而对工夫效率要求不高，能够减少负载因子 loadFactor 的值，这个值能够大于 1。

咱们来追溯下作者在源码中的正文（JDK1.7）：

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

翻译过去大略的意思是：作为个别规定，默认负载因子（0.75）在工夫和空间老本上提供了很好的折衷。较高的值会升高空间开销，但进步查找老本（体现在大多数的 HashMap 类的操作，包含 get 和 put）。设置初始大小时，应该思考预计的 entry 数在 map 及其负载系数，并且尽量减少 rehash 操作的次数。如果初始容量大于最大条目数除以负载因子，rehash 操作将不会产生。

11. HashMap 中 key 的存储索引是怎么计算的？

首先依据 key 的值计算出 hashcode 的值，而后依据 hashcode 计算出 hash 值，最初通过 hash&（length-1）计算失去存储的地位。看看源码的实现：

// jdk1.7
办法一：static int hash(int h) {
    int h = hashSeed;
        if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);
        }

    h ^= k.hashCode(); // 为第一步：取 hashCode 值
    h ^= (h >>> 20) ^ (h >>> 12); 
    return h ^ (h >>> 7) ^ (h >>> 4);
}
办法二：static int indexFor(int h, int length) {  //jdk1.7 的源码，jdk1.8 没有这个办法，但实现原理一样
     return h & (length-1);  // 第三步：取模运算
}

// jdk1.8
static final int hash(Object key) {   
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    /* 
     h = key.hashCode() 为第一步：取 hashCode 值
     h ^ (h >>> 16)  为第二步：高位参加运算
    */
}

这里的 Hash 算法实质上就是三步：取 key 的 hashCode 值、依据 hashcode 计算出 hash 值、通过取模计算下标。其中，JDK1.7 和 1.8 的不同之处，就在于第二步。咱们来看下具体过程，以 JDK1.8 为例，n 为 table 的长度。

12. HashMap 的 put 办法流程？

以 JDK1.8 为例，简要流程如下：

1. 首先依据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
2. 如果数组是空的，则调用 resize 进行初始化；
3. 如果没有哈希抵触间接放在对应的数组下标里；
4. 如果抵触了，且 key 曾经存在，就笼罩掉 value；
5. 如果抵触后，发现该节点是红黑树，就将这个节点挂在树上；

6. 如果抵触后是链表，判断该链表是否大于 8，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个构造转换为红黑树；否则，链表插入键值对，若 key 存在，就笼罩掉 value。

13. HashMap 的扩容形式？

HashMap 在容量超过负载因子所定义的容量之后，就会扩容。Java 里的数组是无奈主动扩容的，办法是将 HashMap 的大小扩充为原来数组的两倍，并将原来的对象放入新的数组中。

那扩容的具体步骤是什么？让咱们看看源码。

先来看下 JDK1.7 的代码

void resize(int newCapacity) {   // 传入新的容量
        Entry[] oldTable = table;    // 援用扩容前的 Entry 数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {// 扩容前的数组大小如果曾经达到最大 (2^30) 了
            threshold = Integer.MAX_VALUE; // 批改阈值为 int 的最大值(2^31-1)，这样当前就不会扩容了
            return;
        }

        Entry[] newTable = new Entry[newCapacity];  // 初始化一个新的 Entry 数组
        transfer(newTable);                         //！！将数据转移到新的 Entry 数组里
        table = newTable;                           //HashMap 的 table 属性援用新的 Entry 数组
        threshold = (int)(newCapacity * loadFactor);// 批改阈值
    }

这里就是应用一个容量更大的数组来代替已有的容量小的数组，transfer()办法将原有 Entry 数组的元素拷贝到新的 Entry 数组里。

void transfer(Entry[] newTable) {Entry[] src = table;                   //src 援用了旧的 Entry 数组
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) { // 遍历旧的 Entry 数组
            Entry<K,V> e = src[j];             // 获得旧 Entry 数组的每个元素
            if (e != null) {src[j] = null;// 开释旧 Entry 数组的对象援用（for 循环后，旧的 Entry 数组不再援用任何对象）do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); //！！从新计算每个元素在数组中的地位
                    e.next = newTable[i]; // 标记[1]
                    newTable[i] = e;      // 将元素放在数组上
                    e = next;             // 拜访下一个 Entry 链上的元素
                } while (e != null);
            }
        }
    }

newTable[i] 的援用赋给了 e.next，也就是应用了单链表的头插入方式，同一地位上新元素总会被放在链表的头部地位；这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果产生了 hash 抵触的话）。

JDK1.8 做了两处优化

1. resize 之后，元素的地位在原来的地位，或者原来的地位 +oldCap (原来哈希表的长度）。不须要像 JDK1.7 的实现那样从新计算 hash，只须要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 + oldCap”。这个设计十分的奇妙，省去了从新计算 hash 值的工夫。

   如下图所示，n 为 table 的长度，图（a）示意扩容前的 key1 和 key2 两种 key 确定索引地位的示例，图（b）示意扩容后 key1 和 key2 两种 key 确定索引地位的示例，其中 hash1 是 key1 对应的哈希与高位运算后果。

元素在从新计算 hash 之后，因为 n 变为 2 倍，那么 n-1 的 mask 范畴在高位多 1 bit(红色)，因而新的 index 就会产生这样的变动：

2. JDK1.7 中 rehash 的时候，旧链表迁徙新链表的时候，如果在新表的数组索引地位雷同，则链表元素会倒置（头插法）。JDK1.8 不会倒置，应用尾插法。

14. 个别用什么作为 HashMap 的 key?

个别用 Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为罕用。

• 因为字符串是不可变的，所以在它创立的时候 hashcode 就被缓存了，不须要从新计算。这就是 HashMap 中的键往往都应用字符串的起因。
• 因为获取对象的时候要用到 equals() 和 hashCode() 办法，那么键对象正确的重写这两个办法是十分重要的, 这些类曾经很标准的重写了 hashCode() 以及 equals() 办法。

15. HashMap 为什么线程不平安？

• 多线程下扩容死循环。JDK1.7 中的 HashMap 应用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的呈现，造成死循环。因而，JDK1.8 应用尾插法插入元素，在扩容时会放弃链表元素本来的程序，不会呈现环形链表的问题。
• 多线程的 put 可能导致元素的失落。多线程同时执行 put 操作，如果计算出来的索引地位是雷同的，那会造成前一个 key 被后一个 key 笼罩，从而导致元素的失落。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
• put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。此问题在 JDK 1.7 和 JDK 1.8 中都存在。

具体分析可见我的这篇文章：面试官：HashMap 为什么线程不平安？

16. ConcurrentHashMap 的实现原理是什么？

ConcurrentHashMap 在 JDK1.7 和 JDK1.8 的实现形式是不同的。

先来看下 JDK1.7

JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组构造和 HashEntry 数组构造组成，即 ConcurrentHashMap 把哈希桶切分成小数组（Segment），每个小数组有 n 个 HashEntry 组成。

其中，Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，表演锁的角色；HashEntry 用于存储键值对数据。

首先将数据分为一段一段的存储，而后给每一段数据配一把锁，当一个线程占用锁拜访其中一个段数据时，其余段的数据也能被其余线程拜访，可能实现真正的并发拜访。

再来看下 JDK1.8

在数据结构上，JDK1.8 中的 ConcurrentHashMap 抉择了与 HashMap 雷同的 数组 + 链表 + 红黑树 构造；在锁的实现上，摈弃了原有的 Segment 分段锁，采纳 CAS + synchronized 实现更加低粒度的锁。

将锁的级别管制在了更细粒度的哈希桶元素级别，也就是说只须要锁住这个链表头结点（红黑树的根节点），就不会影响其余的哈希桶元素的读写，大大提高了并发度。

17. ConcurrentHashMap 的 put 办法执行逻辑是什么？

先来看 JDK1.7

首先，会尝试获取锁，如果获取失败，利用自旋获取锁；如果自旋重试的次数超过 64 次，则改为阻塞获取锁。

获取到锁后：

1. 将以后 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
2. 遍历该 HashEntry，如果不为空则判断传入的 key 和以后遍历的 key 是否相等，相等则笼罩旧的 value。
3. 不为空则须要新建一个 HashEntry 并退出到 Segment 中，同时会先判断是否须要扩容。
4. 开释 Segment 的锁。

再来看 JDK1.8

大抵能够分为以下步骤：

1. 依据 key 计算出 hash 值。
2. 判断是否须要进行初始化。

3. 定位到 Node，拿到首节点 f，判断首节点 f：

   • 如果为 null，则通过 cas 的形式尝试增加。
   • 如果为 f.hash = MOVED = -1，阐明其余线程在扩容，参加一起扩容。
   • 如果都不满足，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入。
4. 当在链表长度达到 8 的时候，数组扩容或者将链表转换为红黑树。

源码剖析可看这篇文章：面试 ConcurrentHashMap，看这一篇就够了！

18. ConcurrentHashMap 的 get 办法是否要加锁，为什么？

get 办法不须要加锁。因为 Node 的元素 val 和指针 next 是用 volatile 润饰的，在多线程环境下线程 A 批改结点的 val 或者新增节点的时候是对线程 B 可见的。

这也是它比其余并发汇合比方 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 平安效率高的起因之一。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    // 能够看到这些都用了 volatile 润饰
    volatile V val;
    volatile Node<K,V> next;
}

19. get 办法不须要加锁与 volatile 润饰的哈希桶无关吗？

没有关系。哈希桶 table 用 volatile 润饰次要是保障在数组扩容的时候保障可见性。

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

    // 存放数据的桶
    transient volatile HashEntry<K,V>[] table;

20. ConcurrentHashMap 不反对 key 或者 value 为 null 的起因？

咱们先来说 value 为什么不能为 null，因为 ConcurrentHashMap 是用于多线程的，如果 map.get(key) 失去了 null，无奈判断，是映射的 value 是 null，还是没有找到对应的 key 而为 null，这就有了二义性。

而用于单线程状态的 HashMap 却能够用containsKey(key) 去判断到底是否蕴含了这个 null。

咱们用 反证法 来推理：

假如 ConcurrentHashMap 容许寄存值为 null 的 value，这时有 A、B 两个线程，线程 A 调用 ConcurrentHashMap .get(key)办法，返回为 null，咱们不晓得这个 null 是没有映射的 null，还是存的值就是 null。

假如此时，返回为 null 的真实情况是没有找到对应的 key。那么，咱们能够用 ConcurrentHashMap .containsKey(key)来验证咱们的假如是否成立，咱们冀望的后果是返回 false。

然而在咱们调用 ConcurrentHashMap .get(key)办法之后，containsKey 办法之前，线程 B 执行了 ConcurrentHashMap .put(key, null)的操作。那么咱们调用 containsKey 办法返回的就是 true 了，这就与咱们的假如的真实情况不合乎了，这就有了二义性。

至于 ConcurrentHashMap 中的 key 为什么也不能为 null 的问题，源码就是这样写的，哈哈。如果面试官不称心，就答复因为作者 Doug 不喜爱 null，所以在设计之初就不容许了 null 的 key 存在。想要深刻理解的小伙伴，能够看这篇文章这道面试题我真不知道面试官想要的答复是什么

21. ConcurrentHashMap 的并发度是多少？

在 JDK1.7 中，并发度默认是 16，这个值能够在构造函数中设置。如果本人设置了并发度，ConcurrentHashMap 会应用大于等于该值的最小的 2 的幂指数作为理论并发度，也就是比方你设置的值是 17，那么理论并发度是 32。

22. ConcurrentHashMap 迭代器是强一致性还是弱一致性？

与 HashMap 迭代器是强一致性不同，ConcurrentHashMap 迭代器是弱一致性。

ConcurrentHashMap 的迭代器创立后，就会依照哈希表构造遍历每个元素，但在遍历过程中，外部元素可能会发生变化，如果变动产生在已遍历过的局部，迭代器就不会反映进去，而如果变动产生在未遍历过的局部，迭代器就会发现并反映进去，这就是弱一致性。

这样迭代器线程能够应用原来老的数据，而写线程也能够并发的实现扭转，更重要的，这保障了多个线程并发执行的连续性和扩展性，是性能晋升的要害。想要深刻理解的小伙伴，能够看这篇文章为什么 ConcurrentHashMap 是弱统一的

23. JDK1.7 与 JDK1.8 中 ConcurrentHashMap 的区别？

• 数据结构：勾销了 Segment 分段锁的数据结构，取而代之的是数组 + 链表 + 红黑树的构造。
• 保障线程平安机制：JDK1.7 采纳 Segment 的分段锁机制实现线程平安，其中 segment 继承自 ReentrantLock。JDK1.8 采纳 CAS+Synchronized 保障线程平安。
• 锁的粒度：原来是对须要进行数据操作的 Segment 加锁，现调整为对每个数组元素加锁（Node）。
• 链表转化为红黑树: 定位结点的 hash 算法简化会带来弊病,Hash 抵触加剧, 因而在链表节点数量大于 8 时，会将链表转化为红黑树进行存储。
• 查问工夫复杂度：从原来的遍历链表 O(n)，变成遍历红黑树 O(logN)。

24. ConcurrentHashMap 和 Hashtable 的效率哪个更高？为什么？

ConcurrentHashMap 的效率要高于 Hashtable，因为 Hashtable 给整个哈希表加了一把大锁从而实现线程平安。而 ConcurrentHashMap 的锁粒度更低，在 JDK1.7 中采纳分段锁实现线程平安，在 JDK1.8 中采纳 CAS+Synchronized 实现线程平安。

25. 说一下 Hashtable 的锁机制 ?

Hashtable 是应用 Synchronized 来实现线程平安的，给整个哈希表加了一把大锁，多线程拜访时候，只有有一个线程拜访或操作该对象，那其余线程只能阻塞期待须要的锁被开释，在竞争强烈的多线程场景中性能就会十分差！

26. 多线程下平安的操作 map 还有其余办法吗？

还能够应用 Collections.synchronizedMap 办法，对办法进行加同步锁

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize

        SynchronizedMap(Map<K,V> m) {this.m = Objects.requireNon null (m);
            mutex = this;
        }

        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }
    // 省略局部代码
    }

如果传入的是 HashMap 对象，其实也是对 HashMap 做的办法做了一层包装，外面应用对象锁来保障多线程场景下，线程平安，实质也是对 HashMap 进行全表锁。在竞争强烈的多线程环境下性能仍然也十分差，不举荐应用！

27. HashSet 和 HashMap 区别?

补充 HashSet 的实现：HashSet 的底层其实就是 HashMap，只不过咱们HashSet 是实现了 Set 接口并且把数据作为 K 值，而 V 值始终应用一个雷同的虚值来保留。如源码所示：

public boolean add(E e) {return map.put(e, PRESENT)==null;// 调用 HashMap 的 put 办法,PRESENT 是一个至始至终都雷同的虚值
}

因为 HashMap 的 K 值自身就不容许反复，并且在 HashMap 中如果 K / V 雷同时，会用新的 V 笼罩掉旧的 V，而后返回旧的 V，那么在 HashSet 中执行这一句话始终会返回一个 false，导致插入失败，这样就保障了数据的不可重复性。

28. Collection 框架中实现比拟要怎么做？

第一种，实体类实现 Comparable 接口，并实现 compareTo(T t) 办法，称为外部比拟器。

第二种，创立一个内部比拟器，这个内部比拟器要实现 Comparator 接口的 compare(T t1, T t2)办法。

29. Iterator 和 ListIterator 有什么区别？

• 遍历。应用 Iterator，能够遍历所有汇合，如 Map，List，Set；但只能在向前方向上遍历汇合中的元素。

应用 ListIterator，只能遍历 List 实现的对象，但能够向前和向后遍历汇合中的元素。

• 增加元素。Iterator 无奈向汇合中增加元素；而，ListIteror 能够向汇合增加元素。
• 批改元素。Iterator 无奈批改汇合中的元素；而，ListIterator 能够应用 set()批改汇合中的元素。
• 索引。Iterator 无奈获取汇合中元素的索引；而，应用 ListIterator，能够获取汇合中元素的索引。

30. 讲一讲疾速失败 (fail-fast) 和平安失败(fail-safe)

疾速失败（fail—fast）

• 在用迭代器遍历一个汇合对象时，如果遍历过程中对汇合对象的内容进行了批改（减少、删除、批改），则会抛出 Concurrent Modification Exception。
• 原理：迭代器在遍历时间接拜访汇合中的内容，并且在遍历过程中应用一个 modCount 变量。汇合在被遍历期间如果内容发生变化，就会扭转 modCount 的值。每当迭代器应用 hashNext()/next()遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异样，终止遍历。
• 留神：这里异样的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果汇合发生变化时批改 modCount 值刚好又设置为了 expectedmodCount 值，则异样不会抛出。因而，不能依赖于这个异样是否抛出而进行并发操作的编程，这个异样只倡议用于检测并发批改的 bug。
• 场景：java.util 包下的汇合类都是疾速失败的，不能在多线程下产生并发批改（迭代过程中被批改），比方 HashMap、ArrayList 这些汇合类。

平安失败（fail—safe）

• 采纳平安失败机制的汇合容器，在遍历时不是间接在汇合内容上拜访的，而是先复制原有汇合内容，在拷贝的汇合上进行遍历。
• 原理：因为迭代时是对原汇合的拷贝进行遍历，所以在遍历过程中对原汇合所作的批改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。
• 毛病：基于拷贝内容的长处是防止了 Concurrent Modification Exception，但同样地，迭代器并不能拜访到批改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的汇合拷贝，在遍历期间原汇合产生的批改迭代器是不晓得的。
• 场景：java.util.concurrent 包下的容器都是平安失败，能够在多线程下并发应用，并发批改，比方：ConcurrentHashMap。

End

整顿不易，求个三连~ 心愿找工作的小伙伴都有称心的 offer

伟人的肩膀

https://juejin.cn/post/684490…

https://www.javazhiyin.com/71…

https://blog.csdn.net/qq_3178…

https://www.cnblogs.com/zeroi…
这里也举荐一个我收集的计算机书籍仓库，仓库目前有上百本经典 cs 电子书，看经典的书籍会更悟得深~

点此链接即可中转书单，计算机必看经典书籍（含 pdf 下载）

Github 也有相应仓库，https://github.com/cosen1024/…
欢送 star。