Java 集合源码详解

2024-08-06 14:16:43 浏览数 (2)

Java 集合源码详解

集合和数组：

  • 数组声明了它容纳的元素的类型，而集合不声明存储Object类型 可以通过泛型进行规范！
  • 数组是静态的，一个数组实例具有固定的大小，一旦创建了就无法改变容量了。 集合是可以动态扩展容量，可以根据需要动态改变大小，集合提供更多的成员方法，能满足更多的需求。
  • 集合: 和数组一样Java中用来存储数据的作用，弥补了数组长度固定的缺点更灵活

List接口

概述：

  • 鉴于Java中数组用来存储数据长度固定，我们通常使用List替代数组 动态数组
  • List集合类中元素有序、且可重复 集合中的每个元素都有其对应的顺序索引。 List除了从Collection集合继承的方法外，List 集合里添加了一些 根据索引来操作集合元素的方法。 void add(int index, Object ele):在index位置插入ele元素 boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来 Object get(int index):获取指定index位置的元素 …
  • List接口的实现类常用的有：ArrayList、LinkedList和Vector

ArrayList 源码分析

  • ArrayList 是 List 接口的典型实现类、主要实现类用的最多
  • 本质上，ArrayList是对象引用的一个”变长”数组 因为是数组，所以非常适合与进行遍历！

ArrayList的JDK1.8之前与之后的实现区别？

  • JDK1.7：ArrayList像饿汉式，直接创建一个初始容量为10的数组
  • JDK1.8：ArrayList像懒汉式，一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组

建议可以自己深入底层查看效果更佳！

List list = new ArrayList(); 按住Ctrl 鼠标右键 进入源码, 注意更改JDK版本！

JDK1.7
  • 对于 ArrayList 而言，它实现 List 接口、底层使用数组保存所有元素。
  • Ctrl F 快速查找方法… ArrayList.Java
底层使用数组实现
代码语言：javascript复制
private transient Object[] elementData;
构造器

ArrayList 提供了三种方式的构造器

  • 可以构造一个默认初始容量为 10 的空列表
  • 构造一个指定初始容量的空列表
  • 构造一个指定初始容量的空列表
  • 对应着三个不同的构造方法…
代码语言：javascript复制
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " 
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
        this(10);
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
add
代码语言：javascript复制
// 将指定的元素添加到此列表的尾部。
    public boolean add(E e) {
        ensureCapacityInternal(size   1);  // Increments modCount!!
        elementData[size  ] = e;
        return true;
    }
add(int index, E element)
代码语言：javascript复制
// 将指定的元素插入此列表中的指定位置
// 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加 1）。
    public void add(int index, E element) {
        rangeCheckForAdd(index);
// 如果数组长度不足，将进行扩容。
        ensureCapacityInternal(size   1);  // Increments modCount!!
        // 将 elementData 中从 Index 位置开始、长度为 size-index 的元素
        // 拷贝到从下标为 index 1 位置开始的新的 elementData 数组中。
		// 即将当前位于该位置的元素以及所有后续元素右移一个位置。
        System.arraycopy(elementData, index, elementData, index   1,
                         size - index);
        elementData[index] = element;
        size  ;
    }
扩容机制：
  • 从上面介绍的向 ArrayList 中存储元素的代码中，我们看到，每当向数组中添加元素时 都要去检查添加后元素的个数是否会超出当前数组的长度
  • 如果超出，数组将会进行扩容，以满足添加数据的需求。
  • 数组扩容通过一个公开的方法 ensureCapacity(int minCapacity) 来实现。
