1 Java集合概述

1.1 集合的分类

• 除了 Map 大类， 其他容器类都实现了 Collection 接口

1.2 List、Set、Map的区别

• List：保存的元素是可重复、有序的。
• Set：保存的元素是不可重复、无序的。
• Map：使用Key-Value存储，Key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

1.3 容器结构的底层实现

• List
  • ArrayList：**Object[]**，List的常见实现类，线程不安全。
  • Vector：**Object[]**，List的古老实现类，线程安全。
  • LinkedList：双向链表，JDK7之前采用双向循环链表
• Set
  • HashSet：基于HashMap实现。
  • LinkedHashSet：基于LinkedHashMap实现。
• Map
  • HashMap：DK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。是Map的常见实现类，线程
  • HashTable：数组+链表，Map的古老实现类，线程安全。
  • LinkedHashMap：在HashMap的基础上增加了一个双向链表，用来记录键值对的插入顺序，通过链表实现了访问顺序的相关逻辑
  • TreeMap：红黑树。

2 List

2.1 ArrayList和Vector的区别

• ArrayList是List的主要实现类，底层采用Object[]存储，线程不安全，效率高。
• Vector是List的古老实现类，底层采用Object[]存储，线程安全，效率低。

2.2 ArrayList和LinkedList区别

• 线程安全性：都是线程不安全的.
• 底层数据结构：ArrayList底层采用**Object[]，LinkedList底层采用双向链表**.
• 插入或删除元素
  • ArrayList采用数组存储，在非尾部插入元素会产生数据移动，时间复杂度O(n)。
  • LinkedList采用链表存储，插入元素时不会产生数据移动，时间复杂度O(n)。
• 快速随机访问
  • ArrayList支持，LinkedList不支持。
• 内存空间占用
  • ArrayList会预留一定的空间保存新的元素，LinkedList的每一个元素需要更多的空间保存（前继和后继）

2.3 ArrayList的扩容机制★★★

JavaGuide (gitee.io)

3 Set

3.1 Comparable和Comparator的区别

• Comparable接口位于java.lang包，它有一个compareTo(Object obj)方法来排序，是一个内比较器。
• Comparator接口位于java.util包，它有一个compare(Object obj1, Object obj2)方法来排序，是一个外比较器。
• 集合自定义排序：重写compareTo()方法或compare()方法。

使用Comparable定制排序（重写compareTo方法）

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

public class test {
    public static void main(String[] args) {
        TreeMap<Person, String> pdata = new TreeMap<Person, String>();
        pdata.put(new Person("张三", 30), "zhangsan");
        pdata.put(new Person("李四", 20), "lisi");
        // 得到key的值的同时得到key所对应的值
        Set<Person> keys = pdata.keySet();
        for (Person key : keys) {
            System.out.println(key.getAge() + "-" + key.getName());

        }
    }
}

public class Person implements Comparable<Person> {
    ...
    
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
    ...
}

使用Comparator定制排序

1
2
3
4
5
6
7
8
9
10
11

ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);arrayList.add(-2);arrayList.add(3);
// void sort(List list),按自然排序的升序排序
Collections.sort(arrayList);
// 定制排序的用法
Collections.sort(arrayList, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});

3.2 无序性和不可重复性的含义是什么？

• 无序性：存储对象在底层数据结构中的位置不是由对象插入的顺序决定的，而是根据对象的哈希值决定的。
• 不可重复性：不重复的对象指使用equals()比较时返回false。

4 Map

4.1 HashMap和HashTable的区别

• 线程安全性：HashMap线程不安全，HashTable线程安全（因为其内部的方法都通过synchronized修饰）。
• 效率：HashMap效率高，HashTable因锁的原因效率低。
• 对null的支持：HashMap可以存储值为null的key和value，HashTable不允许。
• 初始容量大小和扩容机制：HashTable默认大小为11，扩容为2n+1；HashMap初始大小为16，扩容为2n。
• 底层数据结构：数据+链表；JDK1.8之后，HashMap发生了变化：当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

4.2 HashMap和TreeMap区别

• TreeMap中的元素会根据键值自动排序。

4.3 HashSet如何检查重复

会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

4.4 HashMap的底层实现

• JDK1.8之前： 数组和链表 结合在一起，即 链表散列，使用拉链法解决哈希冲突。

• JDK1.8及之后：当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

4.5 ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

• 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
• 实现线程安全的方式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

• HashTable

• ConcurrentHashMap（JDK1.7）：Segment 数组 + HashEntry 数组 + 链表

• ConcurrentHashMap（JDK1.8）：Node 数组 + 链表 / 红黑树，冲突链表达到一定长度时，链表会转换成红黑树。

4.6 ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

4.6.1 JDK1.7（上面有示意图）

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

1
2
3
4

//ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
//Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

4.6.2 JDK1.8 （上面有示意图）

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

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。