Java集合基础梳理(集合体系+ArrayList)

Java集合体系

为什么要使用集合类 ?

如何选用集合?

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

快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

遍历的同时修改一个List有几种方式

ArrayList 如何进行元素的遍历操作？

ArrayList

ArrayList基础

ArrayList怎么序列化的知道吗？

为什么用transient修饰数组？

当传递ArrayList到某个方法中，或者某个方法返回ArrayList，什么时候要考虑安全隐患？如何修复安全违规这个问题呢？(todo)

ArrayList初始化相关

ArrayList（int initialCapacity）会不会初始化数组⼤⼩？

ArrayList list = new ArrayList(10) 的list扩充了多少次?

ArrayList扩容机制

ArrayList扩容机制原理

ArrayList删除元素以后会缩小容量吗？

ArrayList频繁扩容导致添加性能急剧下降，如何处理？

如何复制某个ArrayList到另一个ArrayList中去？

System.arraycopy() 和 Arrays.copyOf()方法

ArrayList相关操作

ArrayList插入和删除元素的时间复杂度？

添加add

ArrayList 可以添加 null 值吗？

ArrayList集合加入1万条数据，应该怎么提高效率 ?

删除remove

List转换

如何实现数组与List之间的转换

用ArrayList.asList转List后,如果修改了数组的内容,list会受影响么? List用toArray方法转数组后,如果修改了List的内容,数组会受影响么?

如何对Object的list排序

去重

ArrayList 如何删除重复的元素或者指定的元素?

ArrayList与其他数据结构比较

ArrayList与数组

为什么数组索引从0开始? 1开始不行么 ?

ArrayList 和 Array（数组）的区别？

ArrayList⽤来做队列合适么？那数组适合⽤来做队列么？(todo)

ArrayList与LinkedList,Vector

ArrayList和LinkedList的区别：如何选择

ArrayList 和 Vector 的区别是什么？(todo)

LinkedList 插入和删除元素的时间复杂度？

ArrayList线程安全问题(todo)

Java集合体系

Java集合主要是由两大核心接口Collection和Map接口派生而来的. Collection接口包括三个子接口,List,Set,Queue 这三个子接口又分别包含多个实现类,

比如 :

List子接口包含实现类比如 : ArrayList, LinkedList,Vector,Stack. 特点 : 元素有序可重复
Set子接口包含实现类比如 : HashSet , LinkedHashSet , TreeSet 特点 : 元素无序不可重复
Queue子接口包含实现类比如 : PriorityQueue , ArrayQueue 特点 : 按照特定规则先后顺序存储元素, 有序可重复

再来说说Map接口,它的特点是是以键值对存储元素, 根据key获取val, key无序,可重复

Map接口包含实现类比如 : HashMap , LinkedHashMap, TreeMap等

为什么要使用集合类 ?

在没有集合类之前我们可以想到使用数组存储元素, 但是数组存储有一些缺陷 :

比如 :

对数组的增删改查操作效率不高,每一次还需要自己手写,没有提供相关API能够更加容易的操作数组.
数组的长度是有限制的,一旦确定,不可修改,如果想要达到数组空间满了,自动扩容就实现不了
数组存储元素的特点是有序,重复,但是有一些特点的元素是要求实现无序,不可重复,这样就需要其他的数据结构
再比如数组不能存储键值对元素

为了提高元素的增删查改效率,以及满足不同元素的特点,给与其扩容机制,让元素存储,操作更加灵活,将不同的数据结构封装成集合类提供给开发者去使用

如何选用集合?

我们主要根据元素的存储特点来进行选择合适的集合类

比如你要想存储键值对key-val, 那么我们可以选择Map接口的实现类

存储的键值对有序你就可以使用TreeMap , 否则可以使用HashMap
如果需要保证Map的线程安全, 可以采用ConcurrentHashMap.

如果你想要存储单个元素,那么可以采用Collection接口

