集合

什么是集合

集合就是用于存储数据的容器，只能存储引用类型，所以集合非常适合用来存储对象。而且集合是长度可变，所以对象个数不确定的时候适合使用集合

集合的特点

1、集合只能存储引用数据类型。集合用于存储对象。

2、对象的个数确定可以使用数组，对象的个数不确定的可以用集合。因为集合是可变长度的。

集合和数组的区别

1、数组是固定长度的；集合可变长度的。

2、数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。

3、数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

使用集合框架的好处

减少开发工作，它提供了几乎所有常见类型的集合和用于迭代和操作数据的有用方法，因此，我们可以更专注于业务逻辑，而不是设计我们的集合api

提高代码质量，使用经过良好测试的核心集合类可以提高我们的程序质量，提高了代码的健壮性和可用性

可重用性和互操作性

降低维护成本 通过使用JDK附带的集合类，可以降低代码维护成本

骚戴理解：其实上面的优点有归咎于使用jdk自带的集合的话我们的编码会规范一点，例如ArrayList集合，这是我们用的jdk自带的统一规范的集合，那么这个集合的方法，具体使用无论在哪里都是一样的，但是如果是我们每个人自己设计自己的集合，首先要花很多时间，其次每个人设计的集合的方法名可能不一样，那么你自己用还好，要是别人也用你这个那还要去看你的方法名对应的功能是什么，他要是也写了个跟你一样的集合，定义的方法名也不一样，那就会很乱，所以用jdk自带的集合就会统一规范，不会像上面一样这么乱七八糟

常用的集合类有哪些？

Map接口和Collection接口是所有集合框架的父接口：

Collection集合的子接口有Set、List、Queue 三种子接口

Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等

List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

Queue接口的实现类主要有：BlockingQueue、Deque等

Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap等

骚戴理解：注意没有TreeList

集合框架底层数据结构

Collection集合主要有List和Set两大接口

1、List

rrayList：ArrayList是基于数组实现的，它的底层数据结构是一个可变的数组。当插入元素时，如果数组已满，则需要扩容，扩容的方式是创建一个新的数组，将原数组中的元素复制到新数组中，然后将新元素插入到新数组中。

LinkedList：LinkedList是基于链表实现的，它的底层数据结构是一个双向链表。当插入元素时，只需要修改链表中相应的指针，不需要像ArrayList那样进行数组的复制和扩容。

Vector：Vector是线程安全的List实现类，它的底层数据结构和ArrayList类似，也是一个可变的数组。不同的是，Vector的方法都是同步的，因此可以保证线程安全。

Stack：Stack是基于Vector实现的，它是一种后进先出（LIFO）的数据结构，支持压栈和出栈操作。

骚戴理解：Vector和Stack都是线程安全的类

2、Set

HashSet（无序，唯一）：基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

LinkedHashSet： LinkedHashSet 继承 HashSet，并且其内部是通过 LinkedHashMap

来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。

TreeSet（有序，唯一）： 红黑树(平衡的排序二叉树)

3、Map

HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间

LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表来保持键值对的插入顺序。同时通过对链表进行相应的操作， 实现了访问顺序相关逻辑。

HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

TreeMap： 红黑树（自平衡的排序二叉树）

ConcurrentHashMap：Java中线程安全的哈希表实现，它的底层数据结构是分段锁的哈希表。具体来说，它将整个哈希表分成了多个段(segment)，每个段都是一个独立的哈希表，每个段都有自己的锁，因此可以实现多线程并发访问，提高了并发性能。

每个段的大小可以通过参数进行配置，默认是16。在ConcurrentHashMap中，每个元素被存储在一个Entry对象中，Entry对象包含了key、value和一个指向下一个Entry的指针。每个段都包含一个Entry数组，数组的每个元素都是一个链表的头结点，每个链表中存储了哈希值相同的元素。

