关于对Java集合类的一些总结（一）

小咪咪 2022-11-28 15:13 95阅读 0赞

## Java集合类主要分为Collection和Map两大接口，下面将对每个实现类做简要概述 ##

![集合类][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center]

### 一、List接口下有两个实现类，分别是ArrayList和LinkedList ###

1、ArrayList底层的数据结构是Object\[ \]数组

transient Object[] elementData;

当创建一个没有指定初始大小的ArrayList时，默认会创建一个长度为0的数组

private static final Object[] EMPTY_ELEMENTDATA = { };
    ...
    public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

添加元素时调用add()方法中的ensureCapacityInternal()方法，会指定数组的长度为10

private static final int DEFAULT_CAPACITY = 10;
    ...
    public boolean add(E e) { 
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    ...
    private void ensureCapacityInternal(int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }

如果存放的元素个数大于10，会调用grow()方法，创建一个长度为原来1.5倍的数组，将原数组中的元素复制过去，并引用新的数组。

private void grow(int minCapacity) { 
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);//移位操作
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

细心的朋友已经发现了，**ArrayList是线程不安全的**，下面做一下简要分析：  
**情况一：** 当多线程往ArrayList里添加元素时，首先会调用add()方法中的

ensureCapacityInternal(size + 1);

假设此时ArrayList中的size为9，线程A先调用此方法，size+1后容量为10，判断可以继续添加元素，在即将调用添加方法时

elementData[size++] = e;

线程B调用`ensureCapacityInternal(size + 1);`方法，size+1后容量为10，判断可以继续添加元素，此时A添加完元素之后，size为10，当B继续添加发现size=11,报ArrayIndexOutOfBoundsException。  
**情况二:** 调用`elementData[size++] = e;`时，是分为两步的，  
（1）elementData\[size++\]=e;  
（2）size=size+1;  
当线程A和B同时添加元素时，A执行(2)之前，B执行(1)，B线程的值会覆盖A的值，此时elementData\[1\]=0;  
**如果需要用到线程安全的列表时，可以用Collections包下的synchronizedList(new ArrayList())或者Concurrent包下copyOnWriteArrayList()；**

2、LinkedList底层是双向链表，由Node节点组成，Node节点包括以下三部分：  
![linkedlist][]  
LinkedList初始大小为0，没有所谓的扩容机制，添加元素时调用add()方法

public boolean add(E e) { 
            linkLast(e);
            return true;
        }
    ...
    void linkLast(E e) { 
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }

**LinkedList也是非线程安全的。**

**ArrayList和LinkedList区别：**  
（1）前者的底层数据结构是数组，后者是双向链表  
（2）前者查询效率高，因为数组有下标索引，可以快速访问。插入和删除的效率低，因为插入和删除会移动其他元素的位置。后者插入和删除的效率高，只需要移动节点间的箭头指向即可，查询需要从头开始遍历，效率低

3、Vector底层是object\[ \]数组，因为方法都由synchronized修饰，所以是线程安全的，不过由于vector是古老的类且效率较低，现在很少使用了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/3b8e8252d2c84953b006f01a8fbafd75.png
[linkedlist]: /images/20221124/7d6ca5c4c6dd4022957d39901d1cb446.png