首页  思维导图  详情

面试题之集合

2021-09-02 15:51:30   15  举报





AI智能生成

面试题之集合

Java

作者其他创作

大纲/内容

常见的集合有哪些

接口：Collection接口下的List，set，与Map接口

Queue队列

Vector矢量队列

Stack栈，先进后出

具体实现：ArrayList,LinkedList,HashMap,HashSet,HashTable,LinkedHashMap

有序集合List

不重复集合Set

键值映射集合Map

阻塞队列BlockingQueue

哪些集合类是线程安全的

Vector，Stack，Hashtable，java.util.concurrent包下所有的集合类

集合比较系列

Collection和Collections有什么区别

Collection是接口，Collections是包装类

Collection是JDK中集合层次结构中的最根本的接口，定义了集合类的基本方法。

Collections是一个包装类，包含有各种有关集合操作的静态多态方法，不能实例化，是Collection集合框架的工具类。

List，Set，Map之间的区别是什么

List：有序集合，元素可重复

Set：不重复集合，LinkedHashSet按照插入排序，SortedSet可排序，HashSet无序

Map：键值对集合，存储键、值和之间的映射；key无序，唯一；value不要求有序，允许重复

ArrayList和LinkedList的区别是什么

ArrayList基于动态数组实现的非线程安全的集合；LinkedList基于双向链表实现的非线程安全的集合

扩容问题：ArrayList使用个数组实现，无参构造函数默认初始化长度为10，数组扩容是会将原数组中的元素重新拷贝到新数组中，长度是原来的1.5倍；LinkedList不存在扩容问题，新增元素放到集合尾部，修改相应的指针节点即可

访问

对于随机index访问的get和set方法，一般ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组小标直接找到元素；LinkedList要移动指针遍历每个元素直到找到为止。

新增和删除元素，一般LinkedList的速度要优于ArrayList（尾部节点插入）。因为ArrayList在新增和删除元素时，可能扩容和复制数组；LinkedListt在新增和删除元素时修改节点指针即可

LinkedList集合不支持高效的随机访问（RandomAccess）

LInkedList比ArrayList更占内存，因为LinkedList为每个节点存储了前后两个元素的引用

ArrayList的空间浪费主要体现在在List列表的结尾预留一定的容量空间；LinkedList的空间花费则体现在它的每个元素都需要消耗存储指针节点对象的空间。

Array和ArrayList有何区别

Array即数组，定义一个Array时，必须指定数组的数据类型及数组长度，即数组中存放的元素个数固定并且类型相同

ArrayList是动态数组，长度动态可变，会自动扩容。不使用泛型时，可以添加不同类型元素。

ArrayList与Vector的联系和区别

相同点

底层都是使用数组实现的

功能相同，实现增删改查等操作的方法相似

长度可变的数组结构

不同点

Vector的方法都是同步的，线程安全的；ArrayList的方法都是非线程安全的，但性能比Vector好

默认初始化容量都是10，但是扩容倍数不同，Vector扩容默认是翻倍，可以指定扩容的大小；ArrayList只增加50%

HashMap与HashTable的区别

线程安全性不同：HashMap线程不安全，HashTable线程安全，方法中都是synchronized修饰的

Key、Value是否允许为null：HashMap的key和value都可以是null，可以只允许一个null；HashTable的key和value都不允许为null。

迭代器不同：HashMap的Iterator是fail-fast迭代器；HashTable还使用了Enumerator迭代器

初始容量大小和每次扩容的大小不同：

HashMap的初始容量为16，HashTable初始容量为11，两者的填充因子默认都是0.75

HashMap扩容时是当前容量翻倍及：capacity * 2 ；HashTable扩容时是容量翻倍+1 ，即：capacity * 2 + 1

底层实现不同：HashMap在1.8后使用数组加链表+红黑树的数据结构存储；HashTable使用的是数组加链表存储

父类不同：HashMap继承自AbstractMap；HashTable继承自Dictionary

如何决定使用HashMap还是TreeMap

HashMap基于散列桶（数组和链表）实现；TreeMap基于红黑树实现

HashMap不支持排序；TreeMap默认按照key值升序排序，可指定排序的比较器，主要用于存入元素时对元素进行自动排序。

HashMap大多数情况下有更多的性能，尤其是读数据。在没要求排序的情况下，使用HashMap。

HashMap与TreeMap都是非线程安全的。

如何实现数组和List之间的转换

数组转list，使用JDK中java.util.Arrays工具类的asList方法

list转数组，使用List的toArray方法。无参toArray方法返回Object数组，传入初始化长度的数组对象，返回该对象数组

迭代器Iterator是什么

首先说一下迭代器模式，它是 Java 中常用的设计模式之一。用于顺序访问集合对象的元素，无需知道集合对象的底层实现。

Iterator 是可以遍历集合的对象，为各种容器提供了公共的操作接口，隔离对容器的遍历操作和底层实现，从而解耦。

缺点是增加新的集合类需要对应增加新的迭代器类，迭代器类与集合类成对增加。

为什么基本类型不能作为HashMap的键值

Java中使用泛型来约束HashMap中的key和value的类型，HashMap<K,V>

泛型在Java的规定中必须是对象Object类型的，基本数据类型不是Object类型，不能作为键值

map.put(0,"123")中编译器已将key值0进行了自动装箱，变成了Integer类型

怎么确保一个集合不能被修改

以List为例，使用 JDK中java.util.Collections 类的unmodifiableList方法赋值原集合，原理是将数据复制到UnmodifiableList的list属性中，返回类型是UnmodifiableList，而UnmodifiableList不允许修改，增删改的方法都会抛出异常

原理系列

HashMap的底层原理

ArrayList的底层原理

ConcurrentHashMap原理

1.7

数据结构：ReentrantLock+Segment+HashEntry，一个Segment中包含一个HashEntry数组，每个
HashEntry又是一个链表结构

元素查询：二次hash，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部
锁：Segment分段锁 Segment继承了ReentrantLock，锁定操作的Segment，其他的Segment不受影
响，并发度为segment个数，可以通过构造函数指定，数组扩容不会影响其他的segment
get方法无需加锁，volatile保证

1.8

数据结构：synchronized+CAS+Node+红黑树，Node的val和next都用volatile修饰，保证可见性
查找，替换，赋值操作都使用CAS

锁：锁链表的head节点，不影响其他元素的读写，锁粒度更细，效率更高，扩容时，阻塞所有的读写
操作、并发扩容
读操作无锁：
Node的val和next使用volatile修饰，读写线程对该变量互相可见
数组用volatile修饰，保证扩容时被读线程感知

TreeMap的实现原理，如何保证其有序性