第一部分：集合概述
第二部分：Collection子接口之List
- 2.1 Arraylist和Vector的区别
- 2.2 Arraylist与LinkedList区别
第三部分：Collection子接口之Set
第四部分：Map接口

第一部分：集合概述

1.1 Java集合概览

从下图可以看出，在 Java 中除了以 Map 结尾的类之外，其他类都实现了 Collection 接口。并且，以 Map 结尾的类都实现了 Map 接口。

1.2 List，Set，Map三者的区别？

List (对付顺序的好帮手)：存储的元素是有序的、可重复的。
Set (注重独一无二的性质)：存储的元素是无序的、不可重复的。
Map (用 Key 来搜索的专家)：使用键值对(key-value)存储，类似于数学上的函数 y=f(x)，”x”代表key，”y”代表 value，Key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

1.3 集合框架底层数据结构总结
先来看一下 Collection 接口下面的集合：
List
- Arraylist：Object[]数组；
- Vector：Object[]数组；
- LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)。
Set
- HashSet(无序，唯一)：基于 HashMap 实现的，底层采用 HashMap 来保存元素；
- LinkedHashSet：LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的；
- TreeSet(有序，唯一)：红黑树(自平衡的排序二叉树)。

再来看看 Map 接口下面的集合：

Map
- HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认为 8，将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树)时，将链表转化为红黑树，以减少搜索时间；
- LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑；
- Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的；
- TreeMap：红黑树(自平衡的排序二叉树)。
  1.4 如何选用集合
  主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap，不需要排序时就选择 HashMap，需要保证线程安全就选用 ConcurrentHashMap。
  当我们只需要存放元素值时，就选择实现 Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。
  1.5 为什么要使用集合
  当我们需要保存一组类型相同的数据的时候，我们应该是用一个容器来保存，这个容器就是数组，但是，使用数组存储对象具有一定的弊端，因为我们在实际开发中，存储的数据的类型是多种多样的，于是，就出现了“集合”，集合同样也是用来存储多个数据的。
  数组的缺点是一旦声明之后，长度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可重复的，特点单一。但是集合提高了数据存储的灵活性，Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据。
  第二部分：Collection子接口之List
  2.1 Arraylist和Vector的区别
ArrayList 是 List 的主要实现类，底层使用 Object[ ] 存储，适用于频繁的查找工作，线程不安全；
Vector 是 List 的古老实现类，底层使用 Object[ ] 存储，线程安全的。
2.2 Arraylist与LinkedList区别

是否保证线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构：Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别。）
插入和删除是否受元素位置的影响：
- ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候，ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))，时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位/向前移一位的操作。
- LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响(add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast())，近似 O(1)，如果是要在指定位置 i 插入和删除元素的话(add(int index, E element)、remove(Object o)) 时间复杂度近似为 O(n)，因为需要先移动到指定位置再插入。
是否支持快速随机访问：LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用：ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

🍕补充内容：双向链表和双向循环链表
双向链表：包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
Java容器常见问题总结 - 图2
双向循环链表： 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。
Java容器常见问题总结 - 图3
🍕补充内容：RandomAccess接口

public interface RandomAccess {}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以，RandomAccess 接口是一个标识。标识什么？标识实现这个接口的类具有随机访问功能。
在 binarySearch() 方法中，它要判断传入的 list 是否 RandomAccess 的实例，如果是，调用indexedBinarySearch()方法，如果不是，那么调用iteratorBinarySearch()方法

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 实现了 RandomAccess 接口，而 LinkedList 没有实现。ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O(n)，所以不支持快速随机访问。ArrayList 实现了 RandomAccess 接口，就表明了具有快速随机访问功能。RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的⭕。

第三部分：Collection子接口之Set

3.1 comparable和comparator比较

3.1.1 相同点

