集合常见面试题

# 集合常见面试题

# Java 集合概览

Java集合，是由两个接口派生而来。一个是Collection，用来存放单一元素；一个是Map用来存放键值对。

他们的关系如图所示。

20230220014110

# 说说List,Set,Queue,Map四者的区别？

List 元素顺序，可重复
Set 元素无需，不可重复
Queue 元素按照特定的排队规则确定先后顺序，存储的元素是有序的、可重复的
Map 使用键值对，是搜索的专家，无序、元素不可以重复

# 集合框架底层结构总结

# List

ArrayList： Object[] 数组
Vector： Object[]数组
LinkedList：双向链表

# Set

HashSet 无序，基于HashMap来保存元素
LinkedHashSet 是HashSet的子类，它内部是基于LinkedHashMap实现的
TreeSet 有序，唯一，是使用红黑树实现的

# Queue

PriorityQueue： Object[]数组来实现二叉堆
ArrayQueue： Object[] 数组+ 双执政

# Map

HashMap JDK1.8之前是由数组+链表组成的，数组是HashMap的主题，链表则是主要为了解决哈希冲突而存在的。JDK1.8过后，当链接长度大于阈值（64），默认会将他转成红黑树。
LinkedHashMap 继承于HashMap，所以底层基本是一样的，但是增加了一条双向链表，是的上面的结构可以保持键值对的插入顺序。
Hashtable 数组+链表组成，数组是Hashtable的主题，链表则是主要为了解决哈希冲突而存在的
TreeMap 红黑树（白平衡的排序二叉树）

# Collection子接口值List

# ArrayList和Vector的区别

ArrayList是List最主要的实现类，使用Object[]存储，适合频繁查找工作，线程不安全。
Vector是List的古老实现类，线程安全，不过现在很少用了

# ArrayList于LinkedList区别？

他们都不是线程安全的
底层数据结构，一个是Object数组，一个是双向链表
ArrayList插入和删除元素的时间复杂度受元素位置影响，LinkedList则不会。
ArrayList支持随机访问，LinkedList则不支持。

# ArrayList的扩容机制

新建的时候是空数组，然后到达容量之后，就会扩容到一点五倍

# Collection子接口值Set

# comparable 和 Comparator 的区别

        // 定制排序的用法
        Collections.sort(arrayList, new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

1
2
3
4
5
6
7
8

public  class Person implements Comparable<Person> {
  //省略

 /**
     * T重写compareTo方法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Map接口

HashMap线性不安全，hashTable线性安全。但是效率很低，想要线性安全就使用ConcurrentHashMap

HashMap默认大小为16，如果扩容了就会成为原来的两倍，HashMap在链表长度大于阈值的时候，会将链表转为红黑树。（在转换前会进行判断，如果当前数组的长度小于64，会选择先进行数组扩容，以减少搜索时间。）

# HashMap和HashSet的区别。

HashSet底层时基于HashMap的，它只存储对象，通过hashCode判断是否相等，如果相等的话，就继续判断equals是否相等。都相等的话，就会判断这个对象是相等的。

# HashMap和TreeMap的区别

TreeMap很少用。它对比HashMap，有着搜索、排序的功能。

NavigableMap 提供搜索能力

SortedMap 提供根据key排序的能力。

以下是TreeMap的一些API

get() - 返回与指定键关联的值。如果找不到键，则返回null。
getOrDefault() - 返回与指定键关联的值。如果找不到键，则返回指定的默认值。
remove(key) - 返回并从TreeMap中删除与指定键关联的条目
remove(key, value) -仅当指定键与指定值相关联时才从映射中删除条目，并返回布尔值
firstKey() - 返回map的第一个键
firstEntry() - 返回映射的第一个键的键/值映射
lastKey() - 返回map的最后一个键
lastEntry() - 返回映射的最后一个键的键/值映射
HigherKey() - 返回大于指定键的那些键中的最小的键。
HigherEntry() - 返回与所有大于指定键的键中最小的键相关的条目。
lowerKey() - 返回所有小于指定键的最大键。
lowerEntry() - 返回与所有小于指定键的键中最大的键关联的条目。
ceilingKey() - 返回大于指定键的那些键中的最小的键。如果映射中存在作为参数传递的键，则它将返回该键。
ceilingEntry() - 返回与大于指定键的那些键中最小的键相关的条目。如果映射中存在与传递给自变量的键关联的条目，则返回与该键关联的条目。
floorKey() - 返回小于指定键的那些键中最大的键。如果存在作为参数传递的键，它将返回该键。
floorEntry() - 返回与小于指定键的那些键中最大的键相关的条目。如果存在作为参数传递的键，它将返回该键。

综上，相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

# HashSet如何检查重复？

1.8的时候已经不检查了，在add()的时候，依托map的能力，无论重复不重复都会插进去，只是会反馈一个插入成功与否的标识符。

# HashMap的底层逻辑？

再问1.7版本怎么实现的就不礼貌了。2023年了，谁还tm的用1.7？

说1.8的

HashMap底层数据结构就是一个数组加链表。首先是通过Key计算hashCode，然后放在（n-1）& hash的位置。如果当前位置已经有元素了。就通过判断value的hash以及key是否相同，如果相同就覆盖掉。不想用就通过拉链法解决冲突。

所谓拉链法，就是这样，将数组和链表结合，当有冲突的时候，就放进链表里面。

但是如果链表太长了，在1.8会将链表转为红黑树

#Java

上次更新: 2023/04/10, 17:41:57

← 基础概念与常识 IO常见知识点→