Java数据结构面试题以及答案

本专栏记录Java后端开发相关的面试题，欢迎大家阅读专栏的其他文章。

目录

1.B树和B+树的区别？B树和B+树的优点分别是？

2.排序算法的种类和复杂度

3.HashMap和Hashtable的原理、区别、应用场景

4.ConcurrentHashMap的原理、应用场景

5.ArrayList和LinkedList的区别？原理？应用场景？

6.String、StringBuilder和StringBuffer的区别，应用场景

7.ArrayList和Vector的区别

8.Collection下有哪些子类

9.Comparable和Comparator的区别

---

 

1.B树和B+树的区别？B树和B+树的优点分别是？

B树和B+树详细解析_星空是梦想的博客-CSDN博客

1.1 B树和B+树的区别

B树特征：

• 关键字集合分布在整颗树中
• 每个结点都存放有若干个 key 和 value
• 任何一个关键字出现且只出现在一个结点中
• 搜索有可能在非叶子结点结束
• 其搜索性能等价于在关键字全集内做一次二分查找

B+树特征：

• 非叶子结点不保存数据，只保存 key，所有数据都保存在叶子节点
• 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
• 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字
• 通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点
• 同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素

B树和B+树区别：

• B+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”
• b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）
• 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历

1.2 B树的优点

相比于普通的二叉树来说，B树是平衡二叉树，它增加和删除节点对树的整体结构来说，改动非常小，适合用来存储大数据

1.3 B+树的优点

• b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”
• b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）
• 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历

2.排序算法的种类和复杂度

2.1 什么是算法的空间复杂度

算法的空间复杂度是指：算法在运行过程中，除了存储算法基本数据的空间外，需要耗费的额外空间。

2.2 排序算法的时间和空间复杂度

排序算法的时间和空间复杂度

算法名称	时间复杂度	空间复杂度
冒泡排序	O(n^2)	O(1)
直接插入排序	O(n^2)	O(1)
直接选择排序	O(n^2)	O(1)
快速排序	O(n*logn)	O(n*logn)
希尔排序	O(n*logn)	O(1)
堆排序	O(n*logn)	O(1)
计数排序 介绍	O(d(n+k))	O(n+k)
归并排序	O(n*logn)	O(n)

 

 

        

 

 

 

 

 

 

 

 

3.HashMap和Hashtable的原理、区别、应用场景

3.1 原理

1. HashMap 和 Hashtable 的底层结构都是 数组+链表结构实现的。数组用于存储链表头节点，新增元素都会添加到对应位置的链表末尾，链表节点数量超过 8 时，链表会转化为红黑树。
2. 它们的链表节点中有一个 hash 变量，用于存储该结点的 hash 值，通过 hash值 可以快速定位元素位置。

3.2 区别

HashMap 和 Hashtable 的主要区别是：

1. Hashtable 是线程安全的，HashMap 是线程不安全的，主要原因是 Hashtable 的主要方法都加了 synchronized锁，实现了访问互斥。
2. HashMap 的 key 和 value 都允许为 null，Hashtable 的 key 和 value 都不允许为空。

3.3 应用场景

HashMap 用于非并发场景，Hashtable 用于并发场景，但是并发场景推荐使用concurrentHashMap。

4.ConcurrentHashMap的原理、应用场景

4.1 原理

1. ConcurrentHashMap 的底层结构也是 基于 数组+链表 实现的，数组用于存储链表的链表头，链表节点包含 key、value、hash值、next变量等，每次新插入的元素都会添加到对应下标的链表末尾，当链表长度超过 8 时，链表将转化为红黑树。
2. ConcurrentHashMap 跟 Hashtable 一样是线程安全的，但是 ConcurrentHashMap 的锁是细粒度锁，需要进行修改操作时，它只对数组的一项进行加锁，而不是对整个数组加锁。

4.2 应用场景

多线程情况下对 HashMap 进行添加、删除操作时使用。虽然 Hashtable 和 ConcurrentHashMap 的应用场景差不多，但是还是尽量使用 ConcurrentHashMap。

