集合面试题整理

ゝ一世哀愁。 2022-01-23 04:27 404阅读 0赞

**集合面试题整理**

推荐博客：[http://cmsblogs.com/?cat=325][http_cmsblogs.com_cat_325]

1、Map和ConcurrentHashMap的区别？

ConcurrentHashMap：jdk1.5之后引入，解决了HashMap线程不安全，和HashTable效率不高的问题。1.7之前使用了分段锁的方式。1.8之后使用数组链表红黑树cas原子操作来实现的。

Map：是一个映射接口。

2、hashMap内部具体如何实现的？

哈希表：综合了数组的链表的优点，可以快速的定位查找和删除。使用拉链法构建哈希表。就是使用数组加链表的形式。而每个元素中储存的是链表的头结点。我们可以把这样的一张链表称为一个桶。那么hashMap是在快速定位的呢。使用hashCode(key)%len，key的哈希码（每个key的哈希码都会不一样）对数组长度取余。我们可以认为hashMap的容器是一个线性的数组。它的内部实现了一个静态内部类Entry，其重要的属性是key、value、next。这个数组就是Entry\[\]。

**put**：当我们通过哈希值与Entry.lenght取余的时候，获得了相同的下标值。那么值会不会覆盖？？？？前面我们说过了Entry有一个重要的属性就是next。比如：A的哈希值与len取余等于下标5。这时会把A放在Entry\[5\]中。到需要储存B的时候，B的哈希值与len取余也等于下标5，那么B.next=A,然后把B放在Entry\[5\]中。当需要储存C的时候，C的哈希值与len取余也等于下标5,那么C.next=B,然后把C放在Entry\[5\]中。实际上数组Entry中储存的都是后插入的元素。当然hashMap中也有优化的地方，当数据越来越大，map的长度会根据负载因子自动扩容。**null key始终放在第一个元素。**链表的长度默认为8超过，就转为红黑树。

**get**：先定位到数组，然后根据哈遍历链表找到哈希值相同的元素。

**resize**：resize表示扩容。capacity：Entry的长度 默认16、loadFactor：负载因子 默认0.75。**当map中的元素个数超过，Entry的长度乘以负载因子时，就会自动扩容为原来的两倍**。当我们预知元素的数量时，设置map的容量应该避免resize。即**Entry的长度乘以负载因子 > 元素个数**。

3、如果hashMap的key是一个自定义的类，怎么办？

需要重写key类的hashCode()和eques()方法。

**hashCode()**：此方法继承自Object类，在使用的时候默认根据jvm的内存地址返回一个整数，对于hashCode有一个约定：

**                    1.**程序在一次执行过程中，对于同一个对象要返回同一个整数。

**                    2.**两个对象通过eques方法比较结果为true，那么他们的hashCode的值也相等。                                           **3.**如果两个对象通过eques方法比较结果为false，不必保证他们的hashCode也相等。

**eques()**:   此方法也是继承自Object，首先比较两个对象的内存地址，然后在比较他们的内容。它具有以下几个特点：

1.  1.  1.  自反性：对于任意的x，x.eques(x)==true；
        2.  对称性：如果x.eques(y)==true那么y.eques(x)==true；
        3.  传递性：对于x，y，z，如果x.eques(y)==true、y.eques(z)==true那么x.eques(z)==true
        4.  一致性：xy的信息没有改变，无论调用多少次x.eques(y)都没true。
        5.  对任何不为null的x，x.eques(null)==false;

当我们使用一个类作为key的时候，比较两个类是否相等，先查看hashCode，然后再比较eques方法，如果为true，那么我们就认为他们是相等的。从而保证了key的唯一性。**需要注意的是我们在创建一个类的时候，重写了它的hashCode方法了 就一定要重写它的eques方法。**

4、ArrayList和LinkedList的区别，如果一直在list的尾部添加元素，用哪个效率高？

**ArrayList**：他的内部使用数组的数据结构。它的默认容量为10，当容量不够的时候，就会自动扩大容量，1.5倍;  在遍历时通过索引序号访问比较快，而使用迭代器的效果最慢。

**LindedList**：内部使用了双向链表的方式。

linkdeList的效率会高一些，因为他只需要改变一些尾部的指针就可以了。而arrayList必须判断是否会越界，如果会，就需要扩大容量。这个过程就会影响到效率。

5、HashMap底层，负载因子，为啥是2^n？

hashMap实际上是使用数组加链表的方式来储存的，通过哈希值对元素长度取余来找元素在数组中的位置，随着我们的数据量越来越大，数组的容量不够用，就会自动扩容到原来的2^n倍，这样就不会打乱之前存放元素的位置，同样可以通过哈希值对长度取余定位到原来的元素位置。

6、ConcurrentHashMap锁加在了哪些地方？

ConcurrentHashMap中用到了一个segment数组， Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。

7、TreeMap底层，红黑树原理

8、ConcurrentHashmap有啥优势，1.7，1.8区别？

ConcurrentHashMap 主要是解决了HashMap效率高但线程不安全，HashTable线程安全但效率不高的问题

1.7使用segment+数组+链表

1.8使用segment+数组+链表+红黑树

9、ArrayList是否会越界？

它会自动扩容为1.5倍；

10、什么是TreeMap?

根据key进行排序的映射，底层使用红黑树实现。

11、ConcurrentHashMap的原理是什么？

ConcurrentHashMap中用到了segment的数组，这个不可以扩容。然后在sement中在放一个数组+链表（相当于hashMap）。对每一个sement进行加锁，就保证了全局的ConcurrentHashMap的全局安全。

12、Java集合类框架的基本接口有哪些？

集合中主要包含Collection个Map。

conllectin中有List和set和queue接口

还有Iterable接口

13、什么是迭代器？

迭代器相当于遍历集合，我们不需要知道集合的内部结构就可以进行遍历。提供了hasNext()next()remove()方法。

14、Iterator和ListIterator的区别是什么？

ListIterator只能用来遍历List，同时还可以在里面添加元素，而且还可以反向遍历。同时还可以添加元素和修改元素。

15、快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

*   *  fail-fast :快速失败，指的是某个线程在访问一个集合的时候，另一个线程改变了这个集合。就会抛出ConcurrentModification异常，这就是fail-fast机制。在遍历的时候我们使用的是迭代器，迭代器有3个变量：cursor：即将遍历到的下一个元素的下标。lsatRet：表示刚刚遍历过的元素的下标。expectedModCount = modCount：modCount用来记录操作集合的时候，对集合的修改次数。在操作集合的过程中，expectedModCount ！= modCount 就会抛出异常，产生fail-fast。
     *  fail-safe：在java.util.concurrent包下的类都是安全失败的。它不会抛出异常。使用迭代器遍历的时候会复制一个集合，而修改的时候是对原集合进行修改的，所以就不会触发ConcurrenModification异常。

16、HashMap和Hashtable有什么区别？

*   *   Hashtable是线程安全的，不支持null的key和null的value。使用 Enumeration   进行枚举遍历，不会出现快速失败的问题。
     *  HashMap是非线程安全的，支持null的key和value，使用iterator迭代遍历。可能出现快速失败的问题

17、ArrayList和LinkedList有什么区别？

ArrayList使用动态数组的方式实现，他的访问效率比较快，但是删除的效率较慢

LinkedList使用链表的方式实现，他的访问比较慢，但是他的插入删除的效率很快

18、ArrayList,Vector,LinkedList的存储性能和特性是什么？

*   *  ArrayList：使用动态数组的方式进行储存，当容量不够的时候会自动扩容到1.5倍。它的读取速度很快。
     *  Vector是线程安全的。但这个类已经过时了。他的性能比ArrayList差
     *  LinkedList使用双向链表进行储存，因为他的删除和插入的效率比较快

19、Collection 和 Collections的区别。

*   *    Conllection是一个集合类的顶级接口。
     *  Collections是一个集合的工具类，提供了一些静态的方法，对集合进行了排序，搜索等等

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

list添加用add方法，获取使用迭代器或者get（）方法

set添加用add方法，获取使用迭代器

map添加使用put方法，获取使用get

21. 怎么求两个集合的并集、交集、差集

并集：使用set，A.addAll(B)

交集：A.retaili（B）交集在集合A中

差集：去掉集合中包含另一个集合的值A.removeAll（B）。

[http_cmsblogs.com_cat_325]: http://cmsblogs.com/?cat=325