第14章：随堂复习与企业真题（数据结构与集合源码）

一、随堂复习

1. 数据结构

• 数据结构的研究对象：
  • ① 数据间的逻辑关系（集合关系、一对一、一对多、多对多）
  • ② 数据的存储结构（或物理结构）
    • 角度一：顺序结构、链式结构、索引结构、哈希结构
    • 角度二：线性表（一维数组、链表、栈、队列）、树（二叉树、B+树）、图（多对多）、哈希表（HashMap、HashSet)
  • ③ 相关运算
• 树（了解）
• 相关数据结构的核心Node的设计（单向链表、双向链表、二叉树、栈、队列）（理解）

2. List接口下的实现类的源码剖析

【面试题】ArrayList、Vector、LinkedList的三者的对比？

• 层次1：

|-----子接口：List:存储有序的、可重复的数据 ("动态"数组)
       |---- ArrayList:List的主要实现类；线程不安全的、效率高；底层使用Object[]数组存储
                       在添加数据、查找数据时，效率较高；在插入、删除数据时，效率较低
       |---- LinkedList:底层使用双向链表的方式进行存储；在对集合中的数据进行频繁的删除、插入操作时，建议使用此                         类在插入、删除数据时，效率较高；在添加数据、查找数据时，效率较低；
       |---- Vector:List的古老实现类；线程安全的、效率低；底层使用Object[]数组存储

• 层次2：查看相关api的源码

（见笔记，略）

3. Map接口下的实现类的源码剖析

• （掌握）HashMap的底层源码的剖析
• （熟悉）LinkedHashMap的底层源码的剖析
• （了解）HashSet、LinkedHashSet的底层源码的剖析

二、企业真题

2.1 数据结构相关

1. 链表和数组有什么区别？（腾*）

第14章课件里：《【拓展】尚硅谷_宋红康_数据结构概述-Java版.xmind》

2. 栈是如何运行的？(西*信息技术)

先进后出。属于ADT(abstract data type)，可以使用数组、链表实现栈结构

2.2 List集合源码相关

1. ArrayList的默认大小是多少，以及扩容机制（顺*、凡*科技）

类似问题：
> 说说ArrayList的扩容机制吧(国*电网)
> 讲一下ArrayList的扩容机制（*实在）
> ArrayList的扩容机制，为什么是10，为什么是1.5倍（*软国际）

略

2. ArrayList的底层是怎么实现的?（腾*）

类似问题：
集合类的ArrayList底层（安全不安全，扩容，初始大小，添加删除查询是怎么操作的，底层是什么组成的）
（湖**利软件、汇*云通、猎*、苏州***动、上海*进天下、北京博*软件、*科软、大连*点科技、中*亿达、德*物流、天*伟业、猫*娱乐）

略。

建议：ArrayList(int capacity){}

3. 在ArrayList中remove后面几个元素该怎么做?（惠*、中*亿达）

前移。

4. ArrayList1.7和1.8的区别（拓*思）

类似于饿汉式、懒汉式

5. 数组和 ArrayList 的区别（阿*、*科软）

ArrayList看做是对数组的常见操作的封装。

6. 什么是线程安全的List？(平*金服)

Vector：线程安全的。

ArrayList：线程不安全。—-> 使用同步机制处理。

HashMap:线程不安全。 ----> 使用同步机制处理。
                   -----> JUC:ConcurrentHashMap

2.3 HashMap集合源码相关

1. 说说HahMap底层实现(新*股份、顺*、猫*娱乐)

