java基础技术集合面试【笔记】

时间:2021-03-03 23:56:53

java基础技术集合面试【笔记】

Hashmap:

基于哈希表的 Map 接口的实现,此实现提供所有可选的映射操作,并允许使用 null 值和 null 键(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变

另外,HashMap是非线程安全的,也就是说在多线程的环境下,可能会存在问题,而Hashtable是线程安全的

HashMap 内部的数据结构?

各个版本的实现略有不同

JDK1.7 及以前的 HashMap 采用数组 + 链表的结构来存储数据

JDK8 中的 HashMap 采用了数组 + 链表或树的结构来存储数据

HashMap 的存储数据的过程?

​不同的 JDK 版本版本的存储过程略有差异,在 JDK1.8 中,HashMap 存储数据的过程可以分为以下几步:

1.对 key 的 hashCode () 进行 hash 后计算数组获得下标 index

2.如果当前数组为 null,进行容量的初始化,初始容量为 16

3.如果 hash 计算后没有碰撞,直接放到对应数组下标里

4.如果 hash 计算后发生碰撞且节点已存在,则替换掉原来的对象

5.如果 hash 计算后发生碰撞且节点已经是树结构,则挂载到树上

6.如果 hash 计算后发生碰撞且节点是链表结构,则添加到链表尾,并判断链表是否需要转换成树结构(默认大于 8 的情况会转换成树结构)

7.完成 put 后,是否需要 resize () 操作(数据量超过 threshold,threshold 为初始容量和负载因子之积,默认为 12)

而在 Java 1.7 的版本中,5和6是合在一起的,即如果发生哈希碰撞且节点是链表结构,则放在链表头

简单来说,jdk1.7是头插法,jdk1.8是尾插法

PS:HashMap 中的两类存储数据的方法:put () 和 putAll (),二者底层都是调用的同一个 putVal () 方法

如果 hashCode 相同,如何获取对象呢?

​hashCode 相同,说明这些对象的数据都在同一个数组下标对应的链表或者树上,get 方法的签名是 V get (Object key) ,入参只有一个 key,因此通过遍链表或者树,取出每一个节点对比 hash 值是否相等且 key 是否相等 (= 或者 equals)

HashMap 和 HashTable 有什么区别?

这是一个比较重要的基础问题

HashMap 是 JDK1.2 才出现的,而HashTable 是 JDK1.0 就出现了

JDK 里面也说了 HashMap 可以大致相当于 HashTable

至于具体的差异:

1.HashMap 是线程不安全的,而 HashTable 由于所有方法都加了 synchronized 关键字所以是线程安全的

2.HashMap 的键需要重新计算对象的 hash 值,而 HashTable 直接使用对象的 hashCode

3.HashMap 的值和键都可以为 null,HashTable 的值和键都不能为 null

4.HashMap 的数组的默认初始化大小为 16,HashTable 为 11,HashMap 扩容时会扩大两倍,HashTable 扩大两倍 + 1

ArrayList 和 LinkedList 的异同?

相同点:ArrayList 和 LinkedList 都是 List 接口的实现类,因此都具有 List 的特点:存取有序,可重复,而且两者都不是线程安全的

不同点:内部数据结构不一样,ArrayList 基于数组实现,LinkedList 基于双向链表实现

ArrayList 和 LinkedList 的异同的派生问题:ArrayList 和 LinkedList 分别适用于什么场景呢?

​我们应该清楚,不同的内部数据结构,其比较合适的应用场景也是不同的

ArrayList 基于数组存储数据,因此查询元素时可以直接按照数据下标进行索引,而插入元素时,通常涉及到数据元素的复制和移动,所以查询数据快而插入数据慢,所以ArrayList 适合查询多(读多)的场景

LinkedList 基于双向链表存储数据,因此查询元素时需要前向或后向遍历,而插入数据时只需要修改本元素的前后项即可,所以查询数据慢而插入数据快,所以,LinkedList 适合插入多(写多)的场景

List、Set以及Map三者之间的区别是什么?

List 是有序集合,可以有重复元素

Set 集合不能包括重复元素,实现类中 LinkedHashSet 按照插入顺序排序,SortedSet 可排序,HashSet 无序

Map 存放键值对 (key-value pairs) 映射,映射关系可以是一对一或多对一,key 无序且唯一,value 可重复。实现类中 LinkedHashMap 按照插入顺序排序,SortedMap 可排序,HashMap 无序

派生问题:原理?

首先,List 与 Set 具有相似性,都继承共同的 Collection 接口,也都是单列元素的集合。List 的内部是数组,所以不断在数组后面追加元素即可,这是它为什么有序的原因

而 Set 里面不允许有重复的元素,这里的重复是指两个相等 (注意不是相同) 的对象 ,即 equals () 返回 true。如果 Set 集合 s 中有 A 元素,现在再向 s 集合插入 B 元素,此时 B 元素如果与 A 元素相等,则 B 元素存储不进去(add 方法返回 false)

​其次,Map 与 List 和 Set 不同,它是双列的集合,值得注意的是并不继承 Collection

List、Set以及Map三者的共同之处?

1.add、remove、contanins、size 等方法的耗时性能,是不会随着数据量的增加而增加的,这个主要跟 HashMap 底层的数组数据结构有关,不管数据量多大,不考虑 hash 冲突的情况下,时间复杂度都是 O (1)

2.线程不安全的,如果需要安全请自行加锁,或者使用 Collections.synchronizedSet

3.迭代过程中,如果数据结构被改变,会快速失败的,会抛出 ConcurrentModificationException 异常

ArrayList 和 LinkedList 都不是线程安全的,那有线程安全的 List 类吗?

有,线程安全 List 类有 Vector 和 CopyOnWriteList

Vector 是通过在其几乎所有方法前加 synchronized 关键字来保证线程安全性

CopyOnWriteList 则是通过数组复制的方法来保证线程安全的。

Java 集合的快速失败(fail-fast)和安全失败(fail-safe)的差别是什么?

快速失败和安全失败都是 java 集合的一种错误机制

单线程情况下,遍历集合时去执行增删等改变集合结构的操作

多线程情况下,一个线程遍历集合,另一个线程执行增删等改变集合结构的操作

快速失败,是指失败以及异常时会立即报错,通常会抛出 ConcurrentModificationException 异常,像 java.util 包下面的集合类就是使用这种机制

安全失败,是指失败以及异常时会直接忽略,java.util.concurrent 包下面的集合类都是使用这种机制。

快速失败的原因在于,每当迭代器在进行增删等操作时,会使用 hashNext ()以及next () 进行元素遍历,而元素遍历之前都会检测 modCount 变量是否为 expectedmodCount 的值,是的话就返回遍历,否则抛出异常 ConcurrentModificationException,终止遍历

安全失败的处理方式则有两种:一是CopyOnWriteArrayList 以及CopyOnWriteArraySet 这类集合,底层增删时会复制数组,如果增删操作前遍历数组,则会遍历复制前的老视图,二者并不冲突,二是 ConcurrentHashMap 这些并发集合,这些集合不存在 expectedmodCount,这样Iterator 也不会做相应的检查

HashMap 和 ConcurrentHashMap 的区别?

1.基础特性不同:

HashMap 的 key 和 value 可以为 null

ConcurrentHashMap 的 key 和 value 不能为 null

2.内部数据结构不同:

ConcurrentHashMap 在 JDK1.7 中采用的数据结构是分段的数组 + 链表,JDK1.8 的内部数据结构采用的数据结构是数组 + 链表 / 红黑二叉树(同 HashMap 一致)

java基础技术集合面试【笔记】

HashMap 在 JDK1.7 中采用的数据结构是数组 + 链表,在 JDK1.8 中采用的数据结构是数组 + 链表 / 红黑二叉树

java基础技术集合面试【笔记】

3.线程安全不同:

HashMap 是非线程安全的

ConcurrentHashMap 是线程安全的

Java集合框架是什么?说出一些集合框架的优点?

每种编程语言中都有集合,集合框架的部分优点如下:

(1)使用核心集合类降低开发成本,而非实现我们自己的集合类

(2)随着使用经过严格测试的集合框架类,代码质量会得到提高

(3)通过使用JDK附带的集合类,可以降低代码维护成本

(4)复用性和可操作性

java基础技术集合面试【笔记】