代码语言：javascript复制
    public void ensureCapacity(int minCapacity) {
    //判断扩展值大于0
        if (minCapacity > 0)
            ensureCapacityInternal(minCapacity);
    }
	//开始扩容
    private void ensureCapacityInternal(int minCapacity) {
        modCount  ;
        // overflow-conscious code
        //判断当前长度是否需要扩容！
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //执行扩容
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;	//原长度(假设2)
        int newCapacity = oldCapacity   (oldCapacity >> 1); //新长度 = 旧   旧右移1位！(二级制右移)
        //<<  左移		3<<2 : 3左移两位 结果就是 3*2*2=12;		左移几位就是 *几次2; 注意数值移动太多数值会出问题;(二级制~ 最后会出现负数) 左移在一定范围内 相当于*2        
		//>>  右移		3>>1 : 3右移一位 结果就是 3/2=1;		右移几位就是 /几次2; 注意数值移动太多数值会出问题; 右移在一定范围内 相对于/2
        // x = 2 (2>>1)=3 及一点五倍！
        
        //如果还是小于扩容的长度,直接等于改长度
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;	
            
        //如果新的数组容量newCapacity大于数组能容纳的最大元素个数 MAX_ARRAY_SIZE 
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        
        //把旧数组放进新的扩容后的数组    
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //那么再判断传入的参数minCapacity是否大于MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {
    	//传入的参数必须大于0，否者报错
        if (minCapacity < 0) 
            throw new OutOfMemoryError();
            
         //如果minCapacity大于MAX_ARRAY_SIZE
         //那么//newCapacity等于Integer.MAX_VALUE，否者newCapacity等于MAX_ARRAY_SIZE   
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

总结：

  • 当重新计算的容量（x1.5那个计算）小于传入要求容量参数，则新容量以传入的比较大的容量参数为准。
  • 当传入容量参数太大，大到超过了数组的容量限定值2^{31}-1-8却又小于整数限定值 2^{31}-1
  • 那么新的数组容量以整数限定值 2^{31}-1为准
  • 但是当传入的容量参数不大于数组的容量限定值时，以容量限定值2^{31}-1-8为准。
JDK1.8
  • 1.8 和 1.7 没有太大变化只是由原来的，饿汉更改为了懒汉
代码语言：javascript复制
//存放元素的数组，从这可以发现 ArrayList 的底层实现就是一个 Object数组
transient Object[] elementData;
//数组中包含的元素个数
private int size;
//数组的最大上限
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造方法
代码语言：javascript复制
public ArrayList() {
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
 if (initialCapacity > 0) {
 this.elementData = new Object[initialCapacity];
 } else if (initialCapacity == 0) {
 this.elementData = EMPTY_ELEMENTDATA;
 } else {
 throw new IllegalArgumentException("Illegal Capacit
y: " initialCapacity);
  • elementData 是一个大小为 0 的空数组
  • 当我们指定了初始大小的时候，elementData 的初始大小就变成了我们所指定的初始大小了。
add 添加方法：
代码语言：javascript复制
public boolean add(E e) {
 ensureCapacityInternal(size   1); // Increments modCou
nt!!
 elementData[size  ] = e;
 return true;
}
  • ArrayList 的 add 方法也很好理解，在插入元素之前，它会先检查是否需要扩容
  • 然后再把元素添加到数组中最后一个元素的后面。
  • 在 ensureCapacityInternal 方法中， 我们可以看见，如果当 elementData 为空数组时，它会使用默认的大小去扩容。
  • 通过无参构造方法来创建 ArrayList 时，它的大小其实是为 0 的， 只有在使用到的时候，才会通过 grow 方法去创建一个大小为 10 的数组。

LinkedList 源码分析

  • LinkedList 是通过一个双向链表来实现的，
  • 它允许插入所有元素，包括 null，同时，它是线程不同步的。
  • 双向链表每个结点除了数据域之外，还有一个前指针next和后指针prev
  • 分别指向前驱结点和后继结点（如果有前驱/后继的话）。
  • 双向链表还有一个 first 指针，指向头节点，和 last 指针，指向尾节点。 即当前,LinkedList 最后一个节点, 和第一个节点！
LinkedList 中的属性：
代码语言：javascript复制
//链表的节点个数
transient int size = 0;
//指向头节点的指针
//整个List集合中的第一个元素！
transient Node<E> first;
//指向尾节点的指针
//整个List集合中最后一个元素！
transient Node<E> last;
  • 当然如果集合中就一个元素，它即是first 也是 last
结点结构
  • Node 是在 LinkedList 里定义的一个静态内部类 该类只在LinkedList中使用到！
  • 它表示链表每个节点的结构，包括一个数据域 item，一个后置指针 next，一个前置指针 prev。
代码语言：javascript复制
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
  • item 实际的元素
  • 因为LinkedList是一个双向链表，next prev 分布表示 item 的下一个元素 和 上一个元素！
add
代码语言：javascript复制
//对外保留的添加方法！
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
	//获取当前最后一个节点
    final Node<E> l = last;			
	//创建e要添加的节点,因为新增是增在最后的,也不需要指定 next下一个元素位置... 
    final Node<E> newNode = new Node<>(l, e, null);
	//并把这个新增的设置为 最后一个节点！
    last = newNode;
    
    //判断最后一个是否为null 
    	//如果为null 就表示这个集合还没有一个元素！没有最后一个元素！
    	//那我就是第一个元素了,并把值赋值给first节点！
    	//else
    	//已经存在元素,把最后一个元素的下一个节点指向e. 因为现在e是才是最后一个！
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    //长度  
    size  ;
    modCount  ;
}
linkFirst 第一个位置添加元素
代码语言：javascript复制
private void linkFirst(E e) {
	//获取当前集合中第一个元素
    final Node<E> f = first;
    //创建e 为第一个元素,因为是第一所有没有prev
    final Node<E> newNode = new Node<>(null, e, f);
    //e成为第一个元素
    first = newNode;
    //判断第一个元素是否为null,表示当前集合啥也没有！  e即是第一也是最后！
    //else f不在是第一,并指向e
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size  ;
    modCount  ;
}
linkLast 最后一个位置添加元素
代码语言：javascript复制
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  ;
}
  • 将e 设置成为 last 并将上一个 last指向e…

ok.现在回头看发现，双向链表果然时候新增！

  • 在任何位置新增，只需要将 前后元素进行链接即可！

Vector 源码分析

Vector 是一个古老的集合，JDK1.0就有了。 已经淘汰很少有人使用了！官方已经停止更新了！

  • 大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。
  • 7/8没变化， 底层默认数组长度10,每次扩容2倍！

ArrayList LinkedList Vector 异同

同

  • 三者都实现了List 接口 存储数据特点相同： 有序 可重复数据！

异

ArrayList和LinkedList的异同

  • 二者都线程不安全，相对线程安全的Vector，执行效率高。
  • ArrayList是实现了基于动态数组的数据结构 LinkedList基于双向链表的数据结构 对于随机访问get和set，ArrayList觉得优于LinkedList 因为LinkedList要移动指针 对于新增和删除操作add(特指插入)和remove，LinkedList比较占优势 因为ArrayList要移动数据。

ArrayList和Vector的区别

  • Vector和ArrayList几乎是完全相同的 底层都是动态数据结构
  • 唯一的区别在于Vector是同步类(synchronized) 因此开销就比ArrayList要大，访问要慢。 大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。
  • Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍
  • Vector还有一个子类Stack

Set接口

Set 概述：

Set接口是Collection的子接口 set接口没有提供额外的方法 存储无序, 唯一的数据

  • 无序： 无序，不表示随机！ 只是, 存入数据在 底层数据上的位置 有自己的一套规则
  • 唯一： 通过, hashCode和 equals 方法实现，存储数据唯一！
  • 实现类： HashSet： set接口的主要实现类，线程不安全，可以存储null值； LinkedHashSet： 作为HashSet在子类，遍历内部数据时，可以按照添加时的顺序进行展示！ 但不代表，它是有序！ TreeSet 　set 接口的实现类，无序,唯一! 存储的数据都是统一类型的! 　可以对新增的元素 , 内部指定一个排序规则: 自然排序 定制排序 (Java类比较强)

HashSet

实例:

User.Java 自定义对象类型

代码语言：javascript复制
public class User {
    private int id=0;
    private String name;
	//get/set/无参有参构造...
}

CSDemo 非常正常的一个 HashSet使用

代码语言：javascript复制
public class CSDemo {
    public static void main(String[] args) {
        //创建新增元素！
        HashSet hset = new HashSet();
        hset.add(123);
        hset.add(123);
        hset.add(456);
        hset.add("ABC");
        hset.add("DEF");
        hset.add(new User(1, "张三"));
        hset.add(new User(1, "张三"));

        //遍历输出
        Iterator it = hset.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
    }
}
  • 可以看到, hashset 确实是 无序,唯一 的
  • 两次 123 都,直接输出不了了 并且输入顺序 和输出的顺序并不一样…
  • 但. 两个User对象…确并不是结果唯一 这是为什么呢? set不是值唯一吗? 接下来让我们来深入源码!
HashSet 实现分析:
  • 进行 深入 HashSet() 构造!
  • 我们发现,HashSet的构造其实就是 HashMap HashSet的值存放于HashMap的key上 HashMap的value统一为PRESENT 那么, 这里就不深入了解了…后面对HashMap进行深入!
  • 而我们通过上面的代码,发现 两个一模一样的对象, 为什么出现了两次, 不是唯一值吗?
HashSet 存储原理:
  • 首先, 我们已经知道, Hashset 底层就是HashMap 而, 一般要进行存储唯一的元素, 难免要对元素进行, 比较是否一致, 一致则不添加! 不一致添加HaseSet集合 Java 中进行比较的方法我们也都知道是 equals() 而, equals其实本质上就是 == 比较地址, 上面两个对象地址不同当然不同,所以是唯一的!
  • 没错, HashSet 也确实是这么干的, 通过比较equals 对象是否true 一致 则不新增!
  • 如果, 我们想对新增的对象,类型的值,进行比较唯一, 对equals重写..即可! 不同地址对象, 值相同添加失败! 实现唯一的效果!
  • 但 如果,只是重写 equals理论上确实可以实现效果... 实际却并不是这样! 改变上面 User 重写equals 执行!

实际情况,直接使用 工具重写即可!

  • 执行之后, 发现效果并不变, 还是两个 id=1 name=张三
总结: ❗
  • HashSet 本质上就是一个: 数组 链表

初始容量为16，当如果使用率超过0.75 负载因子（16*0.75=12） 就会扩大容量为原来的2倍。32 64...

HashSet 集合判断两个元素相等的标准 唯一 / 无序

  • 直接通过equals 其实就可以,实现 唯一 的特点,但因为这样会极大影响程序性能! 一个个eq比较,如果集合有 10个 100个 1000个难道每次新增都要比较...? 太垃圾了!
    对象 集合 数组 源码 java

    0 人点赞