Java核心-集合_java核心集合

集合的本质

集合的主要作用是存储对象的容器.，常用的容器(集合)类,有ArrayList,HashMap,HashSet.等等
不同的集合容器类,他的特点不一样,或者说不同的集合类，可以基于不同的场景进行选择。集合(容器)的底层是由于数据组织的方式不一样,或者这么理解,出现不同的集合是因为他们的数据结构不一样,从而出现了不同的特性.

数据结构的优劣势分析

数组

• 连续的空间要求
• 可以通过下标的成员访问,下标访问的性能高
• 增删操作带来更大的性能消耗(保证数据越界的问题,需动态扩容)
• 典型的JAVA 集合类ArrayList , HashMap
  

链表(双向为例)

• 灵活的空间要求,存储空间不要求连续
• 不支持下标的访问.支持顺序的遍历搜索(LinkedList 有下标访问,怎么回事?LinkedList 详细讲解)
• 针对增删操作找到对应的节点改变链表的头尾指向即可,无需移动元素存储位置.
• 典型的Java 集合类：LinkedList
  

树(二叉查找树)

• 灵活的空间要求,存储空间不要求连续,可按指定顺序进行排列.
• 不支持下标的访问,支持近似二分的查找访问方式
• 增删操作有一个节点查找的过程,操作之后还存在树的平衡保证问题
• 增删改变节点的引用关系,无需移动元素的存储位置
• 典型的Java 集合类：TreeMap

集合的派系整体认识

Java 中集合类分为2 大主要派系，Collection 和Map
我们从ArrayList 入手整理出Collection 的派系

Collection

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

• List 是一个有序的队列，每一个元素都有它的索引。List 的实现类有LinkedList, ArrayList, Vector
• Set 是一个不允许有重复元素的集合。Set 的实现类有HashtSet 和TreeSet。
  HashSet 依赖于HashMap.它实际上是通过HashMap 实现的；TreeSet依赖于TreeMap，它实际上是通过TreeMap 实现的。

Collection 接口中定义了针对集合元素的基本增删查的相关操作.

增:

boolean add(E e);
boolean addAll(Collection<? extends E> c);
1
2

删:

boolean remove(Object o);
boolean removeAll(Collection<?> c);
void clear();
1
2
3

查:

containsAll(Collection<?> c);
1

实现了Iterable 接口来完成集合中元素的遍历能力

Iterator<T> iterator();
1

Iterator

Iterator 是一个接口，它是集合的迭代器。集合可以通过Iterator 去遍历集合中的元素。Iterator 提供的API 接口，包括：是否存在下一个元素、获取下一个元素、删除当前元素

abstract boolean hasNext()
abstract E next()
abstract void remove()
1
2
3

我们从HashMap 入手整理出Map 派系

Map

Map 是一个映射接口即key-value 键值对

• Map 提供接口分别用于返回键集、值集或键-值映射关系集。

entrySet()用于返回键-值集的Set 集合
keySet()用于返回键的Set 集合
values()用户返回值集的Collection 集合
1
2
3

因为Map 中不能包含重复的键；每个键最多只能映射到一个值。所以，键- 值集、键集都是Set ， 值在Map 中是可以允许重复的所有值集是Collection。

• Map 提供了“键-值对”、“根据键获取值”、“删除键”、“获取容量大小”等基本方法。

V get(Object key);
V remove(Object key);
int size();
1
2
3

Map 派系与Collection 是什么关系?

大家用HashMap 应该都有针对HashMap 的key 和value 进行遍历的操作吧。具体使用如:

hashMapObj.keySet() 
hashMapObj.values()
1
2

所以整理来讲Map 派系需要依赖Collection 派系.而在我们Collection 的Set 分支中,HashSet 和TreeSet 又是依赖于HashMap 和TreeMap 进行实现(具体分析在后续Set 集合类中)

Collection–List

ArrayList

ArrayList 他的底层数据结构是以数组的方式进行组织数据的，且通过一定的算法逻辑动态扩容数组的长度,或可理解ArrayList 底层是一个动态数组。与Java中的原生的数组相比，它的容量能动态增长.

继承结构说明

• AbstractCollection
  实现了Collection 中大量的函数,除了特定的几个函数iterator()和size()之外的函数