在进行插入、查找、删除等操作时，首先需要根据key的哈希值找到对应的段，然后在该段中进行操作。由于每个段都有自己的锁，因此不同的线程可以同时访问不同的段，从而提高了并发性能。

总之，ConcurrentHashMap是Java中线程安全的哈希表实现，采用分段锁的哈希表作为底层数据结构，可以实现高效的多线程并发访问。

哪些集合类是线程安全的？哪些集合类是线程不安全的？

哪些集合类是线程安全的？

Vector：只要是关键性的操作，方法前面都加了synchronized关键字，来保证线程的安全性

Hashtable：使用了synchronized关键字，所以相较于Hashmap是线程安全的。

ConcurrentHashMap:使用锁分段技术确保线性安全，是一种高效但是线程安全的集合。

Stack：栈，也是线程安全的，继承于Vector。

哪些集合类是线程不安全的？

• Hashmap
• Arraylist
• LinkedList
• HashSet
• TreeSet
• TreeMap

线程不安全的原因

Hashmap：HashMap在put操作的时候，如果插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是resize，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。

Arraylist： List 对象在做 add 时，执行 Arrays.copyOf 的时候，返回一个新的数组对象。当有线程 A、B… 同时进入 grow方法，多个线程都会执行 Arrays.copyOf 方法，返回多个不同的 elementData 对象，假如，A先返回，B 后返回，那么 List.elementData ==A. elementData,如果同时B也返回，那么 List.elementData ==B. elementData,所以线程B就把线程A的数据给覆盖了，导致线程A的数据被丢失。

LinkedList：与Arraylist线程安全问题相似，线程安全问题是由多个线程同时写或同时读写同一个资源造成的。

HashSet：底层数据存储结构采用了Hashmap，所以Hashmap会产生的线程安全问题HashSet也会产生。

Java集合的快速失败机制 “fail-fast”？

什么是快速失败机制 “fail-fast”？

fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。

当多个线程对同一个集合的内容进行操作时，就有可能出现在一个线程正在迭代集合的过程中，别的线程修改了这个集合的内容，这就会产生fail-fast事件，抛出 ConcurrentModificationException异常，单线程也可能会出现fail-fast事件

例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。但是要注意，fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug

fail-fast的出现场景

在我们常见的java集合中就可能出现fail-fast机制,比如ArrayList，HashMap。在多线程和单线程环境下都有可能出现快速失败。

单线程环境下的fail-fast

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    for (int i = 0 ; i < 10 ; i++ ) {
         list.add(i + "");
    }
    Iterator<String> iterator = list.iterator();
    int i = 0 ;
    while(iterator.hasNext()) {
         if (i == 3) {
              list.remove(3);
         }
         System.out.println(iterator.next());
         i ++;
    }
}

该段代码定义了一个Arraylist集合，并使用迭代器遍历，在遍历过程中，刻意在某一步迭代中remove一个元素，这个时候，就会发生fail-fast。

public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    for (int i = 0 ; i < 10 ; i ++ ) {
         map.put(i+"", i+"");
    }
    Iterator<Entry<String, String>> it = map.entrySet().iterator();
    int i = 0;
    while (it.hasNext()) {
         if (i == 3) {
              map.remove(3+"");
         }
         Entry<String, String> entry = it.next();
         System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
         i++;
    }
}

该段代码定义了一个hashmap对象并存放了10个键值对，在迭代遍历过程中，使用map的remove方法移除了一个元素，导致抛出了 ConcurrentModificationException异常

多线程环境下

