【面试】2021秋招后总结的集合框架的知识我掏出来了（一把辛酸泪）

女爷i 2021-07-24 13:54 211阅读 0赞

> 我每天都努力一点,这样会离满意的offer更近一点吧!!

### 文章目录 ###

*  1.一定要了解集合框架的类层次结构
 *  2.List、Set、Map各有什么特点？
 *  3.剖析ArrayList的源码
 *  4.Vector和ArrayList的区别和联系？
 *  5.Java 的 HashMap 和 Hashtable 有什么区别 HashSet 和HashMap 有什么区别？使用这些结构保存的数需要重载的方法是哪些？
 *  6.使用ArrayList和LinkedList在尾部插入元素哪个快？
 *  7.treeMap 和 TreeSet 在排序时如何比较元素？Collections工具类中的 sort()方法如何比较元素？
 *  8.如果要使用一个线程安全的集合类，你会选择？
 *  9.合并两个链表。（我遇到的面试题之一）
 *  10.数组和集合的区别
 *  11.迭代器Iterator是什么？怎么使用迭代器？
 *  12.如何遍历集合?
 *   *  追问，三种变量集合的方式适用什么场景
 *  13.在ArrayList中如何安全的删除一个元素?
 *  14.Iterator 和 ListIterator 有什么区别？
 *  15. HashMap的底层如何实现?HashMap在JDK1.7和JDK1.8有什么区别?

# 1.一定要了解集合框架的类层次结构 #

![image-20201104221631975][]

*  要注意面试题中描述的细节:到底是继承还是实现
    
     *  比如HashMap继承于Map就是错误的描述
 *  注意List 和Set实现了Collection接口

# 2.List、Set、Map各有什么特点？ #

List 接口存储一组不唯一，有序（插入顺序）的对象。

Set 接口存储一组唯一，无序的对象。

Map 接口存储一组键值对象，提供 key 到 value 的映射。key 无序，唯一。

value 不要求有序，允许重复。（如果只使用 key 存储，而不使用 value，那

就是 Set）。

# 3.剖析ArrayList的源码 #

*  如何扩容的？
    
     *  扩容为原来的1.5倍
 *  ArrayList在构造时可以指定创建的大小，如果不指定那么默认创建的大小是16

# 4.Vector和ArrayList的区别和联系？ #

*  两者都是可自动扩容的数组，实现的功能也基本相似
 *  区别就是Vector是线程安全的，ArrayList不是线程安全的，但是ArrayList的效率比Vector的效率更高

# 5.Java 的 HashMap 和 Hashtable 有什么区别 HashSet 和HashMap 有什么区别？使用这些结构保存的数需要重载的方法是哪些？ #

**答：**

HashMap 与 Hashtable 实现原理相同，功能相同，底层都是哈希表结构，查询速度快，在很多情况下可以互用

两者的主要区别如下

1、Hashtable 是早期 JDK 提供的接口，HashMap 是新版 JDK 提供的接口

2、Hashtable 继承 Dictionary 类，HashMap 实现 Map 接口

3、Hashtable 线程安全，HashMap 线程非安全

4、Hashtable 不允许 null 值，HashMap 允许 null 值

HashSet 与 HashMap 的区别

1、HashSet 底层是采用 HashMap 实现的。HashSet 的实现比较简单，HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此HashSet 和 HashMap 两个集合在实现本质上是相同的。

2、HashMap 的 key 就是放进 HashSet 中对象，value 是 Object 类型的。

3、当调用 HashSet 的 add 方法时，实际上是向 HashMap 中增加了一行(key-value 对)，该行的 key 就是向 HashSet 增加的那个对象，该行的value 就是一个 Object 类型的常量

# 6.使用ArrayList和LinkedList在尾部插入元素哪个快？ #

这个题有一个比较大的坑。

# 7.treeMap 和 TreeSet 在排序时如何比较元素？Collections工具类中的 sort()方法如何比较元素？ #

