集合面试题

集合面试题

集合

• 1.List和Set的区别？
• 2.ArrayList与linkedList的区别？
• 3.HashSet如何检查重复？或HashCode和equals区别？
• 4.HashMap与HashTable的区别？底层实现是什么？
• 5.ConcurrentHashMap原理，jdk7和jdk8版本区别？
• 6.集合类不安全：并发情况下的ArrayList不安全，如何解决？
• 7.集合和数组的区别？
• 8.HashMap 的长度为什么是2的幂次方?
• 9.HashMap 多线程 *** 作导致死循环问题?
• 10.ConcurrentHashMap 和 Hashtable 的区别?
• 11. 如何实现数组和 List之间的转换？
• 12.java集合进行排序的两种方式？
• 13.什么是迭代器（Iterator）？

1.List和Set的区别？

List：有序，可重复，按照对象进入顺序保存对象，允许有多个NULL对象，可以使用get（int index）获取指定下标元素，也可使用Iterator取出所有元素，再逐一遍历。
Set：无序，不可重复，最多有一个NULL元素对象，取元素只能使用Iterator取出所有元素，再逐一遍历

2.ArrayList与linkedList的区别？

ArrayList：基于动态数组，使用连续内存存储，适合下标访问。
扩容机制：因为数组长度固定，超出长度时需要新建数组，将旧数组的数据拷贝到新数组。如果不是插入末尾会涉及到元素的移动
linkedList：基于链表，可存储在分散的内存中，适合数据的删除与插入 *** 作，不适合查询：需要逐一遍历。
遍历linkedList时不要使用for循环，因为每次循环体内获取某一元素时，都需要重新遍历。
ArrayList的增删未必比linkedList慢
1.如果是在末尾进行增删并且初始容量足够，不涉及到元素的移动与复制数组，当数据量有百万级，速度比linkedList要快（需要创建大量Node对象）
2.删除位置在中间时，由于linkedList消耗主要是在遍历上，ArrayList主要是在移动与复制上。当数据量有百万级，速度比linkedList要快。

3.HashSet如何检查重复？或HashCode和equals区别？

HashSet如何检查重复
对象加入HashSet时，先计算对象的HashCode判断对象加入的位置，看位置是否有值，如果没有，就加入，如果有值，会调用equals()方法检查两个对象是否相同，如果相同，不会加入成功，如果不同，重新放到其他位置，减少equals()判断，提高执行速度。
HashCode:确定该对象在哈希表中的索引位置。
两个对象相等，HashCode一定相同
两个对象相等，equals()判断返回true
两个对象HashCode相等，它们不一定相等
重写equals()时，HashCode也必须重写
HashCode默认对堆中的对象产生独特值。

4.HashMap与HashTable的区别？底层实现是什么？

1.区别：
（1）HashMap是非线程安全的，HashTable是线程安全的，方法都是synchronized进行修饰过的。
（2）HashMap允许key和value为null，HashTable不允许
2.底层实现：数组加链表
jdk8之后，当链表长度大于8，数组长度超过64，链表转变为红黑树，元素以内部类node节点存在

当往HashMap中添加key-value时，首先计算key的hash，根据hash确定存放位置。若该位置没有元素，直接插入，如果有，则迭代该处元素链表并依次比较key的hash。如果hash值相等，进行equals比较，如果也相等，使用新的Entry的value覆盖原来节点的value，如果hash值相等但key值不相等，将该节点插入该链表表头。
key为null存在下标为0的位置
数组扩容：创建新的数组，将旧数组的元素复制到新数组中。

5.ConcurrentHashMap原理，jdk7和jdk8版本区别？

jdk7：

数据结构：ReentrantLock+Segment+HashEntry,一个Segment包含一个HashEntry，每个HashEntry又是一个链表结构
元素查询：二次hash,第一次确定在哪个Segment，第二次hash定位到元素所在链表的头部
锁：分段锁Segment Segment继承ReentrantLock，锁定 *** 作的Segment，其他Segment不受影响，数组扩容不会影响其他Segment
get方法无需加锁，volatile保证

-jdk8
数据结构：synchronized + CAS + Node + 红黑树，node的val和next都用volatile修饰，保持可见性
查找、替换、赋值都用CAS（乐观锁机制）
锁：锁链表的head结点，不影响其他元素读写，锁粒度更细，效率更高，扩容时，阻塞所有的读写 *** 作、并发扩容
读 *** 作无锁：
node的val和next都用volatile修饰，
数组用volatile修饰，保证扩容为线程感知

6.集合类不安全：并发情况下的ArrayList不安全，如何解决？

List

1.使用Vector： List<> list = new Vector<>();
2.使用集合类的Collections.synchronizedList()：
List<> list = new Collections.synchronizedList()
3.写入时复制 CopyOnWrite：List<> list = new CopyOnWriteArrayList<>();读写分离
CopyOnWrite在写入时复制，可以避免写入时覆盖，而Vector底层使用synchronized方法，效率较低
Set

1.使用集合类的Collections.synchronizedSet(new HashSet<>())：
2.写入时复制 CopyOnWrite：Set<> set = new CopyOnWriteArraySet<>();读写分离
Map

使用ConcurrentHashMap<>():Map<> map = new ConcurrentHashMap<>();

7.集合和数组的区别？

数组是固定长度的；集合可变长度的。

数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。

数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

8.HashMap 的长度为什么是2的幂次方?

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

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的 *** 作来实现。但是，重点来了：“取余(%) *** 作中如果除数是2的幂次则等价于与其除数减一的与(&) *** 作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位 *** 作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

我们将一个键值对插入HashMap中，通过将Key的hash值与length-1进行&运算，实现了当前Key的定位，2的幂次方可以减少冲突（碰撞）的次数，提高HashMap查询效率
如果length为2的幂次方，则length-1 转化为二进制必定是11111……的形式，在与h的二进制与 *** 作效率会非常的快，而且空间不浪费
如果length不是2的幂次方，比如length为15，则length-1为14，对应的二进制为1110，在与h与 *** 作，最后一位都为0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

接下来，我们来做一个简单的总结：

总结：

也就是说2的N次幂有助于减少碰撞的几率，空间利用率比较大。这样你就明白为什么第一次扩容会从16 ->32了吧？总不会再说32+1=33或者其余答案了吧？至于加载因子，如果设置太小不利于空间利用，设置太大则会导致碰撞增多，降低了查询效率，所以设置了0.75。

9.HashMap 多线程 *** 作导致死循环问题?

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

10.ConcurrentHashMap 和 Hashtable 的区别?

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

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

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

List 转 Array
List 转Array，必须使用集合的 toArray(T[] array)，
Array 转List
使用Arrays.asList() 把数组转换成集合时，不能使用修改集合相关的方法啦

12.java集合进行排序的两种方式？

java集合的工具类Collections中提供了两种排序的方法,分别是:

Collections.sort(List list)
Collections.sort(List list,Comparator c)
第一种称为自然排序,参与排序的对象需实现comparable接口,重写其compareTo()方法,方法体中实现对象的比较大小规则,示例如下:
实体类:(基本属性,getter/setter方法,有参无参构造方法,toString方法)

13.什么是迭代器（Iterator）？

Iterator接口提供了很多对集合元素进行迭代的方法。每一个集合类都包括了可以返回迭代器实例的迭代方法。迭代器可以在迭代过程中删除底层集合的元素，但是不可以直接调用集合的remove(Object obj)删除，可以通过迭代器的remove()方法删除