转载

MO_or关于Java集合框架的感悟

一、引言

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

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

二、集合

2.1 集合的基本概念

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

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

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

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

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

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

2.2 几种常见集合

2.2.1 引言

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

先上一张集合框架图:

MO_or关于Java集合框架的感悟

(图片来源 — 菜鸟教程)

我们将主要对工作场景使用频率较高的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),部分源码注释

MO_or关于Java集合框架的感悟

从上图选中部分可知,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的源码中去看看有木有答案:

MO_or关于Java集合框架的感悟

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

那么为什么这个字节数是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精力和能力有限,这里暂且就不做深入探究了

MO_or关于Java集合框架的感悟

MO_or关于Java集合框架的感悟

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

MO_or关于Java集合框架的感悟

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动态扩容

四、最后

若有不足,敬请指正
求知若渴,虚心若愚
原文  https://segmentfault.com/a/1190000022579892
正文到此结束
Loading...