Java集合框架面试题（更新中）

Created2021-12-19Updated2021-12-19

说出 collection 的常用子接口？说出 3 个以上的常 用方法？都有什么作用？

1. Collection具有两个比较常用的子接口，List和Set;
2. Collection中的常用方法
在这里插入图片描述

1、添加

Boolean add(E e):在集合中添加一个对象，如果添加成功，返回true，如果失败，返回false

Boolean addAll(Collection<?extend E> e)：在集合中添加另一个集合，成功true,失败false;

2、删除
Boolean remove(object obj):删除一个对象,会改变集合的长度

Boolean removeAll(Colleciton con);删除一个集合，还有两个集合中相同的元素

void clear():删除所有

3、判断
Boolean contains(object obj):在集合中是否包含指定的对象

Boolean containsAll(Collection con):在集合是否包含另一个集合

Boolean isEmpty( )：判断集合是否为空

4、获取

int size( )：得到集合的尺寸大小 数组:length 字符串:length( );

Iterator iterator( )：取出元素的方式。迭代器。该对象必须依赖于绝缘体容器，因为每一个容器的数据结构都不同。所以该迭代器对象是在容器中进行内部实现的，对于使用容器者而言，绝缘体的实现不重要，只要通过容器获取到该实现的迭代器的对象即可，也就是iterator方法，Iterator接口就是对所有的collection容器进行元素取出的公共接口。将每一个容器中的取出方式进行了封装，并对外暴露，这样无论是什么容器或者数据结构，只要内部取出方式实现了Iterator接口，都可以通过该接口取出这些容器中的元素。他的出现，将容器的取出方式和容器的数据结构相分离，降低了耦合性，而取出方式因为直接在访问容器的元素，并依赖具体的数据结构，所以被定义在了容器中。通过内部类来实现Iterator接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
Collection c = new ArrayList();

c.add("hello");

Iteratot it = c.iterator();//返回的是Iterator的子类对象

while(it.hasNext()){

String str = (String)it.next();

System.out.println(str);

}

for(object obj:con)用于数组和集合(高级for循环)

注意：迭代要强转，只能有一个next( )方法，否则会有NoSuchElementException异常。

5、交集

boolean retainAll(Collection c)：返回两个集合的交集元素，删除其他元素，功能和removeAll相反。有A,B两个集合，做完交集后，A集合中的元素发生变化，取得是A和B相同的元素，B不变化。boolean值的问题-------->只要A集合变化,那么返回true.否则false

6、集合转数组

Object[ ] toArray()：把集合转换成对象。

如果向 TreeSet 中加入类对象，需要做什么？

实现Comparable接口重写compareTo方法或者在TreesSet创建对象时传入自定义的比较类

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

从它俩的区别谈起，==是用来判断两者是否是同一对象（同一事物），而equals是用来判断是否引用同一个对象。再看一下Set里面存的是

对象，还是对象的引用。根据java的存储机制可知，set里面存放的是对象的引用，所以当两个元素只要满足了equals()时就已经指向同一个对象，

也就出现了重复元素。所以应该用equals()来判断。

ArrayList 和 Vector 的区别？

1.ArrayList是线程不安全的，Vector是线程安全的
2.ArrayList扩容是原来一半，Vector是原来的一倍

集合当中能存放基本数据类型的数据吗？

Java集合不能存放基本数据类型，只能存放对象的引用。

每个集合元素都是一个引用变量，实际内容都存放在堆内或方法区里面，

但是基本数据类型是在栈内存上分配空间的，栈上的数据随时会被收回。

如何解决？

可以通过包装类，把基本数据类型转化为对象类型，存放引用。

更方便的，由于有了自动拆箱和装箱功能，基本数据类型和其对应对象

之间的转换变得很方便，把基本数据类型存入集合中可以自动存，系统

会自动将其装箱成封装类，然后将其加入到集合当中。

ArrayList 与数组的区别?

Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。

Array大小是固定的，ArrayList的大小是动态变化的。

java 集合框架的四种主要接口是

Collection：存储无序的、不唯一的数据；其下有List和Set两大接口。

List：存储有序的、不唯一的数据；

Set：存储无序的、唯一的数据；

Map：以键值对的形式存储数据，以键取值。键不能重复，但值可以重复。

HashMap 和 Hashtable 的区别?

1 HashMap不是线程安全的

HashMap是map接口的子类，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap允许null key和null value，而hashtable不允许。

2 HashTable是线程安全。

HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率上可能高于Hashtable。

HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。 HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。 Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。 最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。 Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差

Collection 框架中实现比较方法

Java集合框架中需要比较大小的集合包括TreeMap、TreeSet，其中TreeMap会根据key-value对中key的大小进行排序，而TreeSet则会对集合元素进行排序。
因此TreeMap的key、TreeSet的集合元素，都需要可以比较大小。集合框架中之比较大小的有两种方式：

