JAVA集合源码

数组的劣势，集合的优势

 

数组：

1. 长度开始时必须指定，而且一旦指定，不能修改
2. 保存的必须为同一类型的元素
3. 使用数组进行增加/删除元素比较麻烦

集合：

1. 可以动态保存任意多个对象，使用比较方便
2. 提供了一系列方便操作对象的方法： add、remove、set、get
3. 使用集合添加，删除新元素的代码简洁明了

集合的总体框架体系如下图

 ArrayList底层结构及源码分析

注意事项

1、ArrayList可以加入多个null

2、ArrayList是由数组实现数据存储

3、ArrayList基本等同于Vector，除了ArrayList是线程不安全的(执行效率高)，在多线程情况下，不建议使用ArrayList

transient:短暂的 ，表示该关键字修饰的对象不会被序列化

1.1 ArrayList的三种构造方式

分别是指定大小构造，

无参构造

接口式构造

1.1.1 无参构造

 首先我们分析一下ArrayList无参构造的源码

 ArrayList list=new ArrayList();

步入可以看到

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

可以当作构建了一个空数组

当我们用for循环往里面添加元素时，可以看到源码

    //使用for循环增加数据
        for(int i=1;i<=10;i++){
            list.add(i);
        }

先对基本类型int做了一个装箱操作，转换成包装类型Integer

    public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

再执行add方法

    public boolean add(E e) {
//先确定是否要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
//执行赋值操作
        elementData[size++] = e;
        return true;
    }

在这里我们需要看一下ensureCapacityInternal方法的底层源码

   private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

其中calculateCapacity方法

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

此方法表示，如果链表为空时，默认将其长度扩大为10（DEFAULT_CAPACITY默认为10），否则返回当前长度。

ensureExplicitCapacity方法：

   private void ensureExplicitCapacity(int minCapacity) {
//记录修改次数        
modCount++;
 
        // overflow-conscious code
//如果所需要的最小长度大于现有长度，调用grow方法进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

grow源码如下所示 

简言之：链表没扩容之前，要加入新元素时，直接将长度扩大为10。扩容之后的链表如果再次无法满足添加元素的要求，会按1.5倍的机制进行扩容，比如10扩容到15。

   private void grow(int minCapacity) {
        // overflow-conscious code
        //记录原数组长度
        int oldCapacity = elementData.length;
        //将原数组长度扩大1.5倍
        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);
    }

1.1.2 有参构造

即指定链表的初始长度，步入进源码如下

    public ArrayList(int initialCapacity) {
//指定长度大于0，选用指定长度
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } 
//指定长度等于0，赋于空数组
else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } 
//指定长度小于0，报非法异常
else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

详细内容参考ArrayList源码分析（全）_zwhandsome的博客-CSDN博客_arraylist源码

2 Vector 源码讲解

 它是线程安全的，从源码中便可得知，有synchronized关键字，保证了线程安全

 public synchronized void removeElementAt(int index) 

Vector与ArrayList的区别

2.1 Vector 构造源码追溯

2.1.1 无参构造

追溯源码

   public Vector() {
        this(10);
    }

再往下走 

    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

继续往下追溯，可以看到分配了长度为10的数组给Vector

  public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

 至于add方法与arraylist大同小异

2.1.2 有参构造

指定长度，与ArrayList大同小异

3、set 本质上就是hashmap

hashset的源码可见

HashSet基本介绍和源码剖析_昱晟168的博客-CSDN博客_hashset负载因子

linkedhashset的源码分析可见

LinkedHashSet基本介绍和源码剖析_昱晟168的博客-CSDN博客_linkedhashset

treeset的源码分析可见

TreeSet基本介绍和源码剖析_昱晟168的博客-CSDN博客_treeset源码分析

4. MAP

4.1 hashmap分析 

HashMap集合基本介绍和底层源码剖析_昱晟168的博客-CSDN博客

4.1.1 hashmap底层数据结构

在jdk1.8 之前，hashmap由数组+链表的数据结构组成的

在jdk1.8之后，hashmap由数组+链表+红黑树数据结构所组成

4.2 hashtable分析

Hashtable集合基本介绍和源码剖析_昱晟168的博客-CSDN博客

4.3 Properties 分析

Properties集合基本介绍和使用_昱晟168的博客-CSDN博客_properties 配置集合

4.4 TreeMap分析

TreeMap集合基本介绍和源码剖析_昱晟168的博客-CSDN博客