他们都是Java的一个接口，并且是用来对自定义的class比较大小的，自定义class：public class Person{ String name; int age }。
当我们有这么一个personList，里面包含了person1, person2, persion3......，我们用Collections.sort(personList)是得不到预期的结果的。那为什么可以排序一个字符串 list 呢，例如以下代码能够得到正确的排序，那是因为 String 这个类已经帮我们实现了 Comparable 接口。所以我们的 Person 如果想排序，也要实现一个比较器。

ArrayList<String> stringList = new ArrayList<>();
stringList.add("hello1");
stringList.add("hello3");
stringList.add("hello2");
Collections.sort(stringList);
System.out.println(stringList)

3.1.2 不同点

Comparable

Comparable 定义在 Person 类的内部：

public class Persion implements Comparable {..比较Person的大小..}

因为已经实现了比较器，那么我们的 Person 现在是一个可以比较大小的对象了，它的比较功能和 String 完全一样，可以随时随地的拿来比较大小，因为 Person 现在自身就是有大小之分的。Collections.sort(personList)可以得到正确的结果。

Comparator

Comparator 是定义在 Person 的外部的，此时我们的 Person 类的结构不需要有任何变化，如：

public class Person{ String name; int age; }

然后我们另外定义一个比较器：

public PersonComparator implements Comparator() {..比较Person的大小..}

在 PersonComparator 里面实现了怎么比较两个 Person 的大小。所以，用这种方法，当我们要对一个 personList进行排序的时候，我们除了要传递 personList 过去，还需要把 PersonComparator 传递过去，因为怎么比较 Person 的大小是在 PersonComparator 里面实现的，如：

Collections.sort( personList , new PersonComparator() )

3.1.3 实例

Comparable

实现 Comparable 接口要覆盖compareTo()方法，在compareTo()方法里面实现比较：

public class Person implements Comparable {
     String name;
     int age
     public int compareTo(Person another) {
          int i = 0;
          i = name.compareTo(another.name); // 使用字符串的比较
          if(i == 0) { // 如果名字一样,比较年龄, 返回比较年龄结果
               return age - another.age;
          } else {
               return i; // 名字不一样, 返回比较名字的结果.
          }
     }
}

这时我们可以直接用 Collections.sort( personList ) 对其排序了。

Comparator

实现 Comparator 需要覆盖 compare() 方法：

public class Person{
     String name;
     int age
}
class PersonComparator implements Comparator { 
     public int compare(Person one, Person another) {
          int i = 0;
          i = one.name.compareTo(another.name); // 使用字符串的比较
          if(i == 0) { // 如果名字一样,比较年龄,返回比较年龄结果
               return one.age - another.age;
          } else {
               return i; // 名字不一样, 返回比较名字的结果.
          }
     }
}

Collections.sort( personList , new PersonComparator())可以对其排序。

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

什么是无序性？无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
什么是不可重复性？不可重复性是指添加的元素按照 equals()判断时，返回 false，需要同时重写 equals()方法和 HashCode()方法。

3.3 比较HashSet、LinkedHashSet和TreeSet三者的异同
HashSet 是 Set 接口的主要实现类，HashSet 的底层是 HashMap，线程不安全的，可以存储 null 值；
LinkedHashSet 是 HashSet 的子类，能够按照添加的顺序遍历；
TreeSet 底层使用红黑树，能够按照添加元素的顺序进行遍历，排序的方式有自然排序和定制排序。

第四部分：Map接口

4.1 HashMap和Hashtable的区别
线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的，因为 HashTable 内部的方法基本都经过 synchronized 修饰。(如果要保证线程安全的话就使用 ConcurrentHashMap )；
效率：因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持：

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；
HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

初始容量大小和每次扩充容量大小的不同：

创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍；
创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小(HashMap 中的tableSizeFor()方法保证，下面给出了源代码)。

底层数据结构：JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认为 8 )时，将链表转化为红黑树(将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树)，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 中带有初始容量的构造函数：

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小：

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

