网站导航
> 文章列表 > 【面试必备】Java集合面试题全总结

【面试必备】Java集合面试题全总结

网友: 文章列表 2024-03-22 01:49:05

【面试必备】Java集合面试题全总结

文章目录

  • 集合
    • Collection
      • 集合概述
      • Collection子接口之List
      • Collection子接口之Set
      • Collection子接口之Queue
    • Map

集合

Collection

集合概述

  • Java集合由哪两大接口派生而来？

    • Collection接口，主要用于存放单一元素。下面有三个主要的子接口：List、Set、Queue。

      • Map接口：主要用于存放键值对。

  • List、Set、Queue、Map四者的区别？

    • List中存储有序、可重复元素。

    • Set中存储无序、不可重复元素。

    • Queue按照特定顺序进行排序，存储有序、可重复元素。

    • Map存储键值对。key是无序的，不可重复；value是无序的，可重复。

  • 如何选用集合？

    • 我们只需要存放元素值时，就选用Collection 接口的集合。
      • 保证元素唯一时选择实现Set接口的集合。不需要就选用List接口的集合。
    • 我们需要根据键值获取到元素值时就选用 Map 接口下的集合。
      • 需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。

  • 为什么要使用集合？

    保存多种类型相同的数据时就要用到集合。集合提高了数据存储的灵活性，不仅可以存储不同类型不同数量的对象，还可以保存具有映射关系的数据。

Collection子接口之List

  • ArrayList、Vector、LinkedList的区别？

    • 底层数据结构：ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储；Vector 是 List 的古老实现类，底层也是使用Object[ ] 存储；LinkedList底层使用双向链表进行存储。

    • 是否线程安全：ArrayList、LinkedList，线程不安全 ；Vector线程安全。

    • 插入和删除操作：ArrayList添加元素追加到末尾O(1)，追加到指定位置O(n - i)；LinkedList在头尾插入删除元素O(1)，指定位置O(n)，先移动到需要插入的位置再插入。

    • 快速随机访问：ArrayList还实现了RandomAccess接口，也就标识了ArrayList支持快速随机访问功能，也就是可以通过元素的序号快速获取元素对象(对应于get(int index)方法)。

  • 说一说ArrayList的扩容机制？

    • 简单版本：初次调用add方法，ArrayList默认的容量为10。扩容会调用grow()方法，将旧数组的容量右移一位，也就是扩容为1.5倍。

    • 复杂版本：以无参构造器创建ArrayList为例。

      首先调用add()方法，添加元素之前，会调用ensureCapacityInternal()方法，得到minCapacity的值。如果是第一次执行add方法，minCapacity为默认值10。

      之后调用ensureExplicitCapacity()方法【确保显式容量】，来判断是否需要扩容。如果minCapacity【随着调用add()方法增加】 - 数组长度 > 0 ，则说明当前数组长度不够用，需要调用grow()方法扩容。

      grow()方法内部首先获取旧的数组大小，右移一位，将新的数组大小扩容为原来的1.5倍。如果扩容后的大小还小于minCapacity，那么当前容量就设置为minCapacity。

      如果新容量大于MAX_ARRAY_SIZE，就比较旧容量和MAX_ARRAY_SIZE的大小，如果小于的话新容量大小则为 MAX_ARRAY_SIZE，否则即为Integer.MAX_VALUE。

Collection子接口之Set

  • comparable和Comparator的区别？

    • comparable 接口出自java.lang包。它有一个 compareTo(Object obj)方法用来排序

    • comparator接口出自 java.util 包。它有一个compare(Object obj1, Object obj2)方法用来排序

  • Set接口的无序性和不可重复性是什么？

    无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定。

    不可重复性是指添加的元素按照equals()判断时，返回false。需要重写equals()和hashCode()。

  • HashSet、LinkedHashSet、TreeSet三者异同？

    • 相同：三者都是线程不安全的，可以保证元素唯一。

    • 不同：HashSet底层使用哈希表；LinkedHashSet底层使用链表和哈希表，元素插入取出满足FIFO；TreeSet底层数据结构是红黑树，元素有序，可以使用自然排序和定制排序。

