面试必备(集合)

其他面试题

Java 中怎么打印数组？

你可以使用 Arrays.toString() 和 Arrays.deepToString() 方法来打印数组。由于数组没有实现 toString() 方法，所以如果将数组传递给 System.out.println() 方法，将无法打印出数组的内容，但是 Arrays.toString() 可以打印每个元素。

说出几点 Java 中使用 Collections 的最佳实践

这是我在使用 Java 中 Collectionc 类的一些最佳实践：

使用正确的集合类，例如，如果不需要同步列表，使用 ArrayList 而不是 Vector。
优先使用并发集合，而不是对集合进行同步。并发集合提供更好的可扩展性。
使用接口代表和访问集合，如使用 List 存储 ArrayList，使用 Map 存储 HashMap 等等。
使用迭代器来循环集合。
使用集合的时候使用泛型。

用哪两种方式来实现集合的排序？

你可以使用有序集合，如 TreeSet 或 TreeMap，你也可以使用有顺序的的集合，如 list，然后通过 Collections.sort() 来排序。

Array 和 ArrayList 有何区别？

定义一个 Array 时，必须指定数组的数据类型及数组长度，即数组中存放的元素个数固定并且类型相同。
ArrayList 是动态数组，长度动态可变，会自动扩容。不使用泛型的时候，可以添加不同类型元素。

Arraylist与LinkedList区别

可以从它们的底层数据结构、效率、开销进行阐述哈

ArrayList是数组的数据结构，LinkedList是链表的数据结构。
随机访问的时候，ArrayList的效率比较高，因为LinkedList要移动指针，而ArrayList是基于索引(index)的数据结构，可以直接映射到。
插入、删除数据时，LinkedList的效率比较高，因为ArrayList要移动数据。
LinkedList比ArrayList开销更大，因为LinkedList的节点除了存储数据，还需要存储引用。

List、Map、Set 三个接口存取元素时，各有什么特点？

List 以特定索引来存取元素，可以有重复元素。

Set 不能存放重复元素（用对象的 equals()方法来区分元素是否重复）。

Map 保存键值对（key-value pair）映射，映射关系可以是一对一或多对一。

Set 和 Map 容器都有基于哈希存储和排序树的两种实现版本，基于哈希存储的版本理论存取时间复杂度为 O(1)，而基于排序树版本的实现在插入或删除元素时会按照元素或元素的键（key）构成排序树从而达到排序和去重的效果。

List、Set、Map 是否继承自 Collection 接口？

List、Set 是，Map 不是。

Map 是键值对映射容器，与 List 和 Set 有明显的区别，而 Set 存储的零散的元素且不允许有重复元素（数学中的集合也是如此），List 是线性结构的容器，适用于按数值索引访问元素的情形。

Collection 和 Collections 的区别？

Collection 是一个接口，它是 Set、List 等容器的父接口；Collections 是个一个工具类，提供了一系列的静态方法来辅助容器操作，这些方法包括对容器的搜索、排序、线程安全化等等。

HashMap原理，java8做了什么改变

HashMap是以键值对存储数据的集合容器
HashMap是非线性安全的。
HashMap底层数据结构：数组+(链表、红黑树)，jdk8之前是用数组+链表的方式实现，jdk8引进了红黑树
Hashmap数组的默认初始长度是16，key和value都允许null的存在
HashMap的内部实现数组是Node[]数组，上面存放的是key-value键值对的节点。HashMap通过put和get方法存储和获取。
HashMap的put方法，首先计算key的hashcode值，定位到对应的数组索引，然后再在该索引的单向链表上进行循环遍历，用equals比较key是否存在，如果存在则用新的value覆盖原值，如果没有则向后追加。
jdk8中put方法：先判断Hashmap是否为空，为空就扩容，不为空计算出key的hash值i，然后看table[i]是否为空，为空就直接插入，不为空判断当前位置的key和table[i]是否相同，相同就覆盖，不相同就查看table[i]是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于8，转为红黑树结构，执行完成后看size是否大于阈值threshold，大于就扩容，否则直接结束。
Hashmap解决hash冲突，使用的是链地址法，即数组+链表的形式来解决。put执行首先判断table[i]位置，如果为空就直接插入，不为空判断和当前值是否相等，相等就覆盖，如果不相等的话，判断是否是红黑树节点，如果不是，就从table[i]位置开始遍历链表，相等覆盖，不相等插入。
HashMap的get方法就是计算出要获取元素的hash值，去对应位置获取即可。
HashMap的扩容机制，Hashmap的扩容中主要进行两步，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算hash插入到新数组中，jdk8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。
HashMap大小为什么是2的幂次方？效率高+空间分布均匀