想要保证元素唯一考虑Set接口,有序可以使用TreeSet, 不要求有序可以采用HashSet
如果想要有按照先进先出规则进行存放元素,需要考虑使用Queue接口实现类, 需要按照优先级规则就使用PriorityQueue,否则可以使用ArrayQueue
其他存放单个元素就可以采用List, 比如 ArrayList,LinkedList, 这两个需要判断增删比较多还是查询比较多根据需求进行选择. 如果要保证集合的线程安全可以使用copyOnWriteList,或者被synchronized包裹的synchronizedList

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

String
Integer
StringBuffer
Random
Vector
Hashtable
java.util.concurrent 包下的类

剩下的不是线程安全的

快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

fial-fast和fail-safe是遍历的同时修改集合应对的两种策略, 因为多线程并发的情况下可能会发生多个线程同时修改即可.

fail-fast : 是快速失败的意思, 如果出现遍历集合的同时又修改集合,那么直接会抛出异常ConcurrentModificationException (遍历的同时不能修改)
- 它的原理就是会有一个modCount是修改集合元素的次数, 每当集合遍历下一个元素的时候会有一个预期的expectedModCount修改次数,如果与实际的modCount不一致就会立即抛出异常,不允许遍历集合的同时修改集合
fail-safe : 则是当在遍历集合的同时又其他线程对其进行修改的时候会有一些应对策略,比如牺牲一些一致性
- 比如CopyOnWriteList就是fail-safe的典型实现,当在遍历集合的时候,有其他线程修改集合,那么会拷贝集合副本让线程进行修改,并不是直接对原来的集合进行修改.

遍历的同时修改一个List有几种方式

使用普通for循环(可能会发生下标错乱,导致漏删的情况)
直接使用iterator进行操作(使用iterator可以修改expectedModCount)
使用Java8提供的filter
使用增强for并且立马退出
直接使用fail-safe的集合类如 copyOnWriteArrayList

ArrayList 如何进行元素的遍历操作？

for循环
for-each循环
stream流的foreach
lambda表达式（集合.foreach）

ArrayList

ArrayList 继承自AbstractList,

实现了List接口 , 底层实现是Object数组,可以支持集合的动态扩容

实现了Accessable接口,这就意味着它支持快速随机访问, 这个接口只是一个标识作用,ArrayList支持下标快速随机访问. 他只要知道下标,会有一个公式就能快速知道这个元素所处的位置,也就是起始位置 + 元素长度 * 下标

他还实现了cloneable,serializable接口表示支持克隆和序列化.

ArrayList是可以存储null值的,但是并不建议存储因为无意义,有可能还会出现空指针异常.

ArrayList基础

ArrayList怎么序列化的知道吗？

如果一个类需要序列化,那么在序列化的过程中会调用被序列化类的readObject方法和writeObject方法,如果用户没有定义这两个方法,会调用默认的方法ObjectOutputStream的defaultWriteObject方法和ObjectInputStream的defaultReadObjet方法;

在ArrayList中就定义了这两个方法

/**
  * Save the state of the <tt>ArrayList</tt> instance to a stream (that
  * is, serialize it).
  *
  * @serialData The length of the array backing the <tt>ArrayList</tt>
  *             instance is emitted (int), followed by all of its elements
  *             (each an <tt>Object</tt>) in the proper order.
  */
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

/**
  * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
  * deserialize it).
  */
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

为什么用transient修饰数组？

对于数组来说,它是动态扩容的, 当元素存放超过数组的阈值机会进行扩容,但是当元素从数组中删除之后,数组不会缩容. 如果一个100大小的数组,那么只存放一个元素,序列化的时候需要序列化99个null值,为了避免Java默认的序列化机制的造成的空间浪费,将数组使用transient来修饰,表示该数组不进行序列化,而ArrayList重写readObject和writeObject方法自己来实现序列化操作.