A．自然排序：对于自然排序来说，要求TreeMap中的所有key都实现Comparable接口，实现该接口时需要实现一个int compareTo(T o)方法，用于判断当前对象与o对象之间的大小关系。如果该方法返回正整数，则说明当前对象大于o对象；如果该方法返回0，说明两个对象相等；如果该方法返回负整数，则说明当前对象小于o对象；JDK的很多类都已经实现了Comparable接口，例如String、Date、BigDecimal等。

B．定制排序：定制排序需要在创建TreeMap或TreeSet时传入一个Comparator对象，此时TreeMap或TreeSet不再要求key、集合元素本身是可比较大小的，而是由Comparator来负责比较集合元素的大小。Comparator本身只是一个接口，因此创建Comparator对象只能是创建它的实现类的对象，Comparator的实现类需要实现int compare(T o1, T o2)方法，该方法用于判断o1、o2两个对象的大小，如果该方法返回正整数，则说明o1大于o2、如果该方法返回负整数，则说明o1小于o2、如果返回0，则说明两个对象相等。

在 Java 中，HashMap 中是用哪些方法来解决哈希冲突的？

解决哈希冲突的方法有三种,分别是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
```再散列法(二次哈希法)```:再次使用一个不同的哈希算法再计算一次 (第一次%16换另一个数进行%运算)
```链地址法(拉链法)```:将所有冲突元素按照链表存储,冲突后时间复杂度变为O(1+n)n为冲突元素个数)[hashMap就是用这种方法]

**首先来了解一下什么是哈希表**

哈希表是以(Key,Value):数值的形式存储数据的

根据相应的哈希算法计算key,返回值即为V存储的数组下标

哈希算法:f(K) --- . int即为V需要存储的数组下标

**为什么会造成哈希冲突呢?**

用一个数去模运算,取得余数就是所要存储数组数据的下标,但是余数可能会存在一样的,这样就导致一样余数的户数无处存储,所以就造成了哈希冲突.

**哈希冲突解决思路:**

哈希算法计算的两个不同对象的哈希值相等的情况

> eg:1 % 16 == 17 % 16[1和17是不同的key值]--->就是哈希冲突了

HashMap中用链地址法来解决 

HashMap源码解析(负载因子,树化策略,内部hash实现,resize策略...)
HashMap中的内部属性:

负载因子:final loadFactor (默认为0.75f)
实际容量: int threshold = loadFactor * tab.length
树化阈值:int TREEIFY_THRESHOLD = 8;
解除树化阈值: int UNTREEIFY_THRESHOLD = 6;
HashMap也采用了懒加载策略,第一次put时初始化哈希表
树化逻辑:索引下标对应的链表长度达到阈值8并且当前哈希表长度达到64才不会树化,否则只是调用resize()方法进行哈希表扩容
resize();扩容为原先数组的2倍
负载因子大小怎么决定?

负载因子过大会导致哈希冲突明显增加,节省内存

负载因子过小会导致哈希表频繁扩容,内存利用率低

 默认0.75,0.75是一个经过计算得出的值,即能保证哈希冲突不会太严重也能保证效率不会太低

源码: 

```java
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
 
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

可以发现源码中并没有直接使用Object中的hashCode方法,而是再让h无符号右移了16位

为何不直接使用Object提供的hashCode?

为了将哈希码保留一半,将高低位都参与运算,减少内存开销,减少哈希冲突

直接使用会造成空间浪费

(h = key.hashCode()) ^ (h >>> 16); //32 —>16 保留一半(原本32右移16位去掉了一半)

put内部逻辑:

1.哈希表索引下标计算:

i = (n-1) & hash //与运算

保证求出的索引下标都在哈希表的长度范围之内

2.n为哈希表的长度

n必须为2 的n次方,保证哈希表中的所有索引下标都会被访问到

若n=15,则以下位置永远不可能存储元素

0011,0101,1001,1011,1101,1111

接下来再看源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
//第一次put值的时候将哈希表初始化
//resize():1,完成哈希表的初始化  2.完成哈希表的扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
//当目标索引未存储元素时,将当前元素存储到目标索引位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
//哈希表已经初始化并且算出的数据下标已经有元素了
    else {
        Node<K,V> e; K k;
//若索引下标对应的元素key值恰好与当前元素key值相等且不为空,
//将value替换为当前元素的value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
//此时索引对应的链表已经树化了,采用红黑树方式将当前节点添加到树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//以链表方式将当前节点添加到链表末尾
        else {
            for (int binCount = 0; ; ++binCount) { //binCount当前链表的长度
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //尝试将链表树化
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
//扩容策略
//此时添加了新节点
    if (++size > threshold)
        //扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

为何HashMap中JDK1.8要引入红黑树?

当链表长度过长时,会将哈希表查找的时间复杂度退化为O(n),树化会保证即便在哈希冲突严重时,查找的时间复杂度也为O(logn)

当红黑树结点个数在扩容或者删除元素时减少为6以下,在下次resize()过程中会将红黑树退化为链表,节省空间

Collection 和 Collections 的区别?

1、Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
2、Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。