4.2 HashMap和HashSet区别

HashSet 底层就是基于 HashMap 实现的。HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap	HashSet
实现了 Map 接口	实现 Set 接口
存储键值对	仅存储对象
调用 `put()` 向 Map 中添加元素	调用 `add()` 方法向 Set 中添加元素
HashMap 使用键(Key)计算 hashcode	HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以`equals()`方法用来判断对象的相等性

4.3 HashMap和TreeMap区别

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

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。
实现 SortMap 接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下：

public class Person {
    private Integer age;
    public Person(Integer age) {
        this.age = age;
    }
    public Integer getAge() {
        return age;
    }
    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

输出：

person1
person4
person2
person3

可以看出，TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了。上面，我们是通过传入匿名内部类的方式实现的，可以将代码替换成 Lambda 表达式实现的方式：

TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
  int num = person1.getAge() - person2.getAge();
  return Integer.compare(num, 0);
});

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

4.4 HashSet如何检查重复

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

如果两个对象相等，则 hashcode 一定也是相同的；
两个对象相等，对两个 equals() 方法返回 true；
两个对象有相同的 hashcode 值，它们也不一定是相等的；
综上，equals() 方法被覆盖过，则 hashCode() 方法也必须被覆盖；
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。

🍕== 与 equals 的区别：

对于基本类型来说，== 比较的是值是否相等；
对于引用类型来说，== 比较的是两个引用是否指向同一个对象地址(两者在内存中存放的地址是否指向同一个地方)；
对于引用类型(包括包装类型)来说，equals() 如果没有被重写，对比它们的地址是否相等；如果 equals() 方法被重写(例如 String)，则比较的是地址里的具体内容。
4.5 HashMap的底层实现

JDK1.8之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置( n 指的是数组的长度)，如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash() 方法。使用 hash() 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。
JDK 1.8 HashMap 的 hash 方法源码：

    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

对比一下 JDK1.7 的 HashMap 的 hash 方法源码：

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
Java容器常见问题总结 - 图6

JDK1.8之后

相比于之前的版本，JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认为 8)时，将链表转化为红黑树(将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树)，以减少搜索时间。
Java容器常见问题总结 - 图7

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

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

Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的，用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。
我们首先可能会想到采用%取余的操作来实现。但是，取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方)，并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

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

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。
详情请查看：https://coolshell.cn/articles/9606.html

4.8 HashMap有哪几种常见的遍历方式

HashMap 的 7 种遍历方式与性能分析！

4.9 ConcurrentHashMap和Hashtable的区别

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

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

两者的对比图：
HashTable：
Java容器常见问题总结 - 图8
https://www.cnblogs.com/chengxiao/p/6842045.html>
JDK1.7 的 ConcurrentHashMap：
Java容器常见问题总结 - 图9
https://www.cnblogs.com/chengxiao/p/6842045.html>
JDK1.8 的 ConcurrentHashMap：
Java容器常见问题总结 - 图10
JDK1.8 的 ConcurrentHashMap 不在是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。

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

JDK1.7

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

JDK1.8

ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表转换为红黑树，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

1.5 Collections工具类

Collections 工具类常用方法：

排序；
查找、替换操作；

同步控制。

1.5.1 排序操作

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

1.5.2 查找、替换操作

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

1.5.3 同步控制

Collections 提供了多个synchronizedXxx()方法，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。
我们知道 HashSet，TreeSet，ArrayList，LinkedList，HashMap，TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。
最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。
方法如下：

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。 
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。 
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。 
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。

Java容器常见问题总结

第一部分：集合概述

1.1 Java集合概览

1.2 List，Set，Map三者的区别？

1.3 集合框架底层数据结构总结

1.4 如何选用集合

1.5 为什么要使用集合

第二部分：Collection子接口之List

2.1 Arraylist和Vector的区别

2.2 Arraylist与LinkedList区别