当传递ArrayList到某个方法中，或者某个方法返回ArrayList，什么时候要考虑安全隐患？如何修复安全违规这个问题呢？(todo)

ArrayList初始化相关

ArrayList（int initialCapacity）会不会初始化数组⼤⼩？

JDK7以前： 调用空构造器则是立即初始化为10个容量的数组。
JDK7开始： 调用空构造器初始化容量为0的空数组，在第一次add()之时默认扩容至少为10个容量，也可指定初始化数组的容量

ArrayList list = new ArrayList(10) 的list扩充了多少次?

public ArrayList(int initialCapacity) {
    //判断指定初始容量的值
    if (initialCapacity > 0) {
        //如果指定初始容量大于0,则构建指定长度的空数组并赋值给elementData
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //如果指定初始容量等于0,则将已有的空数组赋值给elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //如果指定初始容量小于0,则将抛出IllegalArgumentException异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);
    }
}

同样还有这个问题 : ArrayList list = new ArrayList(20) 的list扩充了多少次?

再比如 ArrayList list = new ArrayList(n)

答案都是0次,因为当你传递参数也就是initialCapacity的时候,如果大于0就会创建一个initialCapacity这么大的数组,并不会进行扩容.

ArrayList扩容机制

ArrayList扩容机制原理

计算出最小容量；

如果该集合是使用的默认空构造器初始化的，并且是第一次添加数据。然后minCapacity 设置为10

如果使用指定容量或者指定包含集合的构造方法创建的对象，使用add方法时，minCapacity不会设置为10，而是size+1。

判断是否需要扩容or数组长度溢出；

判断如果最小容量减去底层数组长度的值大于0时，即需要扩容或者可能是数组长度溢出则进入扩容逻辑grow方法

计算新的容量

int newCapacity = oldCapacity + (oldCapacity >> 1);

新容量（newCapacity）为原长度的1.5倍;

如果新容量减去最小容量的值小于0，那么设置新容量等于最小容量,因为有可能你自己初始化容量为0,但是你添加一个元素了,newCapacity还是0,所以应该设置为最小容量1

考虑数组长度溢出；

如果最小容量<0则抛出异常, 如果最小容量超过最大值(Integer),那么newCapacity直接设置为Integer的最大值

数组扩容

elementData = Arrays.copyOf(elementData, newCapacity);

实际上在底层也只是新建一个更长的数组，然后拷贝原数组的元素到新数组，并将引用指向新数组

添加元素。

添加到size索引位置,然后size ++;

ArrayList删除元素以后会缩小容量吗？

在 Java 的 ArrayList 中，删除元素并不会自动减少其底层数组的容量.即使删除了一些元素，底层数组的容量仍然保持不变。

ArrayList频繁扩容导致添加性能急剧下降，如何处理？

如果在大量数据需要添加到集合中的时候，提前定义ArrayList集合的初始容量，从而不用花费大量时间在自动扩容上

如何复制某个ArrayList到另一个ArrayList中去？

elementData = Arrays.copyOf(elementData, newCapacity);

实际上在底层也只是新建一个更长的数组，然后拷贝原数组的元素到新数组，并将引用指向新数组

System.arraycopy() 和 Arrays.copyOf()方法

看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法

    // 我们发现 arraycopy 是一个 native 方法,接下来我们解释一下各个参数的具体意义
    /**
    *   复制数组
    * @param src 源数组
    * @param srcPos 源数组中的起始位置
    * @param dest 目标数组
    * @param destPos 目标数组中的起始位置
    * @param length 要复制的数组元素的数量
    */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

arraycopy() 需要目标数组和原始数组,需要指定原始数组的起始位置和目标数组的原始位置,要拷贝的长度是多少,这个是native方法.

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

copyOf() 是系统自动在内部新建一个数组，使用system.arrayCopy拷贝完成之后 , 并返回该数组。Arrays.copyOf()方法主要是为了给原有数组扩容

