Java集合源码分析

一、Collection

1、为什么需要Collection

Java是⼀⻔⾯向对象的语⾔，就免不了处理对象
为了⽅便操作多个对象，那么我们就得把这多个对象存储起来
想要存储多个对象(变量),很容易就能想到⼀个容器
常⽤的容器我们知道有-->StringBuffered,数组(虽然有对象数组，但是数组的⻓度是不可变的！)
所以，Java就为我们提供了集合(Collection)

2、数组和集合的区别

⻓度的区别：

数组的⻓度固定；
集合的⻓度可变；

元素的数据类型：

数组可以存储基本数据类型,也可以存储引⽤类型；
集合只能存储引⽤类型(你存储的是简单的int，它会⾃动装箱成Integer)；

3、Collection的由来与功能

Collection的由来

集合可以存储多个元素,但我们对多个元素也有不同的需求；
- 多个元素,不能有相同的
- 多个元素,能够按照某个规则排序
针对不同的需求：java就提供了很多集合类，多个集合类的数据结构不同。但是，结构不重要，重要的是能够存储东⻄,能够判断,获取
把集合共性的内容不断往上提取,最终形成集合的继承体系---->Collection

Collection的功能

1.添加功能
boolean add(Object obj)：添加一个元素；
booleab addAll(Collection c)：添加一个集合的元素。
2.删除功能
void clear()：移除所有的元素；
boolean remove(Object)：移除一个元素；
boolean remoceAll(Collection c)：移除一个集合的元素，只要一个元素被移除了，就返回true。
3.判断功能
boolean contains(Object o)：判断集合是否包含该元素；
boolean containsAll(Collection c)：判断集合中是否包含指定的集合元素，只有包含所有的元素，才叫包含；
boolean isEmpty()：判断集合是否为空。
4.获取功能
Iterator iterator()：迭代器
5.长度功能
int size()：元素的个数
6.交集功能
boolean retianAll(Collection c)：移除此collection中未包含在指定的collection中的所有元素，集合A和集合B做交集，最终的结果保存在集合A，返回值表示的是A是否发生变化。

4、迭代器(Iterator)

Iterator也是⼀个接⼝，它只有三个⽅法

hasNext()
next()
remove()

迭代器：是遍历集合的一种方式。
迭代器是依赖于集合而存在的。
定义一个集合：

Coleection c =new ArrayList();
c.add("zs");
c.add("ls");
c.add("ww");
//通过迭代器获取迭代器对象
Iterator it = c.Iterator();
while(it.hasNext()){
    String s = (String)it.next();
    System.out.println(s);
}

集合的使用步骤：

A：创建集合对象
B：创建元素对象
C：把元素添加到集合
D：遍历集合

通过集合对象获取迭代器对象；
通过迭代器对象的hasNext()方法判断是否有元素；
通过迭代器的next方法获取元素并移动到下一位置。

迭代器为什么定义成一个接口不是一个类？

假设迭代器定义的是一个类，这样就可以创建该类的对象，再通过该类的方法去遍历集合，但是呢，Java中提供了很多集合类，而这些集合类的数据结构不同，所以存储和遍历的方式是不同的，所以没有定义迭代器类。

并且无论是哪种集合类，你都应该具备获取元素的操作，并且，最好再辅助于判断功能，这样在获取前，先判断。这样更不容易出错，判断和获取功能是一个集合遍历所具备的，而每种集合的方式不一样，所以需要把判断和获取功能提取出来，并不提供具体实现，这个方式是接口。

真正的具体的实现类是子类，是内部类的方式实现。

二、List集合

特点：有序（存储顺序和取出顺序一致），可重复。

List集合常用的子类有三个：

ArrayList
底层数据结构是数组，线程不安全
LinkedList
底层数据结构是链表，线程不安全
Vector
底层数据结构是数组，线程安全。

数组
定义：存储同一种数据类型的多个元素的容器，有索引，方便获取数据。
特点：查询快，增删慢。

//定义一个数组
int[] arr = [11,22,33,44];
//遍历输出
for(int a:arr){
    System.out.println(a);
}
//获取数组的具体数据
int getResult = arr[2];
System.out.println(getResult);

链表
定义：由一个链子把多个结点连起组成的数据。
结点：由数据和地址组成（数据域和指针域组成）。

上面的链表是最基础的单向链表，如果把头元素的地址给了最后一个元素的地址位置，就是循环链表。如果每个结点由3部分组成，就可以组成双向链表，如果把前后的对应也连接起来，就成了双向循环链表。

数据结构：数据的组织方式。

常见的数据结构：
栈：先进后出，例如，存储ABC，入栈ABC，出栈CBA，子弹夹。
队列：先进先出，例如，存储ABC，入队ABC，出队ABC，排队买票。

1、ArrayList解析

1、add(E e)
总览：

1、直接插入元素

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

2、插入到特定位置上

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

实现步骤：
检查是否需要扩容；
插入元素。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

上面的代码做的事：

确认List容量，尝试容量加1，看看有无必要
添加元素

确认最小容量是否满足需求

   public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0
            : DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }//得到最小的容量
    }

随后调⽤ ensureExplicitCapacity() 来确定明确的容量，我们也来看看这个⽅法是怎么实现的

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity - elementData.length > 0)
            //如果要的最小容量比数组的长度大，那么就调用grow（）来扩容（当添加第11个元素时，minCapacity为11，数组长度为10，那么就要扩容）
            grow(minCapacity);
    }

接下来看看grow()是怎么实现的。

private void grow(int minCapacity) {

        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);//扩容完之后，调用copyof()方法
    }

再继续看copyof()方法：

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;
    }

到这里就知道了add(E e) 的基本实现，⾸先去检查⼀下数组的容量是否⾜够：

⾜够：直接添加
不⾜够：扩容
1. 扩容到原来的1.5倍
2. 第⼀次扩容后，如果容量还是⼩于minCapacity，就将容量扩充为minCapacity

2、add(int index, E element)

实现步骤：
检查角标；
空间检查，如果有需要进行扩容。
插入元素。

   public void add(int index, E element) {
        rangeCheckForAdd(index);//检查角标是否越界

        ensureCapacityInternal(size + 1);  // 扩容
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//调用arraycopy进行插入
        elementData[index] = element;
        size++;
    }

3、get⽅法

实现步骤：
检查角标；
返回元素。

    public E get(int index) {
        rangeCheck(index);//检查角标

        return elementData(index);//返回具体元素
    }

//检查角标
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

//返回元素
    E elementData(int index) {
        return (E) elementData[index];
    }

4、set⽅法

实现步骤：
检查角标；
替代元素。
返回旧值。

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;//将值进行替代，返回旧值
    }

阅读量: 45

页码： 1 2

Java集合源码分析

目录

一、Collection

1、为什么需要Collection

2、数组和集合的区别

3、Collection的由来与功能

4、迭代器(Iterator)

二、List集合

1、ArrayList解析

留言取消回复

目录

一、Collection

1、为什么需要Collection

2、数组和集合的区别

3、Collection的由来与功能

4、迭代器(Iterator)

二、List集合

1、ArrayList解析

留言 取消回复

留言取消回复