【总结】Java集合(Set、List、Queue)

Java集合

简介

Java集合大致可分为Set、List、 Queue和Map四种体系,其中Set代表无序、不可重复的集合; List代表有序、重复的集合;而Map则代表具有映射关系的集合,Java 5又增加了Queue体系集合,代表一种队列集合实现。集合类主要负责保存、盛装其他数据,因此集合类也被称为容器类。所有的集合类都位于
java.util包下,后来为了处理多线程环境下的并发安全问题,Java 5还在java utilconcurrent包下提供了一些多线程支持的集合类。

【总结】Java集合(Set、List、Queue)

Collection是一个接口,Map没有继承Collection。

Set和Map很相似,Set底层是Map实现的。Map和List的实现比较重要

Set

01 / HashSet

HashSet是Set接口的典型实现,HashSet不能 保证元素的排列顺序,它是非线程安全的,并且集合内元素的值可以是nullHashSet底层 是由HashMap实现的,它将元素存到了HashMap的key上,而对应的value则是一个空对象。

底层数据怎么存的?

有序和无序怎么保证的?

扩容机制?

//transient,该属性不需要序列化,因为只把数据存在了map的k上,即v为空,浪费空间
private transient HashMap<E,Object> map; //底层存数据
//map中的v存固定的PRESENT,而不是null,起到判断比较的作用,null无法比较,常量可以
 private static final Object PRESENT = new Object();

//构造器,初始化map
 public HashSet() {
        map = new HashMap<>();
    }

//添加数据的方法
 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

//移除
public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

//迭代方法
 public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

//重写序列化方法,只序列化key
 for (E e : map.keySet())
            s.writeObject(e);

02 / TreeSet

TreeSet可以确保集合元素处于排序状态(按照数据的值排序,可以自定义排序规则),TreeSet支持 自然排序和定制排序两种排序方式,它的底层是由TreeMap实现的。TreeSet也是非线程安全的,但是它内部元素的值不能为null(要排序,null没法比较)。

 private transient NavigableMap<E,Object> m;


//底层实现
 public TreeSet() {
        this(new TreeMap<E,Object>());
    }
//添加和移除,iterator,序列化和上面的HashSet一样

List

01 / ArrayList

ArrayList是基于数组实现的List,所以ArrayList封装 了一个动态的、允许再分配的Object数组。
ArrayList对象使用initialCapacity参数来设置该数组的长度,当 向ArrayList中添加元素超出了该数组的长度时,它的initialCapacity会 自动增加,即ArrayList会自动扩 容。若需要对ArrayList缩容,则需要主动调用trimToSize()。会主动扩容但不会主动缩容

源码解读:

定义和初始化:

 /**
     * Default initial capacity.首次初始化数组,默认长度为10
     */
    private static final int DEFAULT_CAPACITY = 10;

//两个空的数组,区分创建集合的时候是默认长度还是指定长度,两者方式再扩容机制上不一样
 private static final Object[] EMPTY_ELEMENTDATA = {};

 
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//数组中存储的具体元素
 transient Object[] elementData;

