java集合知识

发表于 | 分类于

集合接口：Collection、Map

1.Collection接口下面存在的接口有：List，Set.

1.1.List集合接口的实现类有：AarryList、Vector、LinkedList、AbstractList、SynchronizedList等

1.2.Set集合接口的实现类有：HashSet、AbstractSet、SynchronizedSet、LinkedHashSet，TreeSet等

2.Map接口：

2.1.Map集合接口的实现类有：HashMap、RefereneMap、LinkedHashMap、TableMap、CopyOnWriteHashMap等

一.List集合

1.ArrayList知识点

1.继承实现关系：

1
2
3
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
1.ArrayList继承了AbstractList抽象类、现实了List接口、RandomAccess接口、Cloneable接口以及序列号接口

2.属性字段理解：

2.1 DEFAULT_CAPACITY

1
2
3
4
/**
 * Default initial capacity. 默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

2.2 EMPTY_ELEMENTDATA

1
2
3
4
5
/**
 * Shared empty array instance used for empty instances.
 用于空实例的共享空数组实例。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

2.3 DEFAULTCAPACITY_EMPTY_ELEMENTDATA

1
2
3
4
5
6
7
/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 用于默认大小的空实例的共享空数组实例。我们 将其与空的element数据区分开来，以了解何时扩张添加第一个元素。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

2.4 elementData

1
2
3
4
5
6
7
8
9
10
11
/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 存储ArrayList的元素的数组缓冲区。
ArrayList的容量是此数组缓冲区的长度。 任何
具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList
添加第一个元素时，将扩展为DEFAULT_CAPACITY
 */
transient Object[] elementData; // non-private to simplify nested class access

2.5 size

1
2
3
4
5
6
/**
 * The size of the ArrayList (the number of elements it contains).
 *ArrayList的大小（它包含的元素数）。
 * @serial
 */
private int size;

3.方法的解读

ArrayList(int initialCapacity)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 构造一个指定了初始容量的Lsit列表
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
	//初始容量的参数大于0则new一个类型为Object数组且长度大小为initialCapacity,然后复制给elementData
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
    //等0则用一个空的Object类型数据给elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

ArrayList()

1
2
3
4
5
6
7
/**
 * Constructs an empty list with an initial capacity of ten.
 	构造一个空的Object类型的数据
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 按照集合迭代器返回的顺序构造一个包含指定集合元素的列表。
 * @param c the collection whose elements are to be placed into this list
 将其元素放置到此列表中的集合
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
	//将其转换为Object类型的数组
    Object[] a = c.toArray();
    //如果目标数组的大小等于本身数组的大小且不等于0则判断目标类地址是否为ArrayList.class如果是则将其值赋值给本数组、否则执行copyOf()将其复制到一个指定大小为size类型为Object数组的新数组中然后将其赋值给本数据
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.赋默认类型为object的空引用数组
        elementData = EMPTY_ELEMENTDATA;
    }
}

trimToSize

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 * list's current size.  An application can use this operation to minimize
 * the storage of an <tt>ArrayList</tt> instance.
将此<tt>ArrayList</tt>实例的容量修剪为
列表的当前大小。应用程序可以使用此操作最小化
<tt>ArrayList</tt>实例的存储。
 */