答：TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，该接口提供了比较元素的 compareTo()方法，当插入元素时会回调该方法比较元素的大小。

TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进行排序。Collections 工具类的 sort 方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是 Comparator 接口的子类型（需要重写 compare 方法实现元素的比较），相当于一个临时定义的排序规则，其实就是是通过接口注入比较元素大小的算法，也是对回调模式的应用。

# 8.如果要使用一个线程安全的集合类，你会选择？ #

Vector是一个线程安全的集合，但是Vector已经被淘汰不推荐使用，如果要多个线程同时操作一个容器对象，我们可以使用ArrayList或者LinkedList，其本身不是线程安全的，我们将其传入Collections中的synchroniezed方法将其转换为一个线程安全的集合。其实这就是装饰模式的实际应用。（将已有对象传入另一个类的构造器中，创造的新对象来增强原对象的功能）。

List<String> synchronizedList = Collections.synchronizedList(list);
    synchronizedList.add("aaa");
    synchronizedList.add("bbb");
    
    for (int i = 0; i < synchronizedList.size(); i++) { 
        System.out.println(synchronizedList.get(i));
    }

# 9.合并两个链表。（我遇到的面试题之一） #

public class Solution { 
    	public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
    		if (l1 == null || l2 == null) {  
     			return l1 != null ? l1 : l2; 
    		} 
    		ListNode head = l1.val < l2.val ? l1 : l2; 
     		ListNode other = l1.val >= l2.val ? l1 : l2; 
    		ListNode prevHead = head; 
     		ListNode prevOther = other; 
     		while (prevHead != null) {  
     			ListNode next = prevHead.next; 
    			if (next != null && next.val > prevOther.val) {  
     			prevHead.next = prevOther; 
    			prevOther = next; 
     			} 
     			if(prevHead.next==null){  
     				prevHead.next=prevOther; 
     				break; 
     			} 
     			prevHead=prevHead.next; 
     		}
            return head; 
        }
    }

# 10.数组和集合的区别 #

1.  最大区别就是数组的大小的固定的,而集合的大小是可以动态增长的。
2.  集合维护着比较好的数据结构和算法，提高了代码执行的速度。

# 11.迭代器Iterator是什么？怎么使用迭代器？ #

迭代器Iterator提供了遍历任何Collection接口的方法，可以使用迭代器来遍历Collection接口的实现类。

使用迭代器。

List<Integer> list  = new ArrayList<Integer>();
    Iterator it = list.itator();
    while(is.hasNext()){ 
        Integer num = it.next();
    }

# 12.如何遍历集合? #

遍历集合有三种方式:

1.  for loop遍历
2.  foreach遍历
3.  使用迭代器遍历

第一种方式:使用for loop遍历,我们需要自己在外部维护一个变量,然后依次读取到每个位置的元素

特点就是：比较熟悉的遍历的操作方法

for(int i = 0; i < list.size(); ++i) { 
        list.get(i);
    }

第二种方式遍历: foreach方式遍历

特点：简洁

for(Integer num : list){ 
        
    }

*  注意使用foreach的方式遍历集合时,不能对集合中的元素进行(删除、替换)操作。

第三种方式遍历：使用迭代器变量，特点就是不论什么集合，都是可以使用迭代器进行遍历的。

## 追问，三种变量集合的方式适用什么场景 ##

1、传统的for循环遍历，基于计数器的：  
顺序存储：读取性能比较高。适用于遍历顺序存储集合。  
链式存储：时间复杂度太大，不适用于遍历链式存储的集合。  
2、迭代器遍历，Iterator：  
顺序存储：如果不是太在意时间，推荐选择此方式，毕竟代码更加简洁，也防止了Off-By-One的问题。  
链式存储：意义就重大了，平均时间复杂度降为O(n)，还是挺诱人的，所以推荐此种遍历方式。  
3、foreach循环遍历：  
foreach只是让代码更加简洁了，但是他有一些缺点，就是遍历过程中不能操作数据集合（删除等），所以有些场合不使用。而且它本身就是基于Iterator实现的，但是由于类型转换的问题，所以会比直接使用Iterator慢一点，但是还好，时间复杂度都是一样的。所以怎么选择，参考上面两种方式，做一个折中的选择。