类似问题：
> HashMap的实现讲一下？（腾*，上海**网络）
> 说说HashMap的底层执行原理？（滴*，纬*软件，上海*想，*昂，*蝶**云，宇*科技，*东数科，猎*网）
> 详细说一下 HashMap 的 put 过程（*度）
> Java中的HashMap的工作原理是什么？（北京中**译咨询）
> 集合类的HashMap底层（安全不安全，扩容，初始大小，添加删除查询是怎么操作的，底层是什么组成的）（湖**利软件）
> HashMap 的存储过程（爱*信、杭州*智）
> Hashmap底层实现及构造（汇**通、猎*、苏州博*讯动、上海*进天下、北京博*软件、*科软、大连*点科技、中*亿达、德*物流、天*伟业、猫*娱乐）
> HashMap的实现原理（腾*、阿*）
> HaspMap底层讲一讲（*米）
> 说一下HashMap的实现，扩容机制？（*节）
> 讲一下 HashMap 中 put 方法过程？（阿*）

略。建议以JDK8为主说明。

2. HashMap初始值16，临界值12是怎么算的（软**力）

16从底层源码的构造器中看到的。

12：threshold，使用数组的长度*加载因子(loadFactor)

3. HashMap长度为什么是2的幂次方(国*时代)

为了方便计算要添加的元素的底层的索引i。

4. HashMap怎么计算哈希值和索引？扩容机制？怎么解决hash冲突？（*软国际、中软*腾）

类似问题：
> HashMap key的哈希冲突了怎么做（新*股份）
> HashMap的默认大小是多少，以及扩容机制（顺*、凡*科技）
> 讲一下HashMap的扩容机制？（好实*）

略

5. HashMap底层是数组+链表，有数组很快了，为什么加链表？（润*软件）

因为产生了哈希冲突。解决方案，使用链表的方式。保证要添加的元素仍然在索引i的位置上。

6. HashMap为什么长度达到一定的长度要转化为红黑树（*度）

类似问题：
> HashMap为什么用红黑树（*软国际）

红黑树的常用操作的时间复杂度O(logn)，比单向链表的O(n)效率高。

7. HashMap什么时候扩充为红黑树，什么时候又返回到链表？（汉*）

类似问题：
> HashMap什么时候转换为红黑树（杭州*智公司）
> 当HashMap中相同hashcode值的数据超过多少时会转变成红黑树？（百*云创）
> 什么时候是数据+链表，什么时候是红黑树（*软国际）

索引i的位置的链表长度超过8且数组长度达到64，需要索引i位置要变成红黑树。

当索引i的位置元素的个数低于6时，要红黑树结构转为单向链表。为什么？节省空间。

8. 在 JDK1.8中，HashMap的数据结构与1.7相比有什么变化，这些变化的好处在哪里？（海*科）

① 在jdk8中，当我们创建了HashMap实例以后，底层并没有初始化table数组。当首次添加(key,value)时，进行判断，
如果发现table尚未初始化，则对数组进行初始化。
② 在jdk8中，HashMap底层定义了Node内部类，替换jdk7中的Entry内部类。意味着，我们创建的数组是Node[]
③ 在jdk8中，如果当前的(key,value)经过一系列判断之后，可以添加到当前的数组角标i中。如果此时角标i位置上有
   元素。在jdk7中是将新的(key,value)指向已有的旧的元素（头插法），而在jdk8中是旧的元素指向新的
   (key,value)元素（尾插法）。 "七上八下"
④ jdk7:数组+单向链表
   jk8:数组+单向链表 + 红黑树
   什么时候会使用单向链表变为红黑树：如果数组索引i位置上的元素的个数达到8，并且数组的长度达到64时，我们就将此索引i位置上
                               的多个元素改为使用红黑树的结构进行存储。（为什么修改呢？红黑树进行put()/get()/remove()
                               操作的时间复杂度为O(logn)，比单向链表的时间复杂度O(n)的好。性能更高。
   什么时候会使用红黑树变为单向链表：当使用红黑树的索引i位置上的元素的个数低于6的时候，就会将红黑树结构退化为单向链表。

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. 用哪两种方式来实现集合的排序（凡*科技）

类似问题：
> 集合怎么排序？（北京中**信科技）

自然排序、定制排序。