<>Java集合面试题

<>集合概述

<>说说List、Set、Map三者的区别?

* List: 存储的元素是有序的、可重复的。
* Set: 存储的元素是无序的、不可重复的
* Map: 使用键值对(kye-value)存储,Key 是无序的、不可重复的,value 是无序的、可重复的,每个键最多映射到一个值
<>集合框架底层数据结构总结

<>list

* Arraylist: Object[]数组
* Vector:Object[]数组
* LinkedList: 双向链表(JDK1.6 之前为循环链表,JDK1.7 取消了循环)
<>Set

* HashSet(无序,唯一): 基于 HashMap 实现的,底层采用 HashMap 来保存元素
* LinkedHashSet:LinkedHashSet 是 HashSet 的子类,并且其内部是通过 LinkedHashMap
来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 HashMap 实现一样,不过还是有一点点区别的
* TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树)
<>Map

* HashMap: JDK1.8 之前 HashMap 由数组+链表组成的,数组是 HashMap
的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为
8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间
* LinkedHashMap: LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,
LinkedHashMap
在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。
* Hashtable: 数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的
* TreeMap: 红黑树(自平衡的排序二叉树)
<>如何选用集合?

* 主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合,需要排序时选择 TreeMap,不需要排序时就选择
HashMap,需要保证线程安全就选用 ConcurrentHashMap。
* 当我们只需要存放元素值时,就选择实现 Collection 接口的集合,需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或
HashSet,不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList,然后再根据实现这些接口的集合的特点来选用。
<>为什么要使用集合?

* 当我们需要保存一组类型相同的数据的时候,我们应该是用一个容器来保存,这个容器就是数组,但是,使用数组存储对象具有一定的弊端,
* 因为我们在实际开发中,存储的数据的类型是多种多样的,于是,就出现了“集合”,集合同样也是用来存储多个数据的
* 数组的缺点是一旦声明之后,长度就不可变了;同时,声明数组时的数据类型也决定了该数组存储的数据的类型;而且,数组存储的数据是有序的、可重复的,特点单一。
* 但是集合提高了数据存储的灵活性,Java 集合不仅可以用来存储不同类型不同数量的对象,还可以保存具有映射关系的数据
<>Iterator 迭代器

<>迭代器 Iterator 是什么?

* Iterator
对象称为迭代器(设计模式的一种),迭代器可以对集合进行遍历,但每一个集合内部的数据结构可能是不尽相同的,所以每一个集合存和取都很可能是不一样的,虽然我们可以人为地在每一个类中定义
hasNext() 和 next() 方法,但这样做会让整个集合体系过于臃肿。于是就有了迭代器。
* 迭代器是将这样的方法抽取出接口,然后在每个类的内部,定义自己迭代方式,这样做就规定了整个集合体系的遍历方式都是 hasNext()和next()
方法,使用者不用管怎么实现的,会用即可。迭代器的定义为:提供一种方法访问一个容器对象中各个元素,而又不需要暴露该对象的内部细节。
<>迭代器 Iterator 有啥用?

* Iterator 主要是用来遍历集合用的,它的特点是更加安全,因为它可以确保,在当前遍历的集合元素被更改的时候,就会抛出
ConcurrentModificationException 异常。
<>有哪些集合是线程不安全的?怎么解决呢?

* 我们常用的 Arraylist ,LinkedList,Hashmap,HashSet,TreeSet,TreeMap,PriorityQueue
都不是线程安全的。解决办法很简单,可以使用线程安全的集合来代替。
* 如果你要使用线程安全的集合的话, java.util.concurrent 包中提供了很多并发容器供你使用:
* ConcurrentHashMap: 可以看作是线程安全的 HashMap
* CopyOnWriteArrayList:可以看作是线程安全的 ArrayList,在读多写少的场合性能非常好,远远好于 Vector
* ConcurrentLinkedQueue:高效的并发队列,使用链表实现。可以看做一个线程安全的 LinkedList,这是一个非阻塞队列。
* BlockingQueue: 这是一个接口,JDK 内部通过链表、数组等方式实现了这个接口。表示阻塞队列,非常适合用于作为数据共享的通道。
* ConcurrentSkipListMap :跳表的实现。这是一个Map,使用跳表的数据结构进行快速查找。
<>Collection 子接口之 List

<>Arraylist 和 Vector 的区别?

* ArrayList 是 List 的主要实现类,底层使用 Object[ ]存储,适用于频繁的查找工作,线程不安全 ;
* Vector 是 List 的古老实现类,底层使用 Object[ ]存储,线程安全的。
* 初始容量都是10,但是Vector每次扩容都是1倍,ArrayList每次扩容是1.5倍
<>Arraylist 与 LinkedList 区别?

