Javase--集合面试题收集

作者: 流年划破容颜_cc55 | 来源:发表于2018-08-05 21:05 被阅读58次

Java 中常见集合

集合这方面的考察相当多，这部分是面试中必考的知识点。

1）说说常见的集合有哪些吧？

1 Collection接口的子接口包括：Set接口和List接口
2 Map接口的实现类主要有：HashMap、TreeMap、Hashtable、
ConcurrentHashMap以及Properties等
3 Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
4 List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

2）HashMap和Hashtable的区别有哪些？（必问）

答：

HashMap没有考虑同步，是线程不安全的；Hashtable使用了synchronized关键字，是线程安全的；
前者允许null作为Key；后者不允许null作为Key

3）HashMap的底层实现你知道吗？

答：在Java8之前，其底层实现是数组+链表实现，Java8使用了数组+链表+红黑树实现。此时你可以简单的在纸上画图分析：

image.png

4）ConcurrentHashMap 和 Hashtable 的区别？（必问）

答：ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 将 hash 表分为 16 个桶（默认值），诸如get,put,remove 等常用操作只锁当前需要用到的桶。

5）HashMap 的长度为什么是2的幂次方？

答：

通过将 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 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

6）List和Set的区别是啥？

答：List元素是有序的，可以重复；Set元素是无序的，不可以重复。

7）List、Set和Map的初始容量和加载因子：

答：

1. List

ArrayList的初始容量是10；加载因子为0.5；扩容增量：原容量的 0.5倍+1；一次扩容后长度为15。

Vector初始容量为10，加载因子是1。扩容增量：原容量的 1倍，如 Vector的容量为10，一次扩容后是容量为20。

2. Set

HashSet，初始容量为16，加载因子为0.75；扩容增量：原容量的 1 倍；如 HashSet的容量为16，一次扩容后容量为32

3. Map

HashMap，初始容量16，加载因子为0.75；扩容增量：原容量的 1 倍；如 HashMap的容量为16，一次扩容后容量为32

8)Comparable(方式一)接口和Compartor（方式二）接口的比较：

两种方法各有优劣, 用Comparable 简单, 只要实现Comparable 接口的对象直接就成为一个可以比较的对象,但是需要修改源代码。

用Comparator 的好处是不需要修改源代码, 而是另外实现一个比较器, 当某个自定义的对象需要作比较的时候,把比较器和对象一起传递过去就可以比大小了, 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑,使其

可以匹配一些比较简单的对象,那样就可以节省很多重复劳动了。

9）Java集合的快速失败机制 “fail-fast”

答：

是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。

例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。

原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

10）ArrayList 和 Vector 的区别

答：

这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合，即存储在这两个集合中的元素位置都是有顺序的，相当于一种动态的数组，我们以后可以按位置索引来取出某个元素，并且其中的数据是允许重复的，这是与 HashSet 之类的集合的最大不同处，HashSet 之类的集合不可以按索引号去检索其中的元素，也不允许有重复的元素。

ArrayList 与 Vector 的区别主要包括两个方面：

同步性：

Vector 是线程安全的，也就是说它的方法之间是线程同步（加了synchronized 关键字）的，而 ArrayList 是线程不安全的，它的方法之间是线程不同步的。如果只有一个线程会访问到集合，那最好是使用 ArrayList，因为它不考虑线程安全的问题，所以效率会高一些；如果有多个线程会访问到集合，那最好是使用 Vector，因为不需要我们自己再去考虑和编写线程安全的代码。

数据增长：

ArrayList 与 Vector 都有一个初始的容量大小，当存储进它们里面的元素的个人超过了容量时，就需要增加 ArrayList 和 Vector 的存储空间，每次要增加存储空间时，不是只增加一个存储单元，而是增加多个存储单元，每次增加的存储单元的个数在内存空间利用与程序效率之间要去的一定的平衡。Vector 在数据满时（加载因子1）增长为原来的两倍（扩容增量：原容量的 1 倍），而 ArrayList 在数据量达到容量的一半时（加载因子 0.5）增长为原容量的 0.5 倍 + 1 个空间。