public void trimToSize() {
	//ArrayList修改的次数
    modCount++;
    //如果list的大小节点数据长度
    if (size < elementData.length) {
    //如果为0则给默认的Object[]的给elementData,否则复制一份长度为size的数据给elementDate
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

elementData(int index)

1
2
3
4
E elementData(int index) {
	//获取指定索引位置的数据
    return (E) elementData[index];
}

get(int index)

1
2
3
4
5
6
public E get(int index) {
	//检查是否索引越界
    rangeCheck(index); //index >= size 则抛出索引越界
	//获取指定索引位置的数据
    return elementData(index);
}

set(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Replaces the element at the specified position in this list with
 * the specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
	//检查是否索引越界
    rangeCheck(index);
	//获取指定索引下的数据
    E oldValue = elementData(index);
    //再将新的值赋值给指定索引的数组
    elementData[index] = element;
    //返回旧的数据
    return oldValue;
}

add(E e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Appends the specified element to the end of this list.
 *将指定的元素追加到此列表的末尾。
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!! 这一步递增修改的次数
    elementData[size++] = e;
    return true;
}
//扩容机制minCapacity（最小容量)的值为数组本身的size大小+1   步骤一
private void ensureCapacityInternal(int minCapacity) {
	//elementData 数组本身数据
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量 步骤二
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	//判断是否为默认的空数组
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
	//如果是则信息max取最大值运算，如果最小容量比默认容量10大则返回minCapacity
	return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	//直接返回最小容量数
	return minCapacity;
}
//确保准确的容量 步骤三
private void ensureExplicitCapacity(int minCapacity) {
        modCount++; //修改的次数递增1

        // overflow-conscious code
        //判断最小容量 - 数组本身的大小是否大于0，大于0进行扩容
        if (minCapacity - elementData.length > 0)
        //真正的扩容步骤
            grow(minCapacity);
    }
  //扩容 步骤四  
 private void grow(int minCapacity) {
        // overflow-conscious code
        //拿到扩容前的数组长度（old）
        int oldCapacity = elementData.length;
        //用old长度右移1位（除以2的一次方）,再加上old的长度等于新的容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新容量 - 去最小容量 < 0 则将最小容量的值赋值给新容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新容量 - Intger.Max - 8 > 0  则进行步骤5
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //最后将数组本身扩到长度为newCapacity大小的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
  //扩容 步骤五（巨大的扩容）
 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
            //最小容量 > Intger.Max - 8 则取Integer.max否则取 Intger.Max - 8
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add(int index, E element)

1
2
3
4
5
6
7
8
9
10
public void add(int index, E element) {
	//检测索引是否越界及idenx是否>0
    rangeCheckForAdd(index);

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

remove(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public E remove(int index) {
	//检测索引是否越界
    rangeCheck(index);
	//修改次数递增1次
    modCount++;
    //获取到指定索引下的数据
    E oldValue = elementData(index);
    //删除的索引数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //数组大小减1并赋值为Null触发gc
    elementData[--size] = null; // clear to let GC do its work
	//返回被删除的数据内容
    return oldValue;
}

remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

4.知识总结：

  1. 线程安全方面：线程不安全的

  2. 是有序的、可以存Null值。

  3. 容量扩容方面：默认容量为10，扩容的方法是copyOf(), 扩容大小为50%，细节看add方法）

  4. 底层结构：Objcet类型的数组，Object []

2.Vector

和ArrayList基本上一样。

  1. 线程安全方面：线程安全的，它的方法被synchronized修饰
  2. 是有序的、可以存Null值。
  3. 容量扩容方面：默认容量为10，扩容的方法是copyOf(), 扩容大小为原来的1倍，细节看add方法）
  4. 底层结构：Objcet类型的数组，Object []

3.LinkedList

1.继承实现关系

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

2.字段属性理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
transient int size = 0;
/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 * 第一个节点
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 * 最后一个节点
 */
transient Node<E> last;

3.方法的解读

双向链表Node结构

1
2
3
4
5
6
7
8
9
10
11
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;
    }
}

LinkedList()

1
2
3
4
5
/**
 * Constructs an empty list. 构造一个空的List
 */
public LinkedList() {
}

linkLast

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Links e as last element.
 */
void linkLast(E e) {
	//获取最后节点链表数据
    final Node<E> l = last;
    //实例化一个链表节点信息l表示prev上一节点指针、e表示本节点内容item、next表示下一个节点指针这个传null
    final Node<E> newNode = new Node<>(l, e, null);
    //将newNode赋值给最后节点last，即让last的引用地址指向newNode。
    last = newNode;
    //如果l为null表示第一次add，则将newNode的值赋值给first节点，否则将newNode数据赋值给上一节点中的next指针
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
        //节点大小加1
    size++;
    //修改次数加1
    modCount++;
}

linkBefore

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Inserts element e before non-null Node succ.
 * 在非null节点succ之前插入元素e
 * E e 表示要插入的节点元素
 * Node<E> succ 原来索引位置的节点元素（old）
 * 简单理解：
 * E 为需要在指定索引位置插入的新节点内容 、
 * succ 为指定索引位置的原数据内容。
 * 步骤一：将old节点数据的prev节点拿出来存储在pred。
 * 步骤二：新建一个新节点内容为e（代替原节点）,e的前节点指向pred（指向原节点的前节点）,e.后节点指向old（原节点）（succ）
 * 步骤三：需要需要将old(succ)节点的前节点(succ.prev)引用地址改为：新节点（newNode）
 * 步骤四：判断原节点的前节点是否为null，为null表示头节点，直接将新节点指向first节点，否则将新节点引用指向old(原节点)的前节点的next（也就是原节点的上一个节点的next要指向新节点的地址）。
 * 以上4步就完成了所有节点的指向问题。完成了节点的插入
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //获取old接口的前节点指针元素、将其赋值给pred
    final Node<E> pred = succ.prev;
    //新实例化一个节点其内容为e，前节点指向pred、下节点指向succ（old）
    final Node<E> newNode = new Node<>(pred, e, succ);
    //其次将old节点中的前节点引用地址指向心插入的节点地址（newNode）
    succ.prev = newNode;
    //判断old节点的前节点是否为Null,为null表示是第一个节点，则将新节点地址指向first节点
    //否则将新节点引用指向old节点里面的next节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
     //节点长度+1
    size++;
    //修改次数加+
    modCount++;
}

node(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Returns the (non-null) Node at the specified element index.
 */
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;
    }
}

add(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * 在指定索引位置插入元素
 */
public void add(int index, E element) {
	//判断是否索引越界
    checkPositionIndex(index);
	//判断索引是否等于目前链表的最大值是则直接在尾部追加，否则执行插入操作
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

set(int index, E element)

1
2
3
4
5
6
7
8
9
10
public E set(int index, E element) {
	//检测索引是否非法
    checkElementIndex(index);
    //二分法获取指定索引下面的数据
    Node<E> x = node(index);
    //将指定索引数据里面的item取出来并返回然后将新的值赋值给指定索引
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

remove(int index)

1
2
3
4
5
public E remove(int index) {
	//删除指定索引下的数据，先检测索引的合法性
    checkElementIndex(index);
    return unlink(node(index));
}

unlink（Node x）删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
总体步骤理解：删除指定索引的数据其实是将next、prev及本身item的引用置为null，
然后再将其将prev（前节点）中的next指向后节点，将后节点中的prev指向前节点
这个需要注意的一点需要判断前、后节是否为空
E unlink(Node<E> x) {
    // assert x != null;
    //拿取索引数据本身数据
    final E element = x.item;
    //拿取索取数据的前节点数据
    final Node<E> next = x.next;
    //拿取索引数据的后节点数据
    final Node<E> prev = x.prev;
	//判断前节点（prev）内容是否为null、为Null表示本节点就是first节点所以直接将后节点(next)数据给first数据。不为null则将前节点(prev)中的后节点(prev.next)引用地址指向后节点(next)。再将本节点(x)的前节点(x.prev)引用地址置为Null
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
//判断后节点(next)是否为null,为null表示本节点就是last节点所以直接将前节点(prev)数据给last，不为null则将后节点(next)中的前节点(next.prev)引用地址指向前节点(prev)然后将本身的后节点(x.next)引用指向null，最后将本身数据(x.item)置为Null再将链表大小减一、修改次数加1,最后返回本次吃删除的数据内容
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

4.知识总结

  1. 线程安全方面：线程不安全的
  2. 是有序的、可以存Null值。
  3. 容量扩容方面：无扩容、默认链表大小为0
  4. 底层结构：Node的双向链表结构

二.Set集合

1.HashSet知识点

1.HashSet继承实现关系

1
2
3
4
5
//继承了AbstractSet类、实现了Set、和Cloneabl、Serializable接口
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{}

2.字段属性理解

1.HashMap

1
2
HashSet数据结构就是用的HashMap只不过不需要传value值
private transient HashMap<E,Object> map;

PRESENT

1
2
默认作为Map的value
private static final Object PRESENT = new Object();

3.方法解读

HashSet()

1
2
3
4
5
6
7
8
/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 * 默认new的HashSet(),实际底层是实例化了一个HashMap,默认的容量为16，负载因子为0.75
 */
public HashSet() {
    map = new HashMap<>();
}

add(E e)

1
2
3
4
public boolean add(E e) {
//新增元素，默认调用的是map的Put方法，value值为默认的object
    return map.put(e, PRESENT)==null;
}

remove(Object o)

1
2
3
4
public boolean remove(Object o) {
//删除也是调用的map的remove
    return map.remove(o)==PRESENT;
}

1.TreeSet知识点

1.TreeSet的继承实现关系

1
2
3
4
//继承了AbstractSet类、实现了NavigableSet接口、这个接口又继承了SortedSet接口所以这个TreeSet是有序的
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{}

2.字段属性知识

1.NavigableMap

1
2
TreeSet的底层结构是NavigableMap
private transient NavigableMap<E,Object> m;

2.PRESENT

1
2
NavigableMap中Vaule的值。
private static final Object PRESENT = new Object();

3.方法解读

TreeSet()//先熟悉HashMap及树知识再来理解TreeSet的知识

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//TreeSet的默认构造函数
public TreeSet() {  步骤1
    this(new TreeMap<E,Object>());
}

/**
* Constructs a set backed by the specified navigable map.
*/
TreeSet(NavigableMap<E,Object> m) { 步骤3
	this.m = m;
 }

//TreeMap类
  private final Comparator<? super K> comparator;

    private transient Entry<K,V> root;

    /**
     * The number of entries in the tree
     */
    private transient int size = 0;

    /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;
public TreeMap() {  步骤2
    comparator = null;
}

add(E e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public boolean add(E e) {
	//m.put进入的TreeMap类里面的put
    return m.put(e, PRESENT)==null;
}
//put后的排序、规则里面用到了红黑树
public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

4.知识总结

三.Map集合

1.HashMap

1.继承实现类

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {}

2.字段属性说明

DEFAULT_INITIAL_CAPACITY（默认初始容量16）

1
2
3
4
5
/**
 *
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

MAXIMUM_CAPACITY（Map容量的最大值2的30幂次方）

1
2
3
4
5
6
/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;