Collection子接口之Queue

  • Queue与Deque的区别？

    Queue是单端队列，Deque是双端队列，可以在队列的两端进行插入或删除元素。

  • ArrayDeque与LinkedList的区别？

    ArrayDeque 和 LinkedList 都实现了 Deque 接口。

    • ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。

    • ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。

    • ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。

    • ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

  • PriorityQueue了解多少？

    其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。而且优先级队列内部元素是自动依照元素的权值排列。PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据

    PriorityQueue默认是一个小顶堆，然而可以通过传入自定义的Comparator函数来实现大顶堆。

    堆是一个完全二叉树：

    • 大顶堆：每个结点的值都大于或等于左右子结点的值。优先级队列中，优先级高的在队头，使用了大顶堆，就是数字越大优先级越大。

    • 小顶堆：每个结点的值都小于或等于左右子结点的值。

    如下代码实现了一个初始大小为11的大顶堆。这里只是简单的传入一个自定义的Comparator函数，就可以实现大顶堆了。

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小顶堆，默认容量为11
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>(){ //大顶堆，容量11@Overridepublic int compare(Integer i1,Integer i2){return i2-i1;}
});//Java8语法：
PriorityQueue<int[]> maxpq = new PriorityQueue<>((int[] pair1, int[] pair2) -> { return pair2[1] - pair1[1];});

为什么i2 - i1 就是大顶堆了，降序排列了？

因为根据compare函数定义：

返回值返回一个负整数，表示第一个参数（i1）小于（<）第二个参数（i2）。

返回值返回一个正整数，表示第一个参数（i1）大于（>）第二个参数（i2）。

i2 - i1 ，比如返回的是正整数，说明i1 < i2 ，但是与函数定义矛盾，所以交换i1和i2位置，大的值（i1）放在小的值（i2）之前，就是第一个值大，第二个值小，降序。

i2 - i1，返回负整数，说明i2 < i1，也就是第一个值（i1）大，第二个值（i2）小，降序。

Map

  • HashMap 和 Hashtable的区别？

    • 线程安全：HashMap是线程不安全的，但是效率高。Hashtable是线程安全的。

      • HashMap的线程不安全，在1.8版本体现为会有数据覆盖的风险。

    • 存储null值：HashMap可以存储null值，Hashtable不可以存储null值。

    • 扩容机制：

      创建时不指定初始容量

      • HashMap默认初始化16，每次扩容，容量变为原来的2倍。

      • Hashtable默认初始化11，每次扩容，容量变为原来2n + 1。

      创建时指定了容量

      • HashMap扩充为原来的2的幂次方。

      • Hashtable使用指定容量。

  • HashMap和HashSet区别？

    HashSet底层基本就是基于HashMap实现的。

    • 实现接口：HashMap实现了Map接口，HashSet实现了Set接口。

    • 存储数据：HashMap存储K-V，HashSet存储对象。

    • 添加元素：HashMap调用put()添加元素，HashSet调用add()添加元素。

    • 计算hashcode：HashMap使用Key计算，HashSet使用对象计算。

  • HashMap和TreeMap区别？

    TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

    • 实现SortedMap接口，多了对集合中元素按照key排序的能力。

    • 实现NavigableMap（可导航的Map）接口，有了对集合内元素的搜索能力。

  • HashSet如何检查重复？

    HashSet通过add()方法返回值判断是否重复，实际上无论HashSet中是否存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。

  • HashMap的底层实现？

    HashMap map = new HashMap():

    以1.7版本为例，在实例化以后，底层创建了长度是16的一维数组Entry[] table。使用put方法放入k1 v1时：
    map.put(key1,value1):

    调用 key1 所在类的hashCode() 计算key1哈希值，此哈希值经过取余（n - 1 & hash == hash % n）计算以后，得到在Entry数组中的存放位置。

    • 如果此位置上的数据为空，key1-value1添加成功。
    • 如果此位置上的数据不为空，（意味着此位置上存在一个或多个数据（以链表形式存在）），比较key1和已经存在的一个或多个数据的哈希值：
      • 如果key1的哈希值与已经存在的数据的哈希值都不相同，则加入到链表中。
      • 如果产生hash冲突，继续比较：调用key1所在类的equals(key2) 方法，比较：
        • 如果equals()返回true，说明加入的就是一个东西，则使用value1替换value2。（equals相等，hashCode一定相等）
        • 如果equals()返回false：此时key1-value1添加成功。（因为即使hashCode相等，但equals不一定相等）

    当然，在不断的添加过程中，会涉及到扩容问题，当超出临界值（且要存放的位置非空）时，会进行扩容操作。默认扩容为原来容量的2倍，并将原有的数据复制过来。

    jdk8 相较于jdk7在底层实现方面的不同：

    • new HashMap():底层没有创建一个长度为16的数组，而是首次调用put()方法时，底层创建长度为16的数组

    • jdk 8底层的数组是：Node[]，而非Entry[]。

    • 形成链表时，七上八下（jdk7：新的元素指向旧的元素。jdk8：旧的元素指向新的元素）

    • 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所有数据改为使用红黑树存储。可以减少搜索的时间。

      • 为什么不用二叉查找树？

        TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

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

    1. 为了让数据均匀分布。根据key的hash值确认在数组中的位置时，如果n为2的幂次方，可以保证数据的均匀插入，这样可以减少hash冲突。
    2. 提高运算性能。计算得到的hash值，还要经过求余运算。如果长度是2的幂次，求余时可以使用二进制的&操作，就是hash&(length-1)。相较于使用%求余，效率更高。

  • HashMap多线程操作导致死循环问题？

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

    • Rehash：Hash表的尺寸和容量都非常重要（因为要避免hash碰撞），一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的无素都需要被重算一遍。这叫rehash，这个成本相当的大。

  • HashMap的常见遍历方式？

    Iterator方式遍历—EntrySet

    Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();while (iterator.hasNext()) {Map.Entry<Integer, String> entry = iterator.next();System.out.println(entry.getKey());System.out.println(entry.getValue());}

    Iterator方式遍历—KeySet

     Iterator<Integer> iterator = map.keySet().iterator();while (iterator.hasNext()) {Integer key = iterator.next();System.out.println(key);System.out.println(map.get(key));}

    forEach EntrySet / KeySet

    for (Map.Entry<Integer, String> entry : map.entrySet()) {System.out.println(entry.getKey());System.out.println(entry.getValue());}for (Integer key : map.keySet()) {System.out.println(key);System.out.println(map.get(key));}

    Stream

     map.entrySet().stream().forEach((entry) -> {System.out.println(entry.getKey());System.out.println(entry.getValue());});