• AbstractList
  该接口继承于AbstractCollection，并且实现List 接口的抽象类。它实现了List 中除size()、get(intlocation)之外的函数。AbstractList 的主要作用：它实现了List 接口中的大部分函数
  和AbstractCollection 相比，AbstractList 抽象类中，实现了iterator()接口

• RandomAccess

RandmoAccess 接口，即提供了随机访问功能。RandmoAccess 是java 中用来被List 实现，为List 提供快速访问功能的。在ArrayList 中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。

List

有序队列接口,提供了一些通过下标访问元素的函数List 是有序的队列，List 中的每一个元素都有一个索引；第一个元素的索引值是0，往后的元素的索引值依次+1

ArrayList中部分代码如下

/**
     * 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.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

ArrayList 包含了两个重要的对象：elementData 和size

• elementData 是"Object[]类型的数组"，它保存了添加到ArrayList 中的元素。如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData 的容量默认是10。

ArrayList 对象new 的过程并不会实际的创建10 长度的Object[]用于对象的 存储,如果后续并没有使用到Arraylist对象进行操作的话,这部分的内存就是浪 费的.只有当程序第一次使用ArrayList 添加元素时,才会完成通过grow 函数完 成对对象数组的创建.主要的意义是防止内存的浪费.

• size 则是动态数组的实际大小。

(动态)数组的数据结构特点

• 内存需要连续的空间保证
• 顺序添加操作涉及到动态扩容问题
• 除尾部位置元素的添加,删除操作都涉及到位置移动操作
• 随机查找效率快(下标搜寻)

FailFast 机制

快速失败机制,是java 集合类应对并发访问在对集合进行迭代过程中,内部对象结构发生变化一种防护措施.这种错误检测的机制为这种有可能发生错误, 通过抛java.util.ConcurrentModificationException.

测试代码

public class ThreadAdd extends Thread {

    private List list;

    public ThreadAdd(List list) {
        this.list = list;
    }

    @Override
    public void run() {
        for (int i = 0; i < 100; i++) {
            System.out.println("loop execute :"+i);
            try {
                Thread.sleep(5);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            list.add(i);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class ThreadIterate extends Thread {


    private List list;

    public ThreadIterate(List list){
        this.list=list;
    }

    @Override
    public void run() {
        while(true) {
            for (Iterator iteratorTmp = list.iterator(); iteratorTmp.hasNext(); ) {
                iteratorTmp.next();
                try {
                    Thread.sleep(5);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class FailFastTest {

    private static final List<String> list = new ArrayList<String>();

    public static void main(String[] args) {
        new ThreadAdd(list).start();
        new ThreadIterate(list).start();
    }
}
1
2
3
4
5
6
7
8
9

如何做到FailFast 检测

最终是在这个方法中,判断预期的值和现在的值是否相等来决定是否已经failfast

我们在ArrayList 的Add会改变我们modCount 的值.

ArrayList 中动态数组的实现逻辑梳理

以初始长度10已满为例。

LinkedList

继承结构说明

• Queue

队列接口
boolean offer(E e);
E poll();
E element();
E peek();
1
2
3
4
5

• Deque

双端队列接口
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
1
2
3
4
5
6
7

LinkedList 基本概要

LinkedList 是通过双向链表去实现的,他的数据结构具有双向链表结构的优缺点，既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。它包含一个非常重要的私有的静态内部类：Node。

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

Node 是双向链表节点所对应的数据结构，它包括的属性有：

• 当前节点所包含的值(item);
• 上一个节点(prev);
• 下一个节点(next).

初此之外还有几个重要的属性.

• size : 元素的个数
• first : 第一个元素
• last : 最后一个元素

由于LinkedList 实现了List 的接口,所有必然具备List 的特性.那我们先来看看List 接口中定义的一个方法get(int index)和set(int index,E e);

LinkedList 的下标搜索

我们都知道List 接口，ArrayList 和LinkedList 都是实现了该接口，我们也知道基于不同的数据结构通过下标寻找具体的元素.在ArrayList 和LinkedList 中效率是不一样的，那我们来分析一波LinkedList 如何通过下标寻找元素。

get(int index):

set(int index,E e)：

通过上面的总结,我们发现确实针对下标位的随机访问,数组的优势很明显。

Vector

Vector 的底层与我们的ArrayList 类似.都是以动态数组的方式进行对象的存储，Vector 是线程同步操作安全的

Vector 的并发安全保证

我们去看他的源码发现很多对外的方法都是用Synchronized 关键字进行修饰的，所以通过vector 进行操作性能并不高.所以慢慢被放弃。

List 接口实现类的并发安全保证

要保证List 接口实现的集合对象在同步操作时能够线程安全.我们可以使用下面的方式.

List list = Collections.synchronizedList(new ArrayList());
1

源码分析:

最终都是返回SynchronizedList 对象

Set

继承关系

• Set
  Set 是继承于Collection 的接口。它是一个不允许有重复元素的集合

• SortedSet
  有序的集合,即SortedSet 中的元素是按指定排序规则排序的排序，定义了一个内部的成员作为排序的比较器(Comparator)

• AbstractSet
  是一个抽象类，它继承于AbstractCollection，AbstractCollection 实现了Set 中的绝大部分函数，为Set 的实现类提供了便利

• NavigableSet
  NavigableSet 接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项

TreeSet

TreeSet 的实现在我们认识完TreeMap 之后就简单多了.
TreeSet 底层的实现依赖的TreeMap 集合[参见Map>>深入TreeMap]

PRESENT 对象就是每一个TreeMap 元素的Value , key 就是set 中的元素,Value 为固定的
PRESENT 值

Map

TreeMap

TreeMap 的底层数据结构为红黑树(RB TREE) 结构.

TreeMap 的继承结构：

• AbstractMap
  继承于Map 的抽象类，它实现了Map 中的大部分API。其它Map 的实现类可以通过继承AbstractMap 来减少重复编码

• SortedMap
  有序的键值对集合接口,即SortedMap 中的内容是排序的键值对，定义了一个
  内部的成员作为排序的比较器(Comparator)

• NavigableMap
  是继承于SortedMap 的接口。相比于SortedMap，NavigableMap 有一系列的导航方法；如"获取大于/等于某对象的键值对"、“获取小于/等于某对象的键值对”等等

红黑树

• 红黑树一种特殊的平衡二叉查找树.
• 红黑树在数据的插入和删除上比平衡二叉树(AVL)效率更高
• 红黑树在数据的查询上由于可能存在树的高度比AVL 树高一层的情况,查询性能略差一点.
• 选择红黑树是查询和增删性能的折中选择

红黑树5 大规则:

• 每个节点都用一个标志位来标识或者是黑色，或者是红色。
• 根节点是一定是黑色。
• 每个叶子节点（NIL 节点）是黑色。
• 如果一个节点是红色的，则它的子节点必须是黑色的。
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

TreeMap 的有序

树形结构保证了TreeMap 的有序.
在二叉树的结构中,我们数据遵循的原则是：
递归比对每一个节点和将插入的数据,若数据比节点的内容小,往该节点的左边进行递归.直到找到元素的存放点.所以我们可以通过红黑树或者说二叉树的特性来完成TreeMap 的有序性.

Entry 对象的结构

pet操作

get操作

深入HashMap

HashMap 的底层数据结构

采用数据+链表或者数组+红黑树方式进行元素的存储
存储在hashMap 集合中的元素都将是一个Map.Entry 的内部接口的实现当数组的下标位是链表时,此时存储在该下标位置的内容将是Map.Entry 的一个实现Node 内部类对象当数组的下标位是红黑树时,此时存储在该下标位置的内容将是Map.Entry 的一个实现TreeNode 内部类对象

HashMap 重要的成员属性

HashMap 如何组织数据的存储

• HashMap 元素的存储
  数组的长度定义,必须为2 的N 次幂.默认为16 大小
  我们可以采用key 的hashcode.把他作为我们的计算的因子与数组的长度进行某一种运算得到一个0-15 的int 值
  [最简单的方式下标位置的确立.我们可以采用取模Array.length()的方式. ]
  但是hashMap 中下标位置的获取采用二进制的&运算进行下标位置的确认
  Hash int 类型值的& Array.length - 1 的方式

如果我只按照原来的hashcode 值进行计算的话,那么参与计算的位数太少了.比如长度为16.参与计算的值就可以hashcode 的最后4 位.下标分布的情况可能会出现不均衡…所以hashmap 的设计者希望让更多的位数来参与我们的计算.将hashcode 进行高低十六位的异或运算.