public class FailFastTest {
    public static List<String> list = new ArrayList<>();
    private static class MyThread1 extends Thread {
          @Override
          public void run() {
               Iterator<String> iterator = list.iterator();
               while(iterator.hasNext()) {
                    String s = iterator.next();
                    System.out.println(this.getName() + ":" + s);
                    try {
                     Thread.sleep(1000);
                 } catch (InterruptedException e) {
                     e.printStackTrace();
                 }
               }
               super.run();
          }
    }
    private static class MyThread2 extends Thread {
          int i = 0;
          @Override
          public void run() {
               while (i < 10) {
                    System.out.println("thread2:" + i);
                    if (i == 2) {
                          list.remove(i);
                    }
                    try {
                     Thread.sleep(1000);
                 } catch (InterruptedException e) {
                     e.printStackTrace();
                 }
                    i ++;
               }
          }
    }
    public static void main(String[] args) {
          for(int i = 0 ; i < 10;i++){
               list.add(i+"");
            }
          MyThread1 thread1 = new MyThread1();
          MyThread2 thread2 = new MyThread2();
          thread1.setName("thread1");
          thread2.setName("thread2");
          thread1.start();
          thread2.start();
    }
}

启动两个线程，其中一个线程1对list进行迭代，另一个线程2在线程1的迭代过程中去remove一个元素，结果也是抛出了java.util.ConcurrentModificationException

上面都是讲的删除导致集合结构改变而造成快速失败的情况，如果是添加导致的集合结构改变，也是会出现快速失败的，这里就不再举例了。

实现原理分析

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

可以看出，该方法才是判断是否抛出ConcurrentModificationException异常的关键。

在该段代码中，当modCount != expectedModCount时，就会抛出该异常。但是在一开始的时候，expectedModCount初始值默认等于modCount，为什么会出现modCount != expectedModCount？

很明显expectedModCount在整个迭代过程除了一开始赋予初始值modCount外，并没有在任何地方对其进行修改操作，不可能发生改变，所以可能发生改变的就只有modCount。下面我们在通过源码来看一下什么时候“modCount 不等于 expectedModCount”，通过ArrayList的源码，来看看modCount是如何被修改的。