//parallel：并行map.entrySet().parallelStream().forEach((entry) -> {System.out.println(entry.getKey());System.out.println(entry.getValue());});

  • ConcurrentHashMap 和 Hashtable 区别？

    • 首先肯定是底层的数据结构不相同：

      • ConcurrentHashMap在JDK1.7使用Segment数组 + 链表实现，JDK1.8之后采用哈希表 + 链表/红黑树，与HashMap相同。

      • Hashtable使用数组 + 链表的方式实现，链表主要为了解决哈希冲突。

    • 其实两者的区别主要体现在实现线程安全的方式不同：

      • JDK1.7中，ConcurrentHashMap使用Segment（段） 数组，每一个数组中包含一个HashEntry，HashEntry就是使用链表实现的。每一把锁只锁一个数据段的内容，多线程访问不同的数据段，不会存在资源的竞争问题。这样并发效率比较高。

        JDK1.8中，ConcurrentHashMap使用Node数组 + 链表/红黑树，并发访问控制使用synchronization和CAS来操作。

      • Hashtable使用synchronized来保证线程安全，效率很低。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

  • ConcurrentHashMap线程安全的具体实现方式？

    JDK1.8之前

    ConcurrentHashMap将数据分为一段一段（Segment）的存储，然后把每一段数据配一把锁，当一个线程占用锁访问段数据，其他段数据可以被其他线程访问。

    ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

    • Segment

      Segment 继承了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

      一个 ConcurrentHashMap里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

      Segment 的结构和 HashMap类似，是一种数组和链表结构，一个 Segment包含一个 HashEntry 数组

    • HashEntry

      每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

    JDK1.8

    Java 8 几乎完全重写了 ConcurrentHashMap。取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

    • CAS是compare and swap的缩写，即我们所说的比较交换。cas是一种基于锁的操作，而且是乐观锁。

      CAS有三个操作数----内存对象（V）、预期原值（A）、新值（B）。CAS原理就是对v对象进行赋值时，先判断原来的值是否为A，如果为A，就把新值B赋值到V对象上面，如果原来的值不是A（代表V的值放生了变化），就不赋新值。CAS是自循环的。

    Java 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

  • JDK 1.7 和 1.8 的ConcurrentHashMap 实现有什么不同？

    • 线程安全实现方式 ：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。

    • Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。

    • 并发度 ：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

网络标签：

相关问题