集合介绍

评论

一、什么是集合

  • 概念：对象的容器，定义了对多个对象进行操作的常用方法。可实现数组的功能
  • 和数组的区别
    • 1、数组的长度是固定的，集合长度不固定
    • 2、数组可以存储基本数据类型和引用类型。集合只能存储引用类型

二、Collections集合

alt="collection集合"

2.1 Collection是一个接口，是高度抽象出来的集合，它包含了集合的基本操作和属性。

Collection包含了List和Set两大分支

  • (01) List是一个有序的队列，每一个元素都有它的索引。第一个元素的索引值是0。

    List的实现类有LinkedList, ArrayList, Vector, Stack。

  • (02) Set是一个不允许有重复元素的集合。

    Set的实现类有HastSet和TreeSet。HashSet依赖于HashMap，它实际上是通过HashMap实现的；TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。

三 、List接口

  • 特点：有序、有下标、元素可以重复
  • 左移n位就相当于乘以2的n次方
  • 右移n位相当于除以2的n次方
1、ArrayList

  • 数组接口实现、查询快、增删慢

  • jdk1.2版本，运行效率快、线程不安全

    源码分析部分

  • 默认容量大小为 DEFAULT_CAPACITY = 10

  • 注意：如果集合中未添加元素，容量为0

  • emementData 存放元素

  • size 元素大小

  • 默认大小为10 一次扩容后变为原来的1.5倍

    1
    2
    3
    4
    5
    6
    public boolean add(E e) {
        //size默认0
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
1
2
3
4
5
6
7
8
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //minCapacity = 10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}
1
2
3
4
5
6
7
8
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    //10-0 = true
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
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);
}
2、LinkedList

  • 链表结构实现、查询慢，增删快

  • 双向链表

    源码分析部分
    1
    2
    3
    4
    5
    //添加元素
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /**
     * Links e as last element.
     */
    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++;
    }
3、Vector
  • 数组结构实现、查询快、增删慢
  • JDK1.0出现，运行效率慢，线程安全

四、Set 集合

  • 特点：无序、无下标、元素不可重复
1、HashSet

  • 基于hashCode计算元素位置

  • 当存放的元素哈希码相同时，会调用equals进行确认，如果为true，则拒绝后者存入

  • 存储结构为哈希表（数组+链表+红黑树）

    存储过程

    • 1、根据hashCode计算保存的位置，如果此位置为空，直接保存
    • 2、在执行equal方法，如果equals方法为true，则认为重复，否则形成链表
    • 重写了hashCode方法，一定要重写equals方法
2、TreeSet

  • 基于排序顺序实现元素不重复

  • 实现了sortedSet接口，对集合元素自动排序

  • 元素对象类型必须实现comparable接口，指定排序规则

  • 基于红黑树

    存储结构

    • 红黑树

五、Map

1、HashMap

  • 基于哈希表实现（数组+链表+红黑树）

  • 线程不安全，运行效率快；允许为key value为null

    哈希map源码分析

    • 1、刚创建时是null，添加元素后，默认初始容量 16

    • 2、默认加载因子0.75 （每次扩容为原来的2倍（目的是减少调整元素的个数），在什么时候扩容，当容量达到16*0.75时，扩容）

    • 3、jdk1.8 如果数组的大小>=64 且链表的长度大于8，则会把链表转成红黑树

    • 4、jdk1.8 当树的节点数小于6时，转为链表结构

    • 5、jdk1.8 以前，链表是头插入 1.8以后是尾插入

2、HashTable
  • 线程安全，运行效率低；不允许key和value为null
  • 默认容量11 加载因子0.75
3、TreeMap
  • 实现了SortedMap接口（是Map的子接口），可以对key自动排序
  • 基于红黑树实现的

迷途小书童iOS & java

坚持、主动、积极、优秀