Java 基础篇:
题记: 本系列文章, 会尽量模拟面试现场对话情景, 用口语而非书面语 , 采用问答形式来展现另外每一个问题都附上延伸, 这部分内容是帮助小伙伴们更深的理解一些底层细节的补充, 在面试中可能很少直接涉及, 权当是提高自身水平的知识储备吧
第一部分: java 容器相关
1. 问: List 和 Set 都有什么区别?
分析: 这种问题面试官一般想考察的都是你对这两种数据结构的了解, 已经使用时候的选择依据, 所以可以从数据结构和一些使用案例入手分别做个介绍
答: List, 列表, 元素可重复常用的实现 ArrayList 和 LinkedList, 前者是数组方式来实现, 后者是通过链表来实现, 在使用选择的时候, 一般考虑的是基本数据结构的特性, 比如, 数组读取效率较高, 链表插入时效率较高
Set, 集合, 特点就是存储的元素不可重复常用是实现, 是 HashSet 和 TreeSet, 分开来谈:
HashSet, 底层实现是 HashMap, 存储时, 把值存在 key, 而 value 统一存储一个 object 对象排重的时候, 是先通过对象的 hashcode 来判断, 如果不相等, 直接存储如果相等, 会再对 key 做 equals 判断, 如果依然相等, 不存储, 如果不相等, 则存入, 我们知道, HashMap 是数组 + 链表的基本结构, 同样的, 在 HashSet 中, 也是通过同样的策略, 存储在相同的数组位置下的链表中
TreeSet, 存入自定义对象时, 对象需要实现 Comparable 接口, 重写排序规则使用场景一般是需要保证存储数据的有序和唯一性底层数据结构是自平衡的二叉排序树(红黑树)
延伸:
a. 在说到 HashMap 时, 可能会直接引到 HashMap 相关话题, 我发现这个问题面试官非常喜欢问, 可能是因为 HashMap 可聊的较多, 也能很好的考验下应聘者对底层实现细节源码阅读刨根问底的态度
b. 涉及到二叉树了, 小端就遇到过一次问红黑树特性的, 因为之前准备过, 胸有成竹的啪啪啪正要一一道来呢, 结果刚说到第二个特性, 面试官就问: 红黑树和普通的平衡二叉树有什么区别? 当时一脸懵逼样... 回来后赶紧补足, 核心区别就是: 红黑树也是二叉查找树的一种, 二叉树需要通过自旋或其他方式 (比如红黑树还能通过变色) 来保证平衡(否则就成了链表结构了, 没有时间复杂度上的优势了), 红黑树限定的条件相对来说比较宽松, 也就是说在平衡的过程中, 消耗相对较小
c. 由于 HashSet 无序, 为了实现有序的目的, 又不想用其他数据结构, 可以用 LinkedHashSet 简要说明, 同 HashSet 和 HashMap 关系一样, 也是使用了一个 LinkedHashMap,LinkedHashMap 和普通的 HashMap 的区别就是, 在原有数据结构之上, 采用双向链表的形式将所有 entry(注意, 是前面讲过的数组 + 链表中的各个链表里的元素, 做了连接)连起来, 顺序就是 entry 的插入顺序, 这样可以保证元素的迭代顺序和插入顺序相同(有序性)
2.HashMap 是线程安全的吗, 为什么不是线程安全的?
分析: 这种问题, 既然面试官问起, 肯定是在这方面有的聊的这个问题, 在多数情况下, 能清晰全面的描述出问题来龙去脉即可, 很少有面试官真的拿一段源码来考当然, 作为应聘者, 如果能理解的很透彻, 再用简单的图边写边讲, 作为补充, 还是非常出彩的
答: 嗯, 不是线程安全的主要从两个方面来说:
a. 在插入新数据的时候, 多线程 hash 后的结果相同, 插入位置也就会定位到数组的相同下标下的同一个链表中在插入时, 假如第二个线程在第一个线程插入的瞬间也插入, 就可能会导致, 覆盖前面插入的值
b. 第二个非线程安全的影响是在扩容的时候, 扩容会把所有值重新 hash, 插入到新的扩容后的数组 + 链表结构中可能会导致环状链表情况出现, 这样在读取节点的 next 节点时, 永不为空, 也就是著名的扩容时 CPU 使用率 100% 情况
延伸:
要做到心中有底, 还是需要知其然知其所以然才行, 所以, 撸下源码好好想想, 才能做到临阵不乱
a. 建议好好看看源码, 源码量不大, 结构也比较清晰
b. 针对环状链表的情况, 我是看了别人写的图文并茂版的文章弄明白的, 这里放上链接, 供参考: HashMap 高并发问题
3. 问: 那你是用什么数据结构来作为替代, 满足线程安全的场景要求呢?
分析: 这里一般面试官想考察的是对 ConcurrentHashMap 的了解, 但是也有个别情况, 会涉及到 HashTable, 小端就吃过这方面的亏, 明明可以一笔带过的小知识点, 却由于准备不充分, 而没能答完整
答: 在 Java 里, 提供了以下数据结构, 可以解决线程安全问题:
a.HashTable, 实现原理是通过 Synchronize 同步锁来把读写方法都加锁的方式虽然线程安全了, 但是效率低下, 只要有读写, 就不能做其他操作
b.SynchronizedMap(涉及较少, 了解即可), 有条件的同步, 是 Collections 类提供的一个方法返回的 HashMap 的多线程版本实现是把基本的方法都加了同步锁
c.ConcurrentHashMap(重头戏): 根据 jdk 版本不同, 实现也有差别
java8 以前, 是用 segment(锁住 map 一段实现, 默认是 16 段也就是可以并发数支持到 16, 也可自定义读不受影响), 数据结构为数组(segment)+ 数组(entry)+ 链表, 适用于读多写少的场景提供原子操作 putIfAbsent()(没有则添加)segment 继承自 ReentrantLock, 来作为锁
java8, 元素结构为 Node(实现 Entry 接口), 数据结构为数组 + 链表; 直接对 Node 进行加锁, 粒度更小当链表长度大于 8, 转换为红黑树, 当然在转换前, 先看下数组长度, 如果小于 64, 那先通过扩容来实现; 插入元素时, 如果该位置为 null, 用 CAS 插入; 如果不为 null, 则加 Synchronize 锁插入到链表;
扩展:
a. 我们看到, 数组的默认长度都是 16, 那么这个数字有什么深意吗? 有! 做运算时效率高! 属于取巧的设计一个是扩容的时候, 直接向左位操作, 移一位, 扩张为二倍; 二是 hash 取模的时候, hash 值是 32 位, 右移 28 位, 剩高四位, 然后与这个 length-1 也就是 15(1111)按位与操作, 使数据均匀分布
b.ConcurrentHashMap 在获取 size 时候是怎么计算的呢?
1.7size(), 先获取 segment 的大小, 然后判断是否修改过, 如果是, 在加锁重新获取 segment 大小, 然后把所有 segment 大小加在一起;
1.8size()的实现是用一个 volatile 变量来做 CAS 修改, 如果高并发, 还会把部分值存到一个 volatile 数组取值时, 把这两部分的值加在一起 mappingcount()方法和 size()方法实现方式一样
c.hashmap 可以使用 null 作为 key 和 value, 存储于 table 数组第一个节点; hashtable 不允许 key 和 value 为 null.(这个在一个小公司被面试官问倒了, 汗颜)
d. 了解一些其他的数据结构:
ConcurrentSkipListMap 数据有序
ConcurrentSkipListSet 能去重
e.hashset 是用 hashmap 实现, 内部存的是 key, 所有的 value 都是同一个 object
来源: https://www.cnblogs.com/xyang/p/8625726.html