MO_or关于Java集合框架的感悟

一、引言

在工作中Java集合框架是很常见的，但MO_or之前仅仅是记住了部分集合的基本概念，并没有真正去理解集合，导致工作时仍不知道如何选择使用哪种集合
所以为了更加熟练掌握集合框架，本篇文章将从集合基本概念、数据结构、适用场景三个角度来进行分析与理解

PS：阅读本篇文章时，建议先了解八大基本数据结构，才能更好吸收本文内容 ( MO_or关于八大数据结构的感悟 )

二、集合

2.1 集合的基本概念

了解其基本概念前，我们不妨先大致了解一下为什么会出现集合

在集合出现前，java中已经有数组可以存储数据了，数组是高效的，但也存在其缺点
比如说：容量固定、只能存储相同数据类型等

同时，“java是一门面向对象编程的语言”
但程序设计中会有很多不同数据结构的相似使用过程

为了优化数组的缺点，体现面向对象的特性，不重复设计相同的过程
于是集合框架便应运而生了

若我们较为熟悉数组的缺点以及面向对象的特性所带来的优势
便更加容易理解，集合的基本概念与优势

概念：
    能够动态扩容、支持不同数据类型共存并提供丰富API的类
优势：
    1、可动态扩充容量(数组容量初始化后就为固定值)
    2、支持存储不同数据类型(数组只能存储相同数据类型)
    3、更丰富的API
    (将使用频率较高的过程进行封装增强，弥补了面向过程的缺陷)
    4、具有封装、继承、多态的特性
    (这意味着集合具有更加灵活、扩展性更好、更易维护的特性)

2.2 几种常见集合

2.2.1 引言

我们大致了解集合的背景、概念、优势后
接下来我们将对一些常见集合进行较为深入的理解与实践，更深刻的去体察其中的奥妙

先上一张集合框架图：

(图片来源 — 菜鸟教程)

我们将主要对工作场景使用频率较高的ArrayList进行深入探讨
(当然HashSet、HashMap的使用频率也很高)

并简单回顾以下集合：
List：Vector、LinkedList
Set：HashSet、TreeSet、LinkedHashSet
Map：HashMap、TreeMap、Hashtable

2.2.2 ArrayList

适用场景

List下的ArrayList可以说是项目中非常常见的一种集合
比如说：数据库查询返回结果，电商项目中订单的批量导出Excel等等

源码分析

在分析源码前，需要先做个小的知识回顾：

1.时空复杂度(时间复杂度/空间复杂度)
这里主要讲讲ArrayList中涉及到的O(n)，部分源码注释

从上图选中部分可知，ArrayList执行添加是按平摊常量时间执行的，即添加n个元素需要花费O(n)的时间，呈线性关系
可以结合数组添加元素的方式来理解
数组添加一个元素需要先从第一个遍历到最后一个再在末尾加上
添加N个元素，就需要先遍历N次

2.">>"位运算符
">>"表示右移，左操作数按位右移右操作数指定的位数，移出部分就被抛弃了，如下

int a = 10 >> 1;
int b = 10 >> 2;
System.out.println(a);
System.out.println(b);

过程：
10 >> 1
    1010 -> 0101
1010 >> 2
    1010 -> 0010
    
输出：
5
2

好了对以上两个小知识点有了基本了解后，就可以开始对部分源码进行分析了

PS：本文不会对ArrayList的源码全部进行分析，主要对ArrayList的效率、扩容、并发三个方面并结合其数据结构进行分析

ArrayList的效率分析

先说结论，再来研究为什么：查询快、增删慢

结合着ArrayList的成员变量来看看：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 版本号
    private static final long serialVersionUID = 8683452581122892189L;
    // 缺省容量
    private static final int DEFAULT_CAPACITY = 10;
    // 空对象数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 缺省空对象数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 元素数组
    transient Object[] elementData;
    // 实际元素大小，默认为0
    private int size;
    // 最大数组容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

tips：缺省 = 默认

成员变量中有许多值得深究的地方，但出于MO_or的时间限制与能力限制，不会对所有细节刨根问底，
比如说缺省容量为何是10，最大数组容量为何是Integer.MAX_VALUE - 8等等
若读者有时间与兴趣可以自行探究其中原有与奥妙

MO_or在这里会深究一下下：最大数组容量为何是Integer.MAX_VALUE - 8，目的在于分享MO_or的探究方式与方法，希望能起到抛砖引玉的效果

为了使读者能更好明白MO_or在探究细节所秉持的心态，MO_or得先唠叨几句：
1、探究细节是对精益求精的追求，而不是过分注意细枝末节而因小失大
2、在探究细节时，应该时刻保持大局意识，明白这个细节是如何服务与整体的
3、通过细节去思考设计者优秀的思想与设计方式才是最终的目的

回到问题中ArrayList的最大容量为什么是Integer.MAX_VALUE - 8呢？
先从ArrayList的源码中去看看有木有答案：

可以看到注释中已经写得很明白了，一些虚拟机需要留部分空间存储标题
同时注释中也说明超过了最大容量后，会抛出异常