* 是否保证线程安全: ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;
* 底层数据结构: Arraylist 底层使用的是 Object 数组;LinkedList 底层使用的是 双向链表 数据结构(JDK1.6
之前为循环链表,JDK1.7 取消了循环。)
* 插入和删除是否受元素位置的影响: ① ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)
方法的时候,ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(
add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i
个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ②LinkedList 采用链表存储,所以对于add(E e)
方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话((add(int index, E element)
) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
* 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList
支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
* 内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList
的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。
<>双向链表和双向循环链表

* 双向链表: 包含两个指针,一个 prev 指向前一个节点,一个 next 指向后一个节点。
* 双向循环链表: 最后一个节点的 next 指向 head,而 head 的 prev 指向最后一个节点,构成一个环。
<>RandomAccess 接口

* RandomAccess 接口中什么都没有定义。所以,在我看来 RandomAccess 接口不过是一个标识罢了。标识什么?
标识实现这个接口的类具有随机访问功能。
* ArrayList 实现了 RandomAccess 接口, 而 LinkedList 没有实现。
* ArrayList 实现了 RandomAccess 接口,就表明了他具有快速随机访问功能。
<>ArrayList 的扩容机制

* 以无参数构造方法创建 ArrayList
时,实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为10。
* ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右(oldCapacity为偶数就是1.5倍,否则是1.5倍左右)! 奇偶不同,比如
:10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数
<>Collection 子接口之 Set

<>comparable 和 Comparator 的区别

* comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
* comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序
* 一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo()方法或compare()
方法,当我们需要对某一个集合实现两种排序方式,比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo()
方法和使用自制的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的
Collections.sort().
<>无序性和不可重复性的含义是什么

* 什么是无序性?无序性不等于随机性 ,无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ,而是根据数据的哈希值决定的。
* 什么是不可重复性?不可重复性是指添加的元素按照 equals()判断时 ,返回 false,需要同时重写 equals()方法和
HashCode()方法。
<>比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

* HashSet 是 Set 接口的主要实现类 ,HashSet 的底层是 HashMap,线程不安全的,可以存储 null 值;
* LinkedHashSet 是 HashSet 的子类,能够按照添加的顺序遍历;
* TreeSet 底层使用红黑树,能够按照添加元素的顺序进行遍历,排序的方式有自然排序和定制排序。
<>Map 接口

<>HashMap 和 Hashtable 的区别

* 线程是否安全: HashMap 是非线程安全的,HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized
修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!);
* 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它;
* 对 Null key 和 Null value 的支持: HashMap 可以存储 null 的 key 和 value,但 null
作为键只能有一个,null 作为值可以有多个;HashTable 不允许有 null 键和 null 值,否则会抛出 NullPointerException。
* 初始容量大小和每次扩充容量大小的不同 : ① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为 11,之后每次扩充,容量变为原来的
2n+1。HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。② 创建时如果给定了容量初始值,那么 Hashtable
会直接使用你给定的大小,而 HashMap 会将其扩充为 2 的幂次方大小(HashMap 中的tableSizeFor()
方法保证,下面给出了源代码)。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
* 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为
8)(将链表转换成红黑树前会判断,如果当前数组的长度小于
64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。
<>HashMap 和 HashSet 区别

* 如果你看过 HashSet 源码的话就应该知道:HashSet 底层就是基于 HashMap 实现的。(HashSet 的源码非常非常少,因为除了
clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。
<>HashMap 和 TreeMap 区别

* TreeMap 和HashMap 都继承自AbstractMap ,但是需要注意的是TreeMap它还实现了NavigableMap接口和
SortedMap 接口。
* 实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。
* 实现SortMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序
<>HashSet 如何检查重复

* 当你把对象加入HashSet时,HashSet 会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的 hashcode
值作比较,如果没有相符的 hashcode,HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象,这时会调用equals()
方法来检查 hashcode 相等的对象是否真的相同。如果两者相同,HashSet 就不会让加入操作成功。
<>HashMap 的底层实现

<>JDK1.8 之前

* JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode
经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n
指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key
是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。
* 所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法
换句话说使用扰动函数之后可以减少碰撞。
<>JDK1.8 之后

* 相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为
8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。
<>HashMap 1.8为何从头插改为尾插

*
jdk1.7中HashMap默认采用数组+单链表方式存储元素,当元素出现哈希冲突时,会存储到该位置的单链表中。这和1.8不同,除了数组和单链表外,当单链表中元素个数超过8个时,会进而转化为红黑树存储,巧妙地将遍历元素时时间复杂度从O(n)降低到了O(logn))
*
HashMap在jdk1.7中采用头插入法,在扩容时会改变链表中元素原本的顺序,以至于在并发场景下导致链表成环的问题。而在jdk1.8中采用尾插入法,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了
* 1.7扩容时需要重新计算哈希值和索引位置,1.8并不重新计算哈希值,巧妙地采用和扩容后容量进行&操作来计算新的索引位置。
<>HashMap 的长度为什么是 2 的幂次方

* 为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上面也讲到了过了,Hash 值的范围值-2147483648 到
2147483647,前后加起来大概 40 亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个 40
亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“
(n - 1) & hash”。(n 代表数组长度)。这也就解释了 HashMap 的长度为什么是 2 的幂次方。
<>HashMap 多线程操作导致死循环问题

* 主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过,jdk 1.8 后解决了这个问题,但是还是不建议在多线程下使用
HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。
<>HashMap 有哪几种常见的遍历方式?

* HashMap 遍历从大的方向来说,可分为以下 4 类:
* 迭代器(Iterator)方式遍历;
* For Each 方式遍历;
* Lambda 表达式遍历(JDK 1.8+);
* Streams API 遍历(JDK 1.8+)。
* 但每种类型下又有不同的实现方式,因此具体的遍历方式又可以分为以下 7 种:
* 使用迭代器(Iterator)EntrySet 的方式进行遍历;
* 使用迭代器(Iterator)KeySet 的方式进行遍历;
* 使用 For Each EntrySet 的方式进行遍历;
* 使用 For Each KeySet 的方式进行遍历;
* 使用 Lambda 表达式的方式进行遍历;
* 使用 Streams API 单线程的方式进行遍历;
* 使用 Streams API 多线程的方式进行遍历。
* 总结
* 具体的 7 种遍历方法,除了 Stream 的并行循环,其他几种遍历方法的性能差别不大,但从简洁性和优雅性上来看,Lambda 和 Stream
无疑是最适合的遍历方式。
* 从安全性来讲,我们应该使用迭代器提供的 iterator.remove() 方法来进行删除,这种方式是安全的在遍历中删除集合的方式,或者使用
Stream 中的 filter 过滤掉要删除的数据再进行循环,也是安全的操作方式。
<>ConcurrentHashMap 和 Hashtable 的区别

* ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
* 底层数据结构: JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟
HashMap1.8 的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表
的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;
* 实现线程安全的方式(重要): ① 在 JDK1.7 的时候,ConcurrentHashMap(分段锁)
对整个桶数组进行了分割分段(Segment[seɡmənt]),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。
到了 JDK1.8 的时候已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized
和 CAS 来操作。(JDK1.6 以后 对 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在
JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;②Hashtable(同一把锁) :使用
synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put
添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。
<>ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

<>JDK1.7

*
JDK1.7 的 ConcurrentHashMap:

*

*
首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。

*
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

*
Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁,扮演锁的角色。HashEntry 用于存储键值对数据。

*
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似,是一种数组和链表结构,一个
Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个 HashEntry
数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 的锁。

<>JDK1.8

*
JDK1.8 的 ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点):

*

*
ConcurrentHashMap 取消了 Segment 分段锁,采用 CAS 和 synchronized 来保证并发安全。数据结构跟
HashMap1.8 的结构类似,数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为
O(N))转换为红黑树(寻址时间复杂度为 O(log(N)))

