4.1.2 银行技术面---编程语言类（Java集合）

本文章将收录在专栏《手把手带你破解银行科技岗面试》，如果你对银行科技岗（研发中心、数据中心、软开中心、金融科技岗、科技人才岗）感兴趣，欢迎点击此处订阅本专栏。本专栏将手把手带你破解银行科技岗面试，学习本专栏至少可以让你知道：

• 我到底能报考哪些银行里的哪些机构？
• 我到底是否能达到这些岗位的招聘要求？
• 我到底如何提前准备这些岗位的招聘面试？

根据我的经验，目前国内大多数银行的后端研发岗的技术栈都是Java那一套，一般上提问也是围绕着Java后端研发那一套展开（也会根据你的简历调整问题），这篇文章主要记录了我收集的银行技术面中问到的Java相关的问题，有问题也有我自己总结的答案，请大家参考。

为了便于分类记忆，我将这些问题分了如下几个目录：

• Java 语言
• Java 集合
• Java 并发
• Java JVM

限于篇幅，将分多篇文章更新，本文将更新Java 集合相关内容。

一、问题列表

我将面试收集到的高频问题给放在了这里，大家可以查漏补缺

1. 请你讲讲对 Java 集合的了解？
2. HashMap 源码分析（超级经典，源码可挖掘的东西很多）
3. 其他几种Map的对比
4. 讲一下jdk7和jdk8中map的区别
5. 讲下CopyOnWriteArrayList

二、答案参考

2.1 请你讲讲对 Java 集合的了解？

1. List,Set,Map 三者的区别？

List(对付顺序的好帮手)： 存储的元素是有序的、可重复的。

Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。