//实际存放的数组长度
private int size;

 /**
     * Constructs an empty list with an initial capacity of ten.创建一一个默认的容量为10的数组
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//初始化数组
 public ArrayList(int initialCapacity) {
     //如果指定容量大于0,创建一个指定容量的数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//等于0,创建一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//小于0报错
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

扩容机制(当数组追加到一定范围,即添加数据时)

默认长度为10,每次在上一次的容量基础上,扩展1.5倍。每次扩容其实是将原数组的数据拷贝到创建的新数组里面

 public boolean add(E e) {
     //先扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;//追加数据
        return true;
    }

//怎么扩容的呢?算好一个容量,算好之后穿过来
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

//怎么计算的容量?


private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //数组是默认构造器创建时
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //在默认容量和最小容量取最大值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
    //当你使用的是有参构造器,直接返回你指定的容量
        return minCapacity;
    }

//以上总体来说就是要不要考虑默认容量

//算好容量之后,开始扩容
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code先判断一下要扩容的容量是否大于数组的长度
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

//grow扩容
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//获取数组旧的容量
    //新的容量=老的容量+老的容量的一半(1.5倍)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    //超过int容量的最小值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    //超过int容量的最大值
        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);
    }


//数组容量溢出处理
 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

List迭代

//两个迭代器
//因为继承关系具有的迭代器
public Iterator<E> iterator() {
        return new Itr();
    }
//list自己加的迭代器
 public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

 private class Itr implements Iterator<E> {
        int cursor; //当前游标
     	int lastRet = -1; //上一次迭代的位置(当前位置的前面??不一定)
     int expectedModCount = modCount;//期望得修改次数,在迭代的过程中,判断次数相等,不相等说明在迭代的过程中,你修改了(即判断在迭代的过程中,能不能修改数据)
     //在迭代的过程中,删除数据时要先判断一下修改次数
 }

自己的itertor实现排序,增加ListIterator是为了增加迭代的顺序,实现可以从前往后,从后向前,从中间迭代

//是itertor的子类,在其基础上扩展了一些东西
private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) { //指定位置开始迭代
            super();
            cursor = index;
        }
    
    public E previous() {//向前迭代,
            checkForComodification();//先检查修改次数,继承的
        int i = cursor - 1;
    }
    //要覆盖某个值也要检查修改次数
    ArrayList.this.set(lastRet, e);//把刚刚访问的元素覆盖掉
    
    //添加
     public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);//将元素
            }
     }

缩容:

public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

总结:

1、数组实现,默认长度为10,每次扩容1.5倍。每次扩容其实是将原数组的数据拷贝到创建的新数组里面。

2、在迭代的过程中检查修改次数,如果数据被改,就不能迭代下去。

3、支持ListIterator,可以更灵活的进行迭代。

02 / LinkedList

LinkedList是基于双向链表实现的List,它内部的元素可以为nul、可以重复,LinkedList是非线程 安全的。

源码解读:

定义和结构:

transient int size = 0;//连表里有多少个节点
transient Node<E> first;
transient Node<E> last;
//Node节点有前驱和后继,所以是双向链表
 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
 }

添加数据:

public boolean add(E e) {
    linkLast(e); //到链表末尾
    return true;
}

//指定位置的添加
 public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

获取数据:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

设置值

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

删除:

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

node方法根据节点获取索引

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {//节点位于前半部分
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {//节点从后面开始迭代
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Queue

Queue用于模拟队列,它是一种先进先出 (FIFO) 的容器。

【总结】Java集合(Set、List、Queue)

常用方法offer,poll

Deque

Deque代表双端队列,它允许你从两端来操作队列中的元素,并支持入栈及出栈操作。Deque在Queue的基础上,增加了如下两类方法:

【总结】Java集合(Set、List、Queue)

选择一端进行操作

【总结】Java集合(Set、List、Queue)

01 / ArrayDeque

ArrayDeque底层通过数组实现,为了满足可以同时在数组两端插入或删除元素的需求,该数组还必须是循环的,即循环数组,也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是 非线程安全的,另外该容器不允许放入null元素。

双端队列基于数组实现,

源码解读:

 transient Object[] elements;//由数组实现,数据放数组里
transient int head;//头部索引
transient int tail;//尾部索引
//默认最小容量
private static final int MIN_INITIAL_CAPACITY = 8;

//构造器,默认初始化长度为16
 public ArrayDeque() {
        elements = new Object[16];
    }
//指定数组大小时,并不是按照你指定多少就是多少,他要计算一下
private void allocateElements(int numElements) {
        elements = new Object[calculateSize(numElements)];
    }

//计算容量(你指定的时候他要扩展为比你指定大的最近的,2的n次方)
private static int calculateSize(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        if (numElements >= initialCapacity) {//大于等于最小长度
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        return initialCapacity;
    }

ArrayDeuqe的容量一定是2的n次方

入队:

public boolean offer(E e) {
    return offerLast(e);
}
public boolean offerLast(E e) {
        addLast(e);
        return true;
    }
//往头部增加数据
public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
    //先算头指针下标
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();//扩容
    }

扩容:

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;//数组的长度
    //头指针右侧的元素数量
    int r = n - p; // number of elements to the right of p
    //新的容量是原来的2倍
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    //数组拷贝,先拷贝头指针右侧的数据,再拷贝头指针左侧的数据
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

出队:

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    //删除头指针
    elements[h] = null;  // Must null out slot
    //头指针移位
    head = (h + 1) & (elements.length - 1);
    return result;
}

public E pollLast() {
    //尾节点
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;//尾指针左移
        return result;
    }

双端队列当作栈来用

public void push(E e) {
        addFirst(e);//上面讲过了
    }
public E pop() {
        return removeFirst();//一个方向来进和出就是栈
    }

02 / LinkedList

除了实现List接口之外,LinkedList还实现 了Deque接口,可以被当成双端队列来使用,因此既可以被当成“栈"来使用,也可以当成队列使用。

源码解读:

public boolean add(E e) {
    linkLast(e);
    return true;
}

//入队:添加到前面去,
private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

//出队
public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
//解除节点的双向关系
private E unlinkFirst(Node<E> f) {
       。。。
    }

栈的方法:

  public void push(E e) {
        addFirst(e);
    }

 
 public E pop() {
        return removeFirst();
    }
上一篇:集合框架之HashMap(一)


下一篇:集合 Vector