4.1.2 银行技术面---编程语言类(Java集合)
本文章将收录在专栏《手把手带你破解银行科技岗面试》,如果你对银行科技岗(研发中心、数据中心、软开中心、金融科技岗、科技人才岗)感兴趣,欢迎点击此处订阅本专栏。本专栏将手把手带你破解银行科技岗面试,学习本专栏至少可以让你知道:
- 我到底能报考哪些银行里的哪些机构?
- 我到底是否能达到这些岗位的招聘要求?
- 我到底如何提前准备这些岗位的招聘面试?
根据我的经验,目前国内大多数银行的后端研发岗的技术栈都是Java那一套,一般上提问也是围绕着Java后端研发那一套展开(也会根据你的简历调整问题),这篇文章主要记录了我收集的银行技术面中问到的Java相关的问题,有问题也有我自己总结的答案,请大家参考。
为了便于分类记忆,我将这些问题分了如下几个目录:
- Java 语言
- Java 集合
- Java 并发
- Java JVM
限于篇幅,将分多篇文章更新,本文将更新Java 集合相关内容。
一、问题列表
我将面试收集到的高频问题给放在了这里,大家可以查漏补缺
- 请你讲讲对 Java 集合的了解?
- HashMap 源码分析(超级经典,源码可挖掘的东西很多)
- 其他几种Map的对比
- 讲一下jdk7和jdk8中map的区别
- 讲下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);
判断插入的数据结构是红黑树还是链表
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏主要介绍银行科技岗的面试技巧和经验,涵盖了银行科技岗可能遇到的所有面试形式。可以帮助你识别面试套路,教你如何根据自身情况提前准备好专属于自己的“面试套话、满分话术”,把面试难度降维,从而提升面试能力、改善面试效果。 如果你对总行管培岗、直属研发中心、直属数据中心、省分行科技专项人才岗感兴趣,欢迎订阅本专栏,本专栏会手把手教你如何破解面试难题,拿到心仪的offer。