Map(用 Key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，“x”代表 key，"y"代表 value，Key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

2. List 主要实现类？

ArrayList 常用的，数组实现的

LinkedList 底层双向链表实现

Vector 和 ArrayList 基本一样，但是线程安全的

3. Set 主要实现类

HashSet 无序不可重复

LinkedHashSet 插入有序

TreeSet 大小有序

4. Map 的主要实现类

HashMap jdk1.7 之前用数组 + 链表 之后用 数组 + 红黑树。

LinkedHashMap 底层维护了一个链表，让插入变的有序。

TreeMap 还是可以按一定规则进行排列有序。

2.2 HashMap 源码分析（超级经典，源码可挖掘的东西很多）

八股文非常重要的一问：HashMap，经典面试题。今天把我看的一篇源码解析给大家分享一下。

一个比较不错的源码理解，可以看看：

https://zhuanlan.zhihu.com/p/79219960

HashMap 主要讲清楚三个点就可以了：

• 数据结构是如何实现的，为什么这么做？
• 根据数据结构讲，详细讲一下增 put 是如何实现的？
• 根据数据结构讲，扩容机制是如何实现的？

1. 数据结构

jdk1.7 的数据结构是数组 + 链表实现的

jdk1.8 的数据结构是数组 + 链表/红黑树实现的

• 数组

transient Node<K,V>[] table;    

记住这个 table，这属于常识性的东西！

• Node 的源码

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

可见 Node 里除了 K 和 V 还有一个 next，表示链表

2. 存储元素 put

以 jdk 1.8 为例！！！

上述 put 的步骤描述如下

（1）第一步：调用 put 方法传入键值对

（2）第二步：使用 hash 算法计算 hash 值

（3）第三步：根据 hash 值确定存放的位置，判断是否和其他键发生了哈希冲突

（4）第四步：若没有发生冲突，直接存放在数组中即可

（5）第五步：若发生了冲突，还要判断此时的数据结构是什么？

（6）第六步：若此时的数据结构是红黑树，那就直接插入红黑树中

（7）第七步：若此时的数据结构是链表，判断插入之后是否大于等于8

（8）第八步：插入之后大于 8 了，就要先调整为红黑树，在插入

（9）第九步：插入之后不大于 8，那么就直接插入到链表尾部即可。

• put 源码

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal 的五个参数的意思分别是

（1）第一个参数 hash：调用了 hash() 方法计算 hash 值，把 key 的 hash 值与与其自身的高十六位进行异或得到。

（2）第二个参数 key：就是我们传入的key值，也就是例子中的张三

（3）第三个参数 value：就是我们传入的value值，也就是例子中的20

（4）第四个参数 onlyIfAbsent：也就是当键相同时，不修改已存在的值

（5）第五个参数 evict ：如果为false，那么数组就处于创建模式中，所以一般为true。

• putVal 源码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //第一部分
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //第二部分
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //第三部分
    else {
        Node<K,V> e; K k;
        //第三部分第一小节
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //第三部分第二小节
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //第三部分第三小节
        else {
            for (int binCount = 0; ; ++binCount) {
                //第三小节第一段
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //第三小节第一段
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //第三小节第三段
                p = e;
            }
        }
        //第三部分第四小节
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //第四部分
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

看着非常恶心，一行一行来，对着那个流程图来看！

（1）首先是数据结构

Node<K,V>[] tab; Node<K,V> p; int n, i;

前面这个 tab 就是数组，所谓的桶；后面这个 p 与当前插入节点在同一个桶内的节点，或者说就是冲突节点n 代表 tab 的 capacityi 代表要插入的位置

（2）第一部分

//第一部分
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

这部分就是说，如果当前 map 的数组 table 为 null，或者 tab 的长度为 0 的话，就重新 resize 一个 table 数组，在 resize 函数内部又新建了一个 table 数组，并赋给 putVal 方法里的 tab。这部分你只需要知道这个就行了，不用知道 resize 是干什么的，之后扩容会说，这俩一定分开讨论，不要瞎几把弄。

（3）第二部分

//第二部分
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

此处就是框图的第二步，表示计算 hash 冲突，通过 (n - 1) & hash 算出位置，为什么要用这种方法算出桶下标的位置？因为 n 在第一部分已经赋值为容量，其容量是 2 的次幂，所以桶下标不允许超过这个下标，因此需要把 hash 的高位直接屏蔽掉，相当于求了个余。第二部分就是在说，如果没有发现 hash 冲突，桶内啥都没有，就直接放进去就 ok 了，但是如果存在 hash 冲突，就转入第三部分。

// 补充知识：计算机对 2 的次幂求余可用位运算，只对 2 次幂有效！如下例子
X & (2^N - 1) // 表示 X 对 2^N 求余
// 举一反三：计算机对 2 的次幂求除可用位运算，只对 2 次幂有效，如下例子
X >> N // 表示 X 除以 2^N 

（4）第三部分

Node<K,V> e; K k; 

e 表示已经存在节点，如果 e 不为空说明有旧节点，直接改新值就可以了。

​ (a) 第三部分第一小节第三部分和第二部分是 if else 关系，是判断 hash 冲突的分支，二部分表示无 hash 冲突，三部分表示有 hash 冲突一 二 三小节是处理 hash 冲突的并列的三个 if-else！

//第二部分
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
//第三部分 承上
else {
    Node<K,V> e; K k;
    //第三部分第一小节
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;

第 8 ~ 9 行，第一小节，判断 p（与当前节点在一个桶内的节点）的和要插入的节点的 hash 和 key 是否一致，如果一致则直接替换掉存在的 key 对应的旧值 e

​ (b) 第三部分第二小节

// 第三部分第二小节
else if (p instanceof TreeNode)
       e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

判断插入的数据结构是红黑树还是链表，在这里表示如果是红黑树，那就直接 putTreeVal 到红黑树中，具体也需要判断 key 和红黑树中的元素是否 equals，如果 equals，这就和流程图里面的第二个判断框对应了。

​ (c) 第三部分第三小节

//第三部分第三小节
else {
     for (int binCount = 0; ; ++binCount) {
        //第三小节第一段
         if ((e = p.next) == null) {
              p.next = newNode(hash, key, value, null);
              if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                  treeifyBin(tab, hash);
                  break;
         }
         //第三小节第二段
         if (e.hash == hash &&
               ((k = e.key) == key || (key != null && key.equals(k))))
              break;
         //第三小节第三段
         p = e;
    }
}

如果是链表，首先要遍历 table 内是否存在，如果不存在直接第 6 行 newNode(hash, key, value, null) ，如果存在了，第 5 行给 e 赋过值了，只要 e 不为空就说明 key 已存在。

注意一点：不存在并且在链表末尾插入元素的时候，会判断binCount >= TREEIFY_THRESHOLD - 1。也就是判断当前链表的长度是否大于阈值8，如果大于那就会把当前链表转变成红黑树，方法是treeifyBin。这也就和流程图中第三个判断框对应了。

​ (d) 第三部分第四小节

//第三部分第四小节
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

第三部分第四小节，收尾工作，如果 e 不为空，说明 key 已经存在于 hashMap 中，直接修改旧值即可！

（5）第四部分

// 第四部分
if (++size > threshold)
        resize();
afterNodeInsertion(evict);
return null;

插入成功之后，还要判断一下实际存在的键值对数量size是否大于阈值threshold。如果大于那就开始扩容了。

3. 扩容原理

首先，为什么要引入负载因子这种东西？而不是满了的话再扩容？满了的话相当于负载因子为 1，调高了意味着哈希冲突的概率会增高，这也就意味着会耗时，因为查找的速度变慢了。

扩容流程如下：

​

这个扩容就比较简单了，HaspMap扩容就是就是先计算新的hash表容量和新的容量****阀值，然后初始化一个新的 hash 表（就是 table 数组），将旧的键值对重新映射在新的 table 数组上。如果在旧的 hash 表里涉及到红黑树，那么在映射到新的 hash 表中还涉及到红黑树的拆分。整个流程也符合我们正常扩容一个容量的过程，我们根据流程图结合代码来分析。

• resize() 源码

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //第一部分：扩容
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //第二部分：设置阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //第三部分：旧数据保存在新数组里面
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //只有一个节点，通过索引位置直接映射
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //如果是红黑树，需要进行树拆分然后映射
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                     //如果是多个节点的链表，将原链表拆分为两个链表
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //链表1存于原索引
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //链表2存于原索引加上原hash桶长度的偏移量
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

其实别的也不用多看，这里面最巧妙的思想就是在第三部分 33 行开始，把旧数据复制到新数组里面的操作。首先说一下设计理念，扩容后，newCap = oldCap << 1; 容量乘 2，相当于把原来的容量分为左右两边，旧数据往新数据移动的理念就是，如果能平均分在这左右两侧就再好不过了，下面来解释 resize() 是如何实现这一点的。首先需要理解 putVal 操作的第二部分源码，通过 hash 值计算位置的这个 & 操作，可以看成是求余操作， hash & (capicity - 1)，对 capicity 求余操作，相当于只保留了 n 二进制的后几位。现在扩容后，执行了 newCap = oldCap << 1 的操作，其实再进行一下 (newCap - 1) & hash 也是可以的，但此处第 51 行用了 (e.hash & oldCap) == 0 这个判断条件，这样更能体现出，多出来的那个高位决定了旧数据是在原位还是位置 + oldCap，如下两条（记着 8 4 2 1 码，可以有助于理解），A：扩容后，若hash值新增参与运算的位 = 0，那么元素在扩容后的位置 = 原始位置B：扩容后，若hash值新增参与运算的位 = 1，那么元素在扩容后的位置 = 原始位置 + 扩容后的旧位置。

4. 构造方法

四个构造方法，最主要的只看这种方法：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}   

我们只需理解两个变量，initialCapacity 和 loadFactor，初始容量和负载因子。

• 缺省值是初始容量为 16，负载因子为 0.75
• 为什么容量一定是 2 的次幂？因为 HashMap 里用的是位运算来代替取模运算的，可以更加高效的算位置，只有大小为 2 的次幂时才能合理运用位运算代替取模。比如在算桶下标时就会用到取模，用 hash 值和 容量 - 1 进行与，就相当于 hash 值对 容量 取模，算出桶下标。
• 负载因子就是控制扩容和哈希冲突的。比如默认大小为 16，负载因子为 0.75，意味着最多放 12 个元素，超过 12 个就需要扩容。每次扩容为原来的 2 倍。
• 不能把负载因子变成 1，这样哈希冲突概率很高，查找效率会下降。

5. 其它HashMap的问题

注意：不是说变成了红黑树效率就一定提高了，只有在链表的长度不小于8，而且数组的长度不小于64的时候才会将链表转化为红黑树，

问题一：什么是红黑树呢？不是 AVL 树呢？

红黑树是一个自平衡的二叉查找树，也就是说红黑树的查找效率是非常的高，查找效率会从链表的 o(n) 降低为 o(logn)。如果之前没有了解过红黑树的话，也没关系，你就记住红黑树的查找效率很高就OK了。

AVL 树是严格平衡的，可以提供更快的查询效果，但是对于插入和删除，调整过于复杂了。如果是查找密集型的任务，用 AVL 没有任何毛病。

红黑树并没有追求完美的平衡，用非完美平衡来换取增删节点时候的调整次数降低，任何不平衡都可以在三次之内解决。如果是插入密集型任务，还是红黑树更适合。

问题二：为什么不一下子把整个链表变为红黑树呢？

这个问题的意思是这样的，就是说我们为什么非要等到链表的长度大于等于8的时候，才转变成红黑树？在这里可以从两方面来解释

（1）构造红黑树要比构造链表复杂，在链表的节点不多的时候，从整体的性能看来， 数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高。就好比杀鸡焉用牛刀的意思。

（2）HashMap频繁的扩容，会造成底部红黑树不断的进行拆分和重组，这是非常耗时的。因此，也就是链表长度比较长的时候转变成红黑树才会显着提高效率。

OK，到这里相信我们对hashMap的底层数据结构有了一个认识。现在带着上面的结构图，看一下如何存储一个元素。

问题三：为什么容量只能是 2 的次方数？

在根据 hash 计算桶下标的时候有一个求余的操作，是用位操作实现的，如果不是 2 的次方数，就没办法用位操作来实现了。

2.3 其他几种Map的对比

1. HashSet

底层还是个 HashMap，只不过所有的 key 对应的 value 是 HashSet 内部虚设了一个 Object，主要还是用的 HashMap 的 key

2. LinkedHashMap 插入有序 Map

底层是数组 链表 双向链表实现的，实际上其继承于 HashMap，在 HashMap 的基础上额外维护了一个双向链表，这个双向链表可以记录插入的顺序，其实就是 Entry 继承了 Node，多了个 before 和 after 节点。

在遍历的时候实际用的是双向链表来遍历的，所以不会影响到遍历性能。

3. TreeMap 比较有序 Map

底层数据结构是红黑树，红黑树是什么？是一个非常适合于查找的二叉搜索树，把查找效率由 N 变到 logN，其 key 不能为 null，TreeMap 也是排序意义上有序的，通过 Comparator 来比较的，如果 Comparator 为 null，则使用自然顺序！

4. ConcurrentHashMap 线程安全 Map

HashMap 并非线程安全的，在多线程环境下，会发生数据丢失或读取不了新数据的问题，比如 A put 进去了，B get 不出来。

所以用 juc 包下的 ConcurrentHashMap，除了这个还有 Hashtable 是线程安全的，当然也可以用 Collentions 包装出一个线程安全的 Map

但无论是 Hashtable 还是 Collections 包装，效率都很低（直接在外层套 synchronized）所以一般都用 ConcurrentHashMap

其底层数据结构是数组 + 链表/红黑树，支持高并发访问更新，是线程安全的。

通过部分加速和利用 CAS 算法来实现同步，在 get 的时候没有加锁，Node 都用了 volatile 修饰。

在扩容的时候，会给每个线程分配对应的区间，为了防止 putVal 导致数据不一致，会给线程所负责的区间加锁。

2.4 讲一下jdk7和jdk8中map的区别

1. 说说 jdk7 和 jdk8 的 HashMap 的区别

• jdk7 扩容头插法，jdk8 扩容尾插法，七上八下
• jkd7 HashMap 没有引入红黑树，jdk8引入了红黑树

2. 说说 jdk7 和 jdk8 的 ConcurrentHashMap 的区别

jdk7 中是用分段锁实现的，jdk8 .......

2.5 讲下CopyOnWriteArrayList

把原始数组复制出来一份快照，我读的时候就读这个快照，写的话就在原始数组上去写，写完之后更新快照即可。