集合之ArrayList

谁借莪１个温暖的怀抱￠ 2023-07-03 07:10 66阅读 0赞

## 集合之ArrayList ##

### 1.ArrayList简介 ###

ArrayList是个类，实现List接口的，底层采用数组实现。

ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

### 2.ArrayList特性 ###

优点: 底层数据结构是数组，查询快，增删慢。  
缺点: 线程不安全，但是效率高

### 3.ArrayList的数据结构 ###

ArrayList的底层数据结构就是一个数组，数组元素的类型为Object类型，对ArrayList的所有操作底层都是基于数组的。

### 4.ArrayList常见的方法 ###

array.add(object); // 添加一个元素
    
    array.get(index); // 取出集合中的元素，在get方法的参数中，写入索引。
    
    array.size(); // 返回集合的长度，也就是存储元素的个数。
    
    array.set(object); // 设置一个元素
    
    array.remove(); // 移除一个元素

### 5.ArrayList的API ###

// 将指定的元素添加到集合尾部
    boolean             add(E object)
    // 按照指定collection的迭代器返回的元素顺序，将collection中的所有元素添加到集合尾部
    boolean             addAll(Collection<? extends E> collection)
    // 移除集合所有的元素
    void                clear()
    // 如果集合包括指定元素，则返回true
    boolean             contains(Object object)
    // 如果集合包含指定集合中的所有元素，则返回 true
    boolean             containsAll(Collection<?> collection)
    // 如果指定集合与此集合相等，则返回 true
    boolean             equals(Object object)
    // 返回此集合的哈希码值
    int                 hashCode()
    // 如果此集合中没有元素，则返回 true
    boolean             isEmpty()
    // 按适当顺序在集合的元素上进行迭代的迭代器
    Iterator<E>         iterator()
    // 移除此集合中首次出现的指定元素（如果存在）。
    boolean             remove(Object object)
    // 移除集合中指定集合中的所有元素，调用此方法后，集合中将不包含任何与指定集合相同的元素。 
    boolean             removeAll(Collection<?> collection)
    // 从集合中移除未包含在指定集合中的所有元素。 
    boolean             retainAll(Collection<?> collection)
    // 返回此集合中的元素数
    int                 size()
    // 将集合转化为你指定的数组类型
    <T> T[]             toArray(T[] array)
    // 将集合直接转为Object[] 数组
    Object[]            toArray()
    // 将指定的元素插入此集合中的指定位置。
    void                add(int location, E object)
    // 从指定的位置开始，将指定集合中的所有元素插入到此列表中
    boolean             addAll(int location, Collection<? extends E> collection)
    // 返回此集合中指定位置上的元素
    E                   get(int location)
    // 返回集合中首次出现的指定元素的索引，如果集合没有此元素，则返回-1
    int                 indexOf(Object object)
    // 返回集合中最后一次出现的指定元素的索引，如果集合没有此元素，则返回-1
    int                 lastIndexOf(Object object)
    // 集合中元素的集合迭代器，从集合中的指定位置开始 
    ListIterator<E>     listIterator(int location)
    // 返回此集合元素的集合迭代器
    ListIterator<E>     listIterator()
    // 移除集合中指定位置上的元素
    E                   remove(int location)
    // 用指定元素替代此集合中指定位置上的元素
    E                   set(int location, E object)
    // 返回一个集合中的一段，可以理解为截取一个集合中的部分元素
    List<E>             subList(int start, int end)
    // 克隆（复制）集合，返回一个Object对象，所以在使用此方法的时候要强制转换。
    Object               clone()
    // 将数组进行扩容，扩容至原数组的1.5倍
    void                 ensureCapacity(int minimumCapacity)
    // 将此 ArrayList 实例的容量调整为集合的当前大小
    void                 trimToSize()
    // 移除集合中索引在fromIndex（包括）和toIndex（不包括）之间的所有元素
    void                 removeRange(int fromIndex, int toIndex)

### 6.ArrayList的自动扩容机制 ###

#### 1.ArrayList的构造函数 ####

ArrayList的构造函数总共有三个：  
1.ArrayList()构造一个初始容量为 10 的空列表。  
2.ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。  
3.ArrayList(int initialCapacity)构造一个具有指定初始容量的空列表。