面试官：那 ArrayList 和 LinkedList 的区别呢？

答：

LinkedList 实现了 List 和 Deque 接口，一般称为双向链表；
LinkedList 在插入和删除数据时效率更高，ArrayList 在查找某个 index 的数据时效率更高；
LinkedList 比 ArrayList 需要更多的内存；

面试官：Array 和 ArrayList 有什么区别？什么时候该应 Array 而不是 ArrayList 呢？

答：它们的区别是：

Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
Array 大小是固定的，ArrayList 的大小是动态变化的。
ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator() 等等。
对于基本类型数据，集合使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。

11）如何去掉一个 Vector 集合中重复的元素？
答：

Vector newVector = new Vector();
for (int i = 0; i < vector.size(); i++) {
    Object obj = vector.get(i);
    if (!newVector.contains(obj)) {
        newVector.add(obj);
    }
}

还有一种简单的方式，利用了 Set 不允许重复元素的特性：

HashSet set = new HashSet(vector);

Set里的元素是不能重复的，那么用什么方法来区分重复与否呢? 是用==还是equals()?

我们知道Set集合实际大都使用的是Map集合的put方法来添加元素。

以HashSet为例，HashSet里的元素不能重复，在源码(HashMap)是这样体现的：

// 1\. 如果key 相等  
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
// 2\. 修改对应的value
   if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
   }

添加元素的时候，如果key(也对应的Set集合的元素)相等，那么则修改value值。而在Set集合中，value值仅仅是一个Object对象罢了(该对象对Set本身而言是无用的)。

也就是说：Set集合如果添加的元素相同时，是根本没有插入的(仅修改了一个无用的value值)！从源码(HashMap)中也看出来，==和equals()方法都有使用！

Collection和Collections的区别

Collection是集合的上级接口，继承它的有Set和List接口
Collections是集合的工具类，提供了一系列的静态方法对集合的搜索、查找、同步等操作

七、Enumeration和Iterator接口的区别

这个我在前面的文章中也没有详细去讲它们，只是大概知道的是：Iterator替代了Enumeration，Enumeration是一个旧的迭代器了。

与Enumeration相比，Iterator更加安全，因为当一个集合正在被遍历的时候，它会阻止其它线程去修改集合。

我们在做练习的时候，迭代时会不会经常出错，抛出ConcurrentModificationException异常，说我们在遍历的时候还在修改元素。
这其实就是fail-fast机制~具体可参考博文：https://blog.csdn.net/panweiwei1994/article/details/77051261

区别有三点：

Iterator的方法名比Enumeration更科学
Iterator有fail-fast机制，比Enumeration更安全
Iterator能够删除元素，Enumeration并不能删除元素
八、ListIterator有什么特点

ListIterator继承了Iterator接口，它用于遍历List集合的元素。
ListIterator可以实现双向遍历,添加元素，设置元素

image.png

Java中HashMap的key值要是为类对象则该类需要满足什么条件？

需要同时重写该类的hashCode()方法和它的equals()方法。

从源码可以得知，在插入元素的时候是先算出该对象的hashCode。如果hashcode相等话的。那么表明该对象是存储在同一个位置上的。
如果调用equals()方法，两个key相同，则替换元素
如果调用equals()方法，两个key不相同，则说明该hashCode仅仅是碰巧相同，此时是散列冲突，将新增的元素放在桶子上
一般来说，我们会认为：只要两个对象的成员变量的值是相等的，那么我们就认为这两个对象是相等的！因为，Object底层比较的是两个对象的地址，而对我们开发来说这样的意义并不大~这也就为什么我们要重写equals()方法

重写了equals()方法，就要重写hashCode()的方法。因为equals()认定了这两个对象相同，而同一个对象调用hashCode()方法时，是应该返回相同的值的！