System.arrayCopy既可以对原数组拷贝也可以把元素拷贝到新数组中

ArrayList相关操作

ArrayList插入和删除元素的时间复杂度？

对于插入 :

头部插入 : 需要将每一个元素向后移动一个位置,时间复杂度为O(N)
指定位置插入 : 最坏情况下,是头部插入, 所以时间复杂度为O(N)
尾部插入 : 直接放到数组中的最后一个位置即可, 放入到size位置,然后size ++ ,时间复杂度为O(1)

对于删除 :

头部删除 : 需要将每一个元素向前移动一个位置 , 时间复杂度为 O(N)
指定位置删除 : 最坏情况下需要将每一个元素向前移动一个位置 , 时间复杂度为 O(N)
尾部删除 : 直接将size--,最后一个位置元素就删除了, 时间复杂度为O(1)

添加add

ArrayList 可以添加 null 值吗？

ArrayList 中可以存储任何类型的对象，包括 null 值。不过，不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。

ArrayList集合加入1万条数据，应该怎么提高效率 ?

提高在 ArrayList 中加入1万条数据的效率，你可以考虑以下几个方面：

预分配足够的空间：在添加数据之前，使用 ArrayList 的构造函数指定一个足够大的初始容量，以避免在添加过程中频繁地进行数组复制和扩容操作。这可以通过估计最终需要存储的元素数量来实现.
避免频繁的中间插入操作：如果可能的话，尽量在 ArrayList 的尾部添加元素，因为尾部添加是 ArrayList 中效率最高的操作。如果需要频繁地在中间位置插入元素，考虑使用其他数据结构，如 LinkedList。
批量添加：如果你有多个元素需要添加到 ArrayList 中，使用 addAll() 方法一次性添加多个元素，而不是使用多次 add() 方法。这可以减少方法调用的次数，提高性能。
使用并行流：如果你使用的是 Java 8 或更高版本，可以考虑使用并行流来加速数据的添加。但请注意，并行流并不总是比顺序流更快，它适用于大量数据和多核处理器环境。
考虑其他数据结构：如果 ArrayList 的性能瓶颈主要在于频繁的中间插入和删除操作，那么可以考虑使用其他数据结构，如 LinkedList、ArrayDeque 或自定义的数据结构，这些数据结构可能更适合这种场景。

删除remove

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    //获取将要被移除的数据
    E oldValue = elementData(index);

    //要移动的数据长度size-(index + 1)  最小值0最大值size-1
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //将index+1后面的列表对象前移一位,该操作将会覆盖index以及之后的元素,相当于删除了一位元素
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 数组前移一位，size自减-，空出来的位置(原数组的有效数据的最后一位)置null，原来的具体的对象的销毁由Junk收集器负责
    elementData[--size] = null;
    //返回原数据
    return oldValue;
}

他会将index后面的元素全部向前移动一个位置,覆盖之前的元素,然后将最后一个位置置为null.size--,返回index位置的旧值.

List转换

如何实现数组与List之间的转换

1. 数组转为List

// 创建一个数组  
Integer[] array = new Integer[]{1, 2, 3, 4, 5};  
// 使用Arrays.asList方法将数组转换为List  
List<Integer> list = Arrays.asList(array);

2. List转为数组

// 创建一个List
List<Integer> arrayList = new ArrayList<>();
// 使用toArray方法将List转换为数组
Integer[] array = arrayList.toArray(new Integer[0]);

用ArrayList.asList转List后,如果修改了数组的内容,list会受影响么? List用toArray方法转数组后,如果修改了List的内容,数组会受影响么?

Arrays.asList(int[] arr)得到的list数组和我们一般使用的ArrayList数组一样吗？可以用同样的方法吗？如何正确转数组到list呢？