#### 2.ArrayList的容量 ####

ArrayList的默认初始容量为10，当然也可以自定义指定初始容量；

随着动态的向其中添加元素，其容量可能会动态的增加，那么扩容的公式为：  
新容量 = 旧容量/2 + 旧容量  
比如：自定义初始容量为4，其容量的每次扩充后的新容量为：4->7->11->17->26->…  
即每次扩充至原有基础的1.5倍  
源码扩容方法如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbl9kYXJr_size_16_color_FFFFFF_t_70]

源码分析：

// 把数组的长度赋给oldCapacity
    int oldCapacity = elementData.length;

// 新的数组容量=老的数组长度的1.5倍。oldCapacity >> 1 相当于除以2
    int newCapacity = oldCapacity + (oldCapacity >> 1);

// 如果新的数组容量newCapacity小于传入的参数要求的最小容量minCapacity，
    // 那么新的数组容量以传入的容量参数为准。
    if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
    
    // 如果新的数组容量newCapacity大于数组能容纳的最大元素个数 MAX_ARRAY_SIZE 2^{31}-1-8
    // 那么再判断传入的参数minCapacity是否大于MAX_ARRAY_SIZE，
    // 如果minCapacity大于MAX_ARRAY_SIZE，那么newCapacity等于Integer.MAX_VALUE，
    // 否则newCapacity等于MAX_ARRAY_SIZE
    
    if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);

// 把旧数组放进新的扩容后的数组
    elementData = Arrays.copyOf(elementData, newCapacity);

**hugeCapacity方法：**

**传入的参数必须大于0，否者报错**，**判断传入的参数minCapacity是否大于MAX\_ARRAY\_SIZE，如果minCapacity大于MAX\_ARRAY\_SIZE返回\*Integer.MAX\_VALUE，否者返回MAX\_ARRAY\_SIZE。**

private static int hugeCapacity(int minCapacity) { 
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

这里有3个判断：

● if (newCapacity - minCapacity < 0)  
● if (newCapacity - MAX\_ARRAY\_SIZE > 0)  
● 以及hugeCapacity(minCapacity);函数中的：  
(minCapacity > MAX\_ARRAY\_SIZE) ? Integer.MAX\_VALUE : MAX\_ARRAY\_SIZE;

**Integer.MAX\_VALUE：整型的最大值2^31-1**

@Native public static final int   MAX_VALUE = 0x7fffffff;

**MAX\_ARRAY\_SIZE：**

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

### 7.ArrayList 去重 ###

1.利用HashSet里面的元素不可重复

public static List test1(List list){ 
            HashSet set = new HashSet(list);
            list.clear();
            list.addAll(set);
            return list;
        }

2.利用list里面contains方法比较是否存在去重

public static List test2(List list){ 
            ArrayList newList = new ArrayList();
            for(int i=0;i<list.size();i++){ 
                if(!newList.contains(list.get(i))){ 
                    newList.add(list.get(i));
                }
            }
            return newList;
        }

### 8.ArrayList的遍历 ###

方法一：普通for循环遍历

for(int i = 0 ; i < list.size() ; i++){ 　
        system.out.println(list.get(i));　
    }

方法二：Iterator迭代器遍历

Iterator it = list.iterator();
      while(it.hasNext()) { 
     　System.out.println(it.next());
     　}

方法三：增强for循环遍历（增强for循环的底层也是Iterator实现的，只是对它包装了一下）

for(String string:list){ 　
        system.out.println(string);　
    }

### 9.面试题 ###

1.ArrayList list = new ArrayList(20);中的list扩充几次

答：0次，因为这是指定初始容量为20；

2.假设有以下程序：

ArrayList<Integer> arrayList = new ArrayList<Integer>(20);
    for(int i=0;i<50;i++) { 
         arrayList.add(i);
    }

初始化容量为20，总共有50个元素，需要扩容几次？

答：3次；扩容次数依次为：20->30->45->67

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbl9kYXJr_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200203220251241.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbl9kYXJr,size_16,color_FFFFFF,t_70