# 13.在ArrayList中如何安全的删除一个元素? #

拿到这道题的时,我们首先会想到,要删除一个元素，那么先要遍历找到这个元素，那么该选择三种遍历方式中的哪一个呢?  
![image-20201105231603384][]

首先不能使用foreach的,因为foreach遍历时不能操作集合元素。

这时可能就会按照平常遍历的老路子想着使用for loop遍历，然后在遍历中删除元素。先看看代码分析一下：

for(int i = 0 ; i < list.size();++i) { 
        //伪代码哈 哈哈哈,我比较懒
        list.remove(...);
    }

分析一下:当我们遍历集合元素时,如果当前的集合元素不是我们需要删除的集合元素,那么就什么也不会发生,假如我们找到的集合元素是我们要删除的集合元素,那么就会调用remove方法删除该元素,听起来逻辑是通顺的，但是会出错。我贴一下源码，细心的人会发现问题出现在哪里。

public E remove(int index) { 
        rangeCheck(index);
    
        modCount++;
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }

public boolean remove(Object o) { 
        if (o == null) { 
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) { 
                    fastRemove(index);
                    return true;
                }
        } else { 
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) { 
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    
    /* * Private remove method that skips bounds checking and does not * return the value removed. */
    private void fastRemove(int index) { 
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

确实,我们在remove时，不仅删除了该元素，`并且在删除之后该集合的size-1`，这时就发生出错。

综上所述，我们需要安全删除一个集合的元素时，需要借助迭代器的remove方法。(此处省略了迭代器删除元素的方法,因为迭代的使用方法已经在上面有说)

*  另外再提一嘴,因为remove是一个重载的方法,两个方法的参数列表是不同的,我们一定要在使用时,特别确切的知道传入该方法的参数是一个对象还是一个int数值的索引。

# 14.Iterator 和 ListIterator 有什么区别？ #

*  Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List。
 *  Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前/后遍历）。
 *  ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

# 15. HashMap的底层如何实现?HashMap在JDK1.7和JDK1.8有什么区别? #

在Java中，保存数据有两种比较简单的数据结构：数组和链表。**数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法**的方式可以解决哈希冲突。

在JDK1.7时,我们采用的是拉链法解决Hash冲突的。

![image-20201105224650594][]

相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

*  记住这个阈值啊，好多面试官会问。

当然关于链表的知识和红黑树的原理也要掌握。（这里我又想到了之前自己写的数据库索引时，也说数据库的索引也用到了红黑树，害，图论真的太重要了）。

![image-20201105230927295][]

除了这些，其实在JDK1.8中对于哈希函数也做了优化，让哈希冲突出现的几率变的更低。

static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
    }

说数据库的索引也用到了红黑树，害，图论真的太重要了）。

![image-20201105231942359][]  
![image-20201105230927295][]

除了这些，其实在JDK1.8中对于哈希函数也做了优化，让哈希冲突出现的几率变的更低。

static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
    }

总结:  
集合框架的知识比较多,但是如何深入到源码,自己理清思路,其实不会忘,而且会记忆的比较深刻。

[image-20201104221631975]: /images/20210724/0595af3523a24c19b2d919b9fc33b548.png
[image-20201105231603384]: /images/20210724/6ec3fa75efdb458c9d3043562155faa0.png
[image-20201105224650594]: /images/20210724/f3b4aad6709e4fbbaba46555c3c5ac9f.png
[image-20201105230927295]: /images/20210724/fa78116ce9f34db08649b3938b896152.png
[image-20201105231942359]: /images/20210724/699325478f0f4a37847ffc919d945d12.png