Java集合类详解（一）

小灰灰 2023-03-01 13:35 37阅读 0赞

Java的集合类被定义在Java.util包中，主要有四种集合，分别为List、Set、Map、Queue，如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70]

## 1. List ##

List是有序的集合，一共有3个实现类ArrayList、Vector、LinkedList。

### 1.1 ArrayList ###

ArrayList的结构比较简单，就是一个数组结构，如下图所示，图中展示的是一个长度为10的数组，从01开始计数，index表示数组的下标，从0开始计数，elementData是保存数组的容器，表示数组本身，除了index和elementData这两个概念，还有以下基本概念：

1.  DEFAULT\_CAPACITY表示数组的初始大小，默认为10
2.  size表示当前数组的大小，类型为int，没有用volatile修饰，非线程安全
3.  modCount统计当前数组被修改的版本次数，一旦数组结构有变动，就会+1
4.  ArrayList允许put null值，会自动扩容
5.  size、isEmpty、get、set、add等方法的时间复杂度都是O(1)
6.  由于ArrayList的实现的方法（add、remove等）没有进行同步操作，所以ArrayList是非线程安全的，多线程情况下，推荐使用线程安全类：Collections.synchronizedList()
7.  增强for循环，或者使用迭代器迭代过程中，如果数组大小改变，会抛出异常

![在这里插入图片描述][2020072813574986.png]

#### 1.1.1 ArrayList的初始化 ####

ArrayList有三种初始化办法：无参数直接初始化、指定容量大小初始化、指定初始数据初始化，源码如下：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
    //无参数直接初始化，数组大小为空
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //指定容量大小初始化
    public ArrayList(int initialCapacity) { 
    	//如果指定容量大小>0，则创建一个指定大小的数据并赋值给elementData
        if (initialCapacity > 0) { 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }
    //指定初始数据初始化
    public ArrayList(Collection<? extends E> c) { 
        //elementData 是保存数组的容器，默认为 null
        elementData = c.toArray();
        //如果给定的集合（c）数据有值
        if ((size = elementData.length) != 0) { 
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            //如果集合元素类型不是 Object 类型，我们会转成 Object
            if (elementData.getClass() != Object[].class) { 
                elementData = Arrays.copyOf(elementData, size, Object[].class);
            }
        } else { 
            // 给定集合（c）无值，则默认空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList无参构造方法初始化时，默认大小是空数组，而不是10，10是在第一次add的时候扩容的数组值。

#### 1.1.2 add()方法 ####

add()方法主要分成两步：

1.  判断是否需要扩容，如果需要扩容就执行扩容操作；
2.  直接赋值；

public boolean add(E e) { 
      //确保数组大小是否足够，不够执行扩容，size 为当前数组的大小
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      //直接赋值，线程不安全的
      elementData[size++] = e;
      return true;
    }
    private void ensureCapacityInternal(int minCapacity) { 
      //如果初始化数组大小时，有给定初始值，以给定的大小为准，不走 if 逻辑
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      //确保容积足够
      ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) { 
      //记录数组被修改
      modCount++;
      // 如果我们期望的最小容量大于目前数组的长度，那么就扩容
      if (minCapacity - elementData.length > 0)
        grow(minCapacity);
    }
    //扩容，并把现有数据拷贝到新的数组里面去
    private void grow(int minCapacity) { 
      int oldCapacity = elementData.length;
      // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
      int newCapacity = oldCapacity + (oldCapacity >> 1);
    
      // 如果扩容后的值 < 我们的期望值，扩容后的值就等于我们的期望值
      if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
      // 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就用 Integer 的最大值
      if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
     
      // 通过复制进行扩容
      elementData = Arrays.copyOf(elementData, newCapacity);
    }

*  扩容的规则不是翻倍，而是原来容量的1.5倍
 *  ArrayList中的数组的最大值是Integer.MAX\_VALUE，超过这个值，JVM就不会给数组分配内存空间了
 *  新增时，没有对值进行严格的校验，所以ArrayList是允许null的
 *  扩容是通过`Arrays.copyOf(elementData, newCapacity)`实现的，这行代码首先会新建一个newCapacity容量的新数组，然后把老数组elementData的数据拷贝到新数组中，`Arrays.copyOf(elementData, newCapacity)`方法内部调用了native方法 `System.arraycopy()`方法进行拷贝。

#### 1.1.3 remove()方法 ####

ArrayList删除元素有多种方式，比如：根据索引删除元素、根据值删除元素等。以根据索引删除元素为例。

public E remove(int index) { 
            rangeCheck(index);
    		// 版本号+1
            modCount++;
            // 根据索引位置取出要删除的元素
            E oldValue = elementData(index);
    		//numMoved表示删除index位置的元素后，需要从index后移动多少个元素到前面去
    		// -1是因为size从1算起，index从0算起
            int numMoved = size - index - 1;
            if (numMoved > 0)
            	// 从index+1位置开始拷贝，拷贝的起始位置是index，长度是numMoved
                System.arraycopy(elementData, index+1, elementData, index, numMoved);
            elementData[--size] = null; // clear to let GC do its work
    		
    		// 返回被删除的元素
            return oldValue;
        }

#### 1.1.4 线程安全 ####

只有当ArrayList作为共享变量的时候，才会有线程安全问题，当ArrayList作为局部变量的时候，没有线程安全问题的。其安全问题的本质是elementData、size、modCount这些类变量都没有加volatile关键字，即对于多个线程来说不是可见的，其次add()、remove()等方法都没有加锁，其原子性没有保证，所以值会有被覆盖的情况。

#### 1.1.5 总结 ####

ArrayList在定义时不需要定义数组的长度，当数组长度不足时，ArrayList会创建一个新的更大的数组并将已有的数据复制到新的数组中；当需要在ArrayList的中间位置插入或者删除某个元素时，需要将这个元素后的所有的元素进行移动，其代价较高，所以ArrayList不适合随机插入和删除的操作，更适合随机查找和遍历的操作

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70]: /images/20230208/caeb4df95e9e471888041512595e6161.png
[2020072813574986.png]: /images/20230208/768e6387732f4c2d98b25e0464979b55.png