`
wdmcygah
  • 浏览: 62441 次
社区版块
存档分类
最新评论

JDK源码剖析与最佳实践—ArrayList

    博客分类:
  • J2SE
阅读更多

知其然,需知其所以然。——古语

知其所以然,需引而伸之,触类而长之;——虫草

最近准备研究下JDK源码,把常用的一些类作个剖析整理,出个系列文章。ArrayList应该是在开发过程中非常高频使用的一个集合类,就先拿这个类开刀了。

笔者使用的JDK版本为:1.8.0_102,由于源码太多,有些也比较简单,所以挑一些重点说明下。

一、整体介绍

ArrayList类如其名,是一个可以动态扩容的数组列表,是List家族中的一员,支持随机访问,而且在JDK8中新支持了Stream API,使用起来还是非常方便的。不过该类不是线程安全的,所以在多线程情况下需要小心使用。

二、源码剖析与实践

2.1 成员变量

transient Object[] elementData;
private int size;
其中elementData即为ArrayList实现依赖的数组,size为ArrayList实际包含的元素的个数。这里elementData有transient,为什么要加这个呢?看后面的2.5小节。

2.2 构造函数

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

这个构造函数可以直接基于collection实现构造成ArrayList,具体过程是先将参数转化成对应数组,再调用Arrays.copyOf方法进行元素的复制,而Arrays.copyOf方法实际是基于System.arraycopy这个本地方法执行的操作。这两个方法在ArrayList被大量用到,主要就是用作数组间的元素拷贝。

最佳实践:在Collection家族的集合类需要转化成ArrayList时,不需要遍历设值,可以直接使用构造方法,这样代码清晰简单,而且性能也好些。

2.3 扩容方法

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

扩容方法主要看ensureCapacityInternal这个私有方法,该方法在列表添加元素时会被调用,以保证数组容量足够。其它扩容相关私有方法都是该方法去调用的。其中比较关键的是grow方法,参数minCapacity为即将达到的元素个数,newCapacity为旧数组容量的1.5倍,哪个值大以哪个容量为准。不过这里还需要注意的是ArrayList的最大长度也是有限制的,最大也只有Integer.MAX_VALUE,而且再设置成最大之前,还会先设置容量为MAX_ARRAY_SIZE 。

为什么先设置成MAX_ARRAY_SIZE呢?这里源码给出的注释是MAX_ARRAY_SIZE是最大分配的数组大小,因为有些虚拟机还存储一些头信息在数组里,数组容量分配过大可能会有OutOfMemoryError。所以其实更安全的最大数组长度是MAX_ARRAY_SIZE。当然实际情况长度很少可能这么长。

另外这里扩容的时候为什么是原来的1.5倍呢?原因是如果扩容倍数太大,比如2.5倍,那么占用的内存会太大,浪费的内存也会相应多;而扩容太小,比如1.1倍,那么后期元素增加时又需要对数组重新分配内存,消耗性能。所以1.5倍是个经过测试的折衷值。【另可参见《编写高质量代码》建议63】

最佳实践:由于ArrayList动态扩容的特性,而且大多数情况下是扩容1.5倍,所以在已知列表容量时,最好先为列表指定初始化容量,这样可以避免内存空间的浪费,以及扩容过程数组复制的性能开销。

2.4 差集与交集

public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

这里removeAll方法是将在参数集合中存在的元素中从list中删除,相当于ArrayList与集合参数c的差集;而retainAll方法是将参数集合中不存在的元素中从list中删除,相当于ArrayList与集合参数c的交集。

这里两个方法都调用的是batchRemove方法,只是complement值传的不同,去判断到底是留包含的还是不包含的。这里有逻辑很多逻辑是写在finally的,是为了保证contains判断报错时也正常执行。另外中间有个elementData[i] = null操作,把所有用不到的元素置为null,这样也便于垃圾回收。

最佳实践:(1)集合之间取并集用addAll,取差集用removeAll,取交集用retainAll;(2) 如果数组元素用不到可以置为空,另外在代码里面如果用到一些的List对象,如果不用了,最好调用clear方法,特别是大List或循环创建的。

2.5 序列化与反序列化

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();
        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);
        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        // Read in size, and any hidden stuff
        s.defaultReadObject();
        // Read in capacity
        s.readInt(); // ignored
        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);
            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }

} 

前面介绍成员变量的时候elementData是有transient标识的,即elementData是不会被序列化的。那ArrayList里面的数据到底会不会序列化呢?上面的代码可以看到ArrayList重写了writeObject与readObject方法,即覆盖了默认的序列化实现。序列化与反序列化的时候都是只序列化了List的数组中实际存在的元素,所以ArrayList加transient标识的目的只是为了避免默认序列化机制把整个数组都序列化了,然后自实现了序列化与反序列化方法,将真实存在的数据进行了序列化操作。

2.6 子列表

public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }
private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;
        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }
       private void checkForComodification() {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }
}

ArrayList提供了subList这个方法得到一个指定下标范围内的子列表视图,这里下标范围检查就不看了,所有的List下标相关操作都需要做个是否越界的检查。关键看下SubList 这个内部类,这里限于篇幅代码没有贴全,重点看下这个内部类的成员变量就可以了,特别注意下parent这个是父列表,而实际上所有子列表操作中其实都是操作的父列表。

另外看下SubList 这个内部类的checkForComodification方法,子列表几乎所有操作都会先调用checkForComodification方法,这个方法主要是检查modCount这个值是否相等,就是为了避免父列表修改的。因为父列表有修改时modCount值会增加,而造成不相等,会抛出异常,所以如果得到了子列表,父列表元素不能有变更操作(增删操作)。

最佳实践:(1)子列表的所有操作都会改变原列表,所以有些场景下想修改列表的某部分数据,可以直接得出子列表进行修改,就会修改原列表了;(2)得到子列表后,不要再直接修改原列表了,否则会抛异常。

2.7 Stream API


public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
其中forEach方法参数为函数式方法,这里会遍历每个数组执行对应的操作。spliterator方法返回Spliterator对象,实际是一个可以并行遍历的迭代器,ArrayList从Collection中继承的stream方法就会用到这个方法去构造。removeIf方法参数也会函数式方法,Predicate是个判断条件的函数接口,条件满足时就会将元素删除。replaceAll方法的参数也是UnaryOperator函数接口,这个接口可以执行操作,然后将对应的元素做替换。

这里Stream API与Lamda表达式一般都关联使用,目前对于这块原理还不是特别清楚,所以就不展开讲。后期理清楚了再补充。这里附几个看到的比较好的相关资料,有助于了解:
官方Lamda表达式教程
Stream语法详解
为什么需要 Stream

 

分享到:
评论

相关推荐

    关于jdk动态代理的源码剖析

    ### 关于JDK动态代理的源码剖析 #### 一、引言 在Java开发过程中,动态代理技术是一项非常实用的技术,它可以帮助我们实现在不修改原有代码的基础上为方法增加额外的功能,比如日志记录、权限校验等。本文将深入...

    Java并发jdk源码剖析-jmc7:https://openjdk.java.net/projects/jmc/

    Java同时jdk源码剖析任务控制 Mission Control 是一个开源的 Java 生产时间分析和诊断工具。 目前可以在受支持平台上的 Oracle JDK 和 Eclipse 市场中找到 Mission Control 的构建版本。 有关任务控制的更多信息,请...

    JDK源码剖析之红黑树TreeMap.pptx

    JDK源码剖析之红黑树TreeMap,偶然看见,传上来分享一下

    jdk源码 jdk源码

    Java Development Kit (JDK) 源码是学习和理解Java平台核心机制的关键资源。它包含了许多关键组件的源代码,使开发者能够深入探索Java语言的底层实现,从而提升编程技巧,优化性能,并理解标准库的工作原理。在这个...

    jdk源码阅读一:ArrayList

    ### jdk源码阅读一:ArrayList #### 一、ArrayList简介与特性 ArrayList作为Java集合框架中的重要组成部分,被广泛应用于各种应用场景。它的主要特点包括: - **基于数组实现**:ArrayList采用数组作为其底层数据...

    jdk源码(完整版)

    - **调试与问题解决**: 对源码的了解能帮助开发者更快定位并解决问题,尤其是在遇到JDK相关问题时。 - **贡献社区**: 掌握源码后,开发者可以参与OpenJDK项目,为Java的发展做出贡献。 总之,JDK源码的完整版为...

    关于 ArrayList get(0)的异常JDK源码跟进

    这篇博客主要探讨了当尝试通过`get(0)`获取ArrayList的第一个元素时可能出现的问题,并通过JDK源码分析了其原因。 首先,我们需要了解ArrayList的内部结构。ArrayList实际上是一个基于数组实现的列表,它维护了一个...

    jdk1.8中文版源码+文档

    **Java JDK 1.8 源码与中文文档详解** Java Development Kit(JDK)是Java编程语言的核心工具集,用于开发、编译、调试和运行Java应用程序。JDK 1.8版本是一个重要的里程碑,引入了许多新特性和优化,极大地提升了...

    自己重新编译的jdk源码jar包

    对于想了解JDK源码的朋友来说,通过调试JDK源码来学习是一个常用的方法。但是默认的情况下eclipse是不支持进入jdk源码中进行调试和显示当前变量的。 我们要明白在jdk中,sun对rt.jar中的类编译时,去除了调试信息,这样...

    JDK8的ArrayList源码文件

    JDK8的ArrayList源码文件

    JDK源码阅读笔记

    JDK源码阅读笔记

    java JDK 源码

    Java JDK源码是Java开发工具包的...同时,源码也是学习Java规范和最佳实践的重要资源,帮助开发者遵循Sun/Oracle制定的标准,提高代码质量。总之,深入研究Java JDK源码对于任何Java开发者来说都是一项宝贵的学习经历。

    JDK源码阅读笔记LearningJDK

    JDK源码阅读笔记

    ArrayList源码Jdk1.8

    ### ArrayList源码解析(JDK 1.8) #### 概述 `ArrayList`是Java集合框架中的一个核心组件,它提供了动态数组的功能。与固定大小的数组不同,`ArrayList`可以随着元素的增加而自动扩展其容量。在JDK 1.8中,`...

    JDK源码,整合所有内容

    - JDK1.8中对集合框架进行了重大更新,`ArrayList`、`LinkedList`、`HashSet`、`HashMap`等都有对应的源码,可以深入理解它们的工作原理和性能差异。 - **Stream API**:新引入的流API提供了函数式编程的支持,...

    源码解析jdk7.0集合:ArrayList的底层实现原理.pdf

    在探讨 JDK 7.0 中 ArrayList 的底层实现原理之前,首先需要了解 ArrayList 作为 Java 集合框架中 List 接口的动态数组实现类的基本概念。ArrayList 提供了一种存储有序、可重复、允许为 null 的数据结构,并且该...

    jdk-8u60源码

    《深入解析JDK 8u60源码》 JDK(Java Development Kit)是Java编程语言的核心组件,包含了编译器、运行时环境、工具集等,是开发者理解和使用Java技术的重要基石。JDK 8u60是Oracle公司发布的一个版本,包含了对...

    jdk源码jdk1.8.0_181

    4. **学习最佳实践**:Oracle的代码风格和编程习惯,往往代表了业界的最佳实践。 总结,JDK1.8.0_181的源码是一本活生生的教科书,它不仅展示了Java语言的强大功能,也揭示了其背后的运行机制。对于任何Java开发者...

    JDK源码选读

    《JDK源码选读》是一本专注于Java开发人员深入...通过《JDK源码选读》,开发者不仅能深化对Java语言的理解,还能学习到软件设计模式和最佳实践,从而写出更高效、更健壮的代码。这是一次提升个人编程技能的宝贵旅程。

    jdk1.8 源码中文版,jdk直接显示中文注释

    下载后直接去本机jdk目录里替换jdk中的src.zip 再打开idea就能看到中文版的源码注释 示例 https://blog.csdn.net/a7459/article/details/106495622

Global site tag (gtag.js) - Google Analytics