package java.util;
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    // list中容量变化时，对应的同步函数
    public void ensureCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
    // 添加元素到队列最后
    public boolean add(E e) {
        // 修改modCount
        ensureCapacity(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    // 添加元素到指定的位置
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(
            "Index: "+index+", Size: "+size);
        // 修改modCount
        ensureCapacity(size+1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
             size - index);
        elementData[index] = element;
        size++;
    }
    // 添加集合
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        // 修改modCount
        ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    // 删除指定位置的元素
    public E remove(int index) {
        RangeCheck(index);
        // 修改modCount
        modCount++;
        E oldValue = (E) elementData[index];
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null; // Let gc do its work
        return oldValue;
    }
    // 快速删除指定位置的元素
    private void fastRemove(int index) {
        // 修改modCount
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    }
    // 清空集合
    public void clear() {
        // 修改modCount
        modCount++;
        // Let gc do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }
    ...
}

我们发现：无论是add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount的值。

接下来，我们再系统的梳理一下fail-fast是怎么产生的。步骤如下：

1、新建了一个ArrayList，名称为arrayList。

2、向arrayList中添加内容。

3、新建一个“线程a”，并在“线程a”中通过Iterator反复的读取arrayList的值。

4、新建一个“线程b”，在“线程b”中删除arrayList中的一个“节点A”。

5、这时，就会产生有趣的事件了。

在某一时刻，“线程a”创建了arrayList的Iterator。此时“节点A”仍然存在于arrayList中，创建arrayList时，expectedModCount = modCount(假设它们此时的值为N)。

在“线程a”在遍历arrayList过程中的某一时刻，“线程b”执行了，并且“线程b”删除了arrayList中的“节点A”。“线程b”执行remove()进行删除操作时，在remove()中执行了“modCount++”，此时modCount变成了N+1！

线程a”接着遍历，当它执行到next()函数时，调用checkForComodification()比较“expectedModCount”和“modCount”的大小；而“expectedModCount=N”，“modCount=N+1”,这样，便抛出ConcurrentModificationException异常，产生fail-fast事件。

至此，我们就完全了解了fail-fast是如何产生的！

实现原理总结

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

有一个checkForComodification方法，当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(其它线程通过add、remove、clear等方法，调用这些方法modCount都会自增，也就是modCount++)，改变了modCount的值，当modCount != expectedModCount时（在一开始的时候expectedModCount初始值默认等于modCount），这时就会抛出ConcurrentModificationException异常，产生fail-fast事件。

解决办法：

1、在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。

1、使用CopyOnWriteArrayList来替换ArrayList

怎么确保一个集合不能被修改？

可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集

合，这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

List list = new ArrayList<>();
list. add("x");
Collection clist = Collections. unmodifiableCollection(list);
clist. add("y"); // 运行时此行报错
System. out. println(list. size());

List、Set、Map 是否继承自Collection 接口？List，Set，Map三者的区别？List、Map、Set 三个接口存取元素时，各有什么特点？

1、List、Set、Map 是否继承自Collection 接口？

Java 容器分为 Collection 和 Map 两大类，Collection集合的子接口有Set、List、Queue 三种子接口。我们比较常用的是Set、List，Map接口不是collection的子接口。 Collection集合主要有List和Set两大接口

2、List，Set，Map三者的区别

List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。

List接口常用的实现类有 ArrayList、LinkedList 和 Vector。

Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。

Set 接口常用实现类是 HashSet、LinkedHashSet 以及TreeSet。

Map：一个键值对集合，存储键、值和之间的映射。 Key无序，唯一；value 不要求有序，允许重复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

3、List、Map、Set 三个接口存取元素时，各有什么特点？

List、Map、Set 三个接口存放时

List以特定的索引(有顺序的存放)来存放元素,可以有重复的元素

Set存放元素是无序的,而且不可重复（用对象的equals()方法来区分元素是否重复）

Map保存键值对的映射,映射关系可以是一对一(键值)或者多对一,需要注意到的是：键无序不可重复,值可以重复

List、Map、Set 三个接口取出时

List取出元素for循环，foreach循环，Iterator迭代器迭代

Set取出元素foreach循环，Iterator迭代器迭代

Map取出元素foreach循环，Iterator迭代器迭代

遍历map集合的方式有哪些

遍历Map集合的方式有以下几种：

1. 使用Iterator迭代器遍历Map集合。通过获取Map的entrySet()方法返回的Set集合，再通过Set集合的iterator()方法获取Iterator迭代器，最后使用while循环遍历Map集合中的元素。示例代码如下：

   Map<String, Integer> map = new HashMap<>();
   map.put("A", 1);
   map.put("B", 2);
   map.put("C", 3);
   Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
   while (iterator.hasNext()) {
       Map.Entry<String, Integer> entry = iterator.next();
       System.out.println(entry.getKey() + " : " + entry.getValue());
   }

2. 使用for-each循环遍历Map集合。通过获取Map的entrySet()方法返回的Set集合，再通过for-each循环遍历Set集合中的元素。示例代码如下：

   Map<String, Integer> map = new HashMap<>();
   map.put("A", 1);
   map.put("B", 2);
   map.put("C", 3);
   for (Map.Entry<String, Integer> entry : map.entrySet()) {
       System.out.println(entry.getKey() + " : " + entry.getValue());
   }

3. 遍历Map集合的键或值。通过获取Map的keySet()方法返回的Set集合，或values()方法返回的Collection集合，再通过for-each循环遍历Set或Collection集合中的元素。示例代码如下：

   Map<String, Integer> map = new HashMap<>();
   map.put("A", 1);
   map.put("B", 2);
   map.put("C", 3);
   for (String key : map.keySet()) {
       System.out.println(key + " : " + map.get(key));
   }
   for (Integer value : map.values()) {
       System.out.println(value);
   }

总之，遍历Map集合的方式有多种，需要根据具体的需求和场景选择合适的方式。

comparable 和 comparator的区别？

comparable 和 comparator的区别？

comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序，comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序

Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。而Comparator是比较器，通过一个类实现这个接口来作为一个比较器来进行排序。

Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。