第14章:随堂复习与企业真题(数据结构与集合源码)
第14章:随堂复习与企业真题(数据结构与集合源码)
一、随堂复习
1. 数据结构
数据结构的研究对象:
- ① 数据间的逻辑关系(集合关系、一对一、一对多、多对多)
- ② 数据的存储结构(或物理结构)
- 角度一:顺序结构、链式结构、索引结构、哈希结构
- 角度二:线性表(一维数组、链表、栈、队列)、树(二叉树、B+树)、图(多对多)、哈希表(HashMap、HashSet)
- ③ 相关运算
树(了解)
相关数据结构的核心Node的设计(单向链表、双向链表、二叉树、栈、队列)(理解)
2. List接口下的实现类的源码剖析
【面试题】ArrayList、Vector、LinkedList的三者的对比?
- 层次1:
1 | |-----子接口:List:存储有序的、可重复的数据 ("动态"数组) |
- 层次2:查看相关api的源码
(见笔记,略)
3. Map接口下的实现类的源码剖析
- (掌握)HashMap的底层源码的剖析
- (熟悉)LinkedHashMap的底层源码的剖析
- (了解)HashSet、LinkedHashSet的底层源码的剖析
二、企业真题
2.1 数据结构相关
1. 链表和数组有什么区别?(腾*)
第14章课件里:《【拓展】尚硅谷_宋红康_数据结构概述-Java版.xmind
》
2. 栈是如何运行的?(西*信息技术)
先进后出。属于ADT(abstract data type),可以使用数组、链表实现栈结构
2.2 List集合源码相关
1. ArrayList的默认大小是多少,以及扩容机制(顺*、凡*科技)
1 | 类似问题: |
略
2. ArrayList的底层是怎么实现的?(腾*)
1 | 类似问题: |
略。
建议:ArrayList(int capacity){}
3. 在ArrayList中remove后面几个元素该怎么做?(惠*、中*亿达)
前移。
4. ArrayList1.7和1.8的区别(拓*思)
类似于饿汉式、懒汉式
5. 数组和 ArrayList 的区别(阿*、*科软)
ArrayList看做是对数组的常见操作的封装。
6. 什么是线程安全的List?(平*金服)
Vector:线程安全的。
ArrayList:线程不安全。—-> 使用同步机制处理。
1 | HashMap:线程不安全。 ----> 使用同步机制处理。 |
2.3 HashMap集合源码相关
1. 说说HahMap底层实现(新*股份、顺*、猫*娱乐)
1 | 类似问题: |
略。建议以JDK8为主说明。
2. HashMap初始值16,临界值12是怎么算的(软**力)
16从底层源码的构造器中看到的。
12:threshold,使用数组的长度*加载因子(loadFactor)
3. HashMap长度为什么是2的幂次方(国*时代)
为了方便计算要添加的元素的底层的索引i。
4. HashMap怎么计算哈希值和索引?扩容机制?怎么解决hash冲突?(*软国际、中软*腾)
1 | 类似问题: |
略
5. HashMap底层是数组+链表,有数组很快了,为什么加链表?(润*软件)
因为产生了哈希冲突。解决方案,使用链表的方式。保证要添加的元素仍然在索引i的位置上。
6. HashMap为什么长度达到一定的长度要转化为红黑树(*度)
1 | 类似问题: |
红黑树的常用操作的时间复杂度O(logn),比单向链表的O(n)效率高。
7. HashMap什么时候扩充为红黑树,什么时候又返回到链表?(汉*)
1 | 类似问题: |
索引i的位置的链表长度超过8且数组长度达到64,需要索引i位置要变成红黑树。
当索引i的位置元素的个数低于6时,要红黑树结构转为单向链表。为什么?节省空间。
8. 在 JDK1.8中,HashMap的数据结构与1.7相比有什么变化,这些变化的好处在哪里?(海*科)
1 | ① 在jdk8中,当我们创建了HashMap实例以后,底层并没有初始化table数组。当首次添加(key,value)时,进行判断, |
9. HashMap的get()方法的原理?(顺*)
参考put()
2.4 hashCode和equals
1. hashcode和equals区别?(海*供应链管理)
略
2. hashCode() 与 equals() 生成算法、方法怎么重写?(阿*校招)
进行equals()判断使用的属性,通常也都会参与到hashCode()的计算中。
尽量保证hashCode()的一致性。(使用IDEA自动生成,hashCode()自动使用相关的算法。
3. 说一下equals和==的区别,然后问equals相等hash值一定相等吗?hash值相等equals一定相等吗?(南*电网、上海*智网络)
equals相等hash值一定相等吗? 是
hash值相等equals一定相等吗?不一定
2.5 Set集合源码相关
1. HashSet存放数据的方式?(拓*软件)
底层使用HashMap。说一下HashMap
2. Set是如何实现元素的唯一性?(湖**利软件)
略
3. 用哪两种方式来实现集合的排序(凡*科技)
1 | 类似问题: |
自然排序、定制排序。