那么为什么这个字节数是8呢？不是更多或更少呢？
这里我仅仅借用StackOverflow中的一个回答(参考中附上了链接)，因为ArrayList的作者就是这样规定的(hahaha...)
到这里疑惑基本就解决了，再深究就有点舍本逐末的味道了

满足了部分好奇心后，回到为什么ArrayList，查询快，增删慢
从上面的成员变量中可以看到，其实ArrayList的底层就是一个数组，那么数组的特性便是查询快，增删慢
如果对数组的数据结构并不太了解，可以看看：

MO_or关于八大数据结构的感悟

上述文章中只是动态的展示了其数据模型，并没有结合硬件原理去深入分析，仅是作为了解入门
到这里理解ArrayList的效率的方式就可以变成：
ArrayList-->底层数据结构-->数组-->数组的特性
所以其记忆重点其实已经转移到数组特性上了，其它的便是其关联关系而已

ArrayList的扩容机制

先说说List是如何扩容的，分为两步：
1、扩容原来的数组
2、将当前元素复制到新数组中

现在结合着源码来看看ArrayList具体是如何扩容的？其扩容大小又是怎样规定的？

下面是ArrayList的两个构造方法

/**
 * 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) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

先看看无参构造器
注释中写得很清晰，通过无参构造器，会生成一个容量为10的ArrayList，这个10即是成员变量中的默认容量

再看看带参构造器
可以构造一个指定容量大小的ArrayList，但初始大小若小于零，则会抛出一个非法参数的异常

接下来看看ArrayList增加一个元素时的流程

/**
 * 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;
}

调用ensureCapacityInternal确保容量，传递size + 1参数，size为当前集合的元素个数(不包含新增的元素，不是当前数组的长度)
然后将新增的元素赋值给elementData[size++]

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

ensureCapacityInternal方法判断elementData若为空数组或无参构造器创建的数组，
通过Math.max取出默认容量(10)与最小容量中的最大值，然后赋值给最小容量
然后调用ensureExplicitCapacity方法

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

这里先暂时不讲modCount++(涉及到Fail-Fast机制，迭代器的注释中有相关说明)
ensureExplicitCapacity方法中判断最小容量是否大于当前数组的长度
若大于则调用grow方法，进行扩容

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

(划重点)注意！注意！注意！
 
grow方法中新的容量为元数组容量加上原数组容量右移一位的大小，
粗略的说即扩容50%
然后判断扩容后的大小若小于最小容量，则取最小容量的值
再判断扩容后的大小若大于最多容量，则将最小容量传到hugeCapacity方法中并调用

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

在hugeCapacity方法中，对最小容量进行判断，若小于零，则抛出异常
通过一个三目运算若最小容量大于最大容量则返回Integer的最大值，反之则返回最大容量
最后调用数组的Arrays.copyOf方法将原数组中的元素复制到新的容量更大的数组中

简单总结如下：
1、调用add方法添加元素，调用ensureCapacityInternal方法确保最小容量有效，
2、调用ensureExplicitCapacity记录modCount，判断是否需要扩容，
3、若需要调用grow方法，将原数组扩容50%，将原数组元素复制到扩容后的新数组中，
4、回到add方法，将需要添加的元素赋值给新数组末尾

ArrayList的并发问题

源码注释中有很明确的说明，由于MO_or精力和能力有限，这里暂且就不做深入探究了

注释中明确指出了ArrayList在多线程环境下存在并发问题，
但同时也指出了可以通过以下方式来创建线程安全的ArrayList

2.2.3 其它集合

LinkedList

1、优点：底层数据结构是链表，增删操作较ArrayList更快

2、缺点：由于查询需要移动指针，所以查询较ArrayList更慢

3、适用场景：需要对数据进行大量增删的场景

Vector

1、优点：底层数据结构是数组，但大部分方法都用synchronized进行修饰，所以多线程安全

2、缺点：性能上较低，一般不推荐使用

3、适用场景：不推荐使用，有更好的解决多线程安全问题的集合，比如上面ArrayList中源码分析中提到得：
List list = Collections.synchronizedList(new ArrayList(...))

HashSet

其底层数据结构为哈希表，可以存储null值，但仅能存一个，元素不能重复，不保证元素顺序
通常需要排序时才会使用TreeSet
注意Set中的无序，不是存储的数据没有进行排序，而是存储数据的方式是无序的
而List是顺序存储的（数组特性，按下标依次存储）
由于笔者几乎没在工作中使用到Set相关的集合，所以这里暂时不多做扩展，感兴趣的读者可以自行拓展

HashMap

1、优点：允许存储空键值对，效率较HashTable更高，增删效率较高

2、缺点：多线程不安全

3、适用场景：需要存储键值对的数据可以选用该集合
笔者在工作中，遇到多数情况是对接三方接口时，需要按指定键值对的格式组装请求参数

HashTable

1、优点：多线程安全

2、缺点：不允许存储空键值对，效率较HashMap更低

3、适用场景：要求多线程安全的情况下

三、参考

MO_or关于八大数据结构的感悟

java集合类—百度百科

Java集合框架——菜鸟教程

集合和数组的区别

时空复杂度

Java运算符——菜鸟教程

Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8?——StackOverflow

ArrayList扩容原理

浅谈ArrayList动态扩容

四、最后

若有不足，敬请指正
求知若渴，虚心若愚