*
synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍。

<>Collections 工具类

<>Collections 工具类常用方法:

*
排序

*
查找,替换操作

*
同步控制(不推荐,需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

* Collections 提供了多个synchronizedXxx()
方法·,该方法可以将指定集合包装成线程同步的集合,从而解决多线程并发访问集合时的线程安全问题。
* 我们知道 HashSet,TreeSet,ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。
Collections 提供了多个静态方法可以把他们包装成线程同步的集合。
* 最好不要用下面这些方法,效率非常低,需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。
* 方法如下: synchronizedCollection(Collection<T> c) //返回指定 collection
支持的同步(线程安全的)collection。 synchronizedList(List<T> list)//返回指定列表支持的同步(线程安全的)List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步(线程安全的)Map。 synchronizedSet(Set<T> s)
//返回指定 set 支持的同步(线程安全的)set。
<>其他重要问题

<>什么是快速失败(fail-fast)?

* 快速失败(fail-fast) 是 Java 集合的一种错误检测机制。
在使用迭代器对集合进行遍历的时候,我们在多线程下操作非安全失败(fail-safe)的集合类可能就会触发 fail-fast 机制,导致抛出
ConcurrentModificationException 异常。 另外,在单线程下,如果在遍历过程中对集合对象的内容进行了修改的话也会触发
fail-fast 机制。
<>什么是安全失败(fail-safe)呢?

*
采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。所以,在遍历过程中对原集合所作的修改并不能被迭代器检测到,故不会抛
ConcurrentModificationException 异常

技术
©2019-2020 Toolsou All rights reserved,
基于神经网络的车辆牌照字符识别技术Java基础(三) String深度解析 dedecms网站被黑 劫持到其他网站如何解决精准手机号抓取,运营商大数据利用梆梆加固逻辑漏洞取巧脱壳QT 删除目录及文件Java小明A+B苹果不送充填器耳机真为环保?可能还是为了赚钱吧在Pytorch上使用summaryC#中字典的排序方法