5.ArrayList和LinkedList的区别？原理？应用场景？

5.1 ArrayList原理

小学生也能看懂的ArrayList底层原理_怎么看arraylist的底层_星空是梦想的博客-CSDN博客

ArrayList 底层使用 char数组 实现，除了数组，还有一个记录数组大小的 size 变量，添加数组元素时，当数组已满时，会进行扩容，将容量扩大为 1.5 倍。

5.2 LinkedList原理

学透 LinkedList 底层实现原理，狂虐面试官！_星空是梦想的博客-CSDN博客

LinkedList 底层使用 双向链表 实现，LinkedList类中有头节点（first）、尾节点（last）和记录链表长度的 size。

LinkedList 的节点结构为：item（存储节点值）、next（存储下一个节点）和 prev（存储上一个节点）。

5.3 两者区别

• ArrayList 使用char数组实现，LinkedList 使用链表实现；
• ArrayList 和 LinkedList 都是非线程安全的；
• 随机 get 和 set 访问，ArrayList 比 LinkedList 好，因为 LinkedList 访问要移动指针；
• 插入和删除操作，LinkedList 比 ArrayList 好，因为 ArrayList 要大量移动数据。

5.4 应用场景

• 如果涉及到“栈”、“队列”、“链表”等操作，应该选择使用 List；

• 如果需要快速删除、插入元素，应该使用 LinkedList ；

• 如果需要快速访问元素，应该使用 ArrayList。

6.String、StringBuilder和StringBuffer的区别，应用场景

6.1 运行速度比较

运行速度测试代码

StringBuilder > StringBuffer > String

解释：

创建 String 对象后，因为 String 对象是不可变的，每次需要改变 String 的值，都要重新建立一个新对象，再将引用指向该对象，浪费内存，而且无用对象多了 jvm 会引发 GC，系统就变慢了。

StringBuilder 和 StringBuffer 是可变的字符串变量，在进行字符串拼接时，不会创建新对象，而是直接对原对象进行操作，速度上比 String 拼接快很多；另外，由于 StringBuffer 底层实现都加了 synchronized 修饰，执行速度上稍微比 StringBuilder 慢一点。

6.2 是否线程安全

• StringBuilder 是线程不安全的；
• StringBuffer 是线程安全的。

解释：

StringBuffer 底层的很多方法（例如append 和 inser）都使用 synchronized 关键字修饰，保证了多线程情境下的线程安全。

6.3 适用场景

• String：适用于少量字符串操作情况。
• StringBulider：适用于单线程在字符串缓存区进行大量操作。
• StringBuffer：适用于多线程在字符串缓存区进行大量操作。

6.4 底层实现

StringBuilder和StringBuffer：

1. 底层使用 char数组 实现；
2. append(str)方法：内部先判断 str 是否为空，为空的话在 char数组后添加“null”，不为空则将 str 拷贝到 char数组。

7.ArrayList和Vector的区别

7.1 相同点

ArrayList 和 Vector 都实现了List接口，都是有序可重复集合。

7.2 不同点

• 线程安全：Vector是 线程安全 的，也就是说是它的方法之间是线程同步的；ArrayList是 线程序不安全 的，它的方法之间是线程不同步的。
• 动态扩容倍数：当存储空间不足时，两种都会动态增长。Vector增长为原来的 2 倍，ArrayList增加为原来的 1.5 倍。

8.Collection下有哪些子类

List

• Vector
• ArrayList
• LinkedList

Set

• HashSet
• TreeSet

9.Comparable和Comparator的区别

1. Comparable和Comparator都可以实现对象比较和对象集合的排序。
2. 类通过实现Comparable接口和compareTo方法，实现比较逻辑，可以实现和同个类对象进行比较，通过Collections.sort(List)实现类集合的排序。
3. Comparator可以不改变类本身而进行比较和排序，需要创建另一个类实现该接口，然后实现compareTo方法，对目标类进行比较，另外，可以使用Collections.sort(List, Comparator)对类集合进行排序。