Arrays.asList()方法返回的ArrayList实例与常规java.util.ArrayList不同。这里返回的实例是Arrays类的一个内部类，它并没有实现add()、remove()等修改集合大小的方法。因此，尝试调用这些方法会导致UnsupportedOperationException。
如果向具有add,remove的方法,那就需要new ArrayList()包裹一下

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));

当你通过List修改一个元素时，你实际上是在修改原数组中的那个元素，同理你修改原数组那个元素,List也会改变因为List中的元素和数组中的元素是同一个对象的引用

如何对Object的list排序

// 根据姓名排序  
Collections.sort(people, new Comparator<Person>() {  
     @Override  
     public int compare(Person p1, Person p2) {  
          return p1.getName().compareTo(p2.getName());  
     }  
});

使用Collections的sort方法重写compare方法

去重

ArrayList 如何删除重复的元素或者指定的元素?

删除重复元素

使用stream流

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 2, 4, 3, 5));  
// 删除重复元素  
List<Integer> uniqueList = list.stream().distinct().collect(Collectors.toList());  
list.clear();  
list.addAll(uniqueList);

使用set去重之后加入到list中

删除指定元素

直接remove

也可以使用filter过滤

ArrayList与其他数据结构比较

ArrayList与数组

为什么数组索引从0开始? 1开始不行么 ?

根据数组索引获取元素的时候，会使用索引和寻址公式来计算内存所对应的元素数据，寻址公式：数组首地址 + 索引 * 存储数据的类型大小

a[i] = baseAddress + i * dataTypeSize

如果数组的下标/索引从1开始，寻址公式需要多做一步减法操作，对于CPU来说，多了一次指令，性能不高

a[i] = baseAddress + (i-1) * dataTypeSize

ArrayList 和 Array（数组）的区别？

ArrayList创建时不需要指定大小，而Array创建时必须指定大小。

ArrayList会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。
ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。
ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。
ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add()、remove()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。

ArrayList⽤来做队列合适么？那数组适合⽤来做队列么？(todo)

ArrayList与LinkedList,Vector

ArrayList和LinkedList的区别：如何选择

共同点：

ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
LinkedList和ArrayList元素都可以为null，元素都有序（存储顺序）。

底层实现：

ArrayList：底层是基于数组实现的，并且实现了动态扩容（当需要添加新元素时，如果 elementData 数组已满，则会自动扩容，新的容量将是原来的 1.5 倍

LinkedList：是将结点（内存块）用指针串起来的链表，因为 LinkedList 存储数据的内存地址是不连续的

新增，删除元素：

头部新增/删除

LinkedList更好一些，因为ArrayList需要往前移动元素

尾部新增/删除

ArrayList更快一些直接插入接口，LinkedList还需修改引用，需要一些指针操作

指定位置新增/删除

两者差不多，数组需要往前或者往后移动元素，链表需要遍历到指定位置进行新增/删除

随机访问：

ArrayList 支持高效的随机访问, 可以通过下标（索引）直接访问到内存地址。

LinkedList 存储数据的内存地址是不连续的，所以不支持随机访问。

如果是根据索引找元素，那么ArrayList要快于LinkedList，LinkedList需要遍历，而ArrayList直接返回即可。

如果根据元素找索引

有两种遍历方式一种是for循环遍历，一种是迭代器遍历

for 循环遍历的时候，ArrayList 花费的时间远小于 LinkedList；迭代器遍历的时候，两者性能差不多。

什么情况下你会使用ArrayList？什么时候你会选择LinkedList？

当需要频繁随机访问元素的时候，例如读取大量数据并进行处理或者需要对数据进行排序或查找的场景，可以使用 ArrayList。

当需要频繁插入和删除元素的时候，例如实现队列或栈，或者需要在中间插入或删除元素的场景，可以使用 LinkedList。

在一些特殊场景下，可能需要同时支持随机访问和插入/删除操作。在这种情况下，可以使用 LinkedList 和 ArrayList 的组合

内存空间占用：

ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。