List 和 Set，Map 的区别

List 以索引来存取元素，有序的，元素是允许重复的，可以插入多个null。
Set 不能存放重复元素，无序的，只允许一个null
Map 保存键值对映射，映射关系可以一对一、多对一
List 有基于数组、链表实现两种方式
Set、Map 容器有基于哈希存储和红黑树两种方式实现
Set 基于 Map 实现，Set 里的元素值就是 Map的键值

poll() 方法和 remove() 方法的区别？

poll() 和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。

HashMap，HashTable，ConcurrentHash的共同点和区别

HashMap

底层由链表+数组+红黑树实现
可以存储null键和null值
线性不安全
初始容量为16，扩容每次都是2的n次幂
加载因子为0.75，当Map中元素总数超过Entry数组的0.75，触发扩容操作.
并发情况下，HashMap进行put操作会引起死循环，导致CPU利用率接近100%
HashMap是对Map接口的实现

HashTable

HashTable的底层也是由链表+数组+红黑树实现。
无论key还是value都不能为null
它是线性安全的，使用了synchronized关键字。
HashTable实现了Map接口和Dictionary抽象类
Hashtable初始容量为11

ConcurrentHashMap

ConcurrentHashMap的底层是数组+链表+红黑树
不能存储null键和值
ConcurrentHashMap是线程安全的
ConcurrentHashMap使用锁分段技术确保线性安全
JDK8为何又放弃分段锁，是因为多个分段锁浪费内存空间，竞争同一个锁的概率非常小，分段锁反而会造成效率低。

写一段代码在遍历 ArrayList 时移除一个元素

因为foreach删除会导致快速失败问题，fori顺序遍历会导致重复元素没删除，所以正确解法如下：

第一种遍历，倒叙遍历删除

for(int i=list.size()-1; i>-1; i--){  
	if(list.get(i).equals("jay")){    
		list.remove(list.get(i));  
	}
}

第二种，迭代器删除

Iterator itr = list.iterator();while(itr.hasNext()) {
	if(itr.next().equals("jay") {        
		itr.remove();      
	}
}

HashMap 的扩容过程

Hashmap的扩容：

第一步把数组长度变为原来的两倍，
第二步把旧数组的元素重新计算hash插入到新数组中。
jdk8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二步一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。

HashMap 是线程安全的吗，为什么不是线程安全的？死循环问题？

不是线性安全的。

并发的情况下，扩容可能导致死循环问题。

哪些集合类是线程安全的？哪些不安全？

线性安全的

Vector：比Arraylist多了个同步化机制。
Hashtable：比Hashmap多了个线程安全。
ConcurrentHashMap:是一种高效但是线程安全的集合。
Stack：栈，也是线程安全的，继承于Vector。

线性不安全的

Hashmap
Arraylist
LinkedList
HashSet
TreeSet
TreeMap

Collection与Collections的区别是什么？

Collection是Java集合框架中的基本接口，如List接口也是继承于它

1	public interface List<E> extends Collection<E> {

Collections是Java集合框架提供的一个工具类，其中包含了大量用于操作或返回集合的静态方法。如下：

1
2
3

public static <T extends Comparable<? super T>> void sort(List<T> list) {
	list.sort(null);
}

迭代器 Iterator 是什么？怎么用，有什么特点？

1 2	public interface Collection<E> extends Iterable<E> { Iterator<E> iterator();

方法如下：

next() 方法获得集合中的下一个元素
hasNext() 检查集合中是否还有元素
remove() 方法将迭代器新返回的元素删除
forEachRemaining(Consumer<? super E> action) 方法，遍历所有元素

Iterator 主要是用来遍历集合用的，它的特点是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常。

使用demo如下：[动画表情]

List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){
    String obj = it. next();
    System. out. println(obj);
}