设为首页 加入收藏

TOP

Java中常见数据结构List之ArrayList
2017-10-12 18:17:16 】 浏览:9915
Tags:Java 常见 数据结构 List ArrayList

这里主要包含ArrayList和LinkedList.
关于Java中的集合内容, 感觉都已经被写烂了, 我这里主要是做个复习, 再从扒下源代码, 尽量用最直白的语言把里面的核心内容记录下来。仅此而已。

首先放一个Collection下的UML图:(此图是idea通过diagram功能生成的, 基于JDK7)

一、ArrayList
1, for-each原理:
0、 在编译的时候编译器会自动将对for这个关键字的使用转化为对目标的迭代器的使用,这就是foreach循环的原理
1、ArrayList之所以能使用foreach循环遍历,是因为ArrayList所有的List都是Collection的子接口,而Collection是Iterable的子接口,ArrayList的父类AbstractList正确地实现了Iterable接口的iterator方法。之前我自己写的ArrayList用foreach循环直接报空指针异常是因为我自己写的ArrayList并没有实现Iterable接口
2、任何一个集合,无论是JDK提供的还是自己写的,只要想使用foreach循环遍历,就必须正确地实现Iterable接口。

2, 集合中的 fail-fast iterator:
Iterator 是工作在一个独立的线程中,并且拥有一个 mutex 锁。 Iterator 被创建之后会建立一个指向原来对象的单链索引表,当原来的对象数量发生变化时,这个索引表的内容不会同步改变,所以当索引指针往后移动的时候就找不到要迭代的对象,所以按照 fail-fast 原则 Iterator 会马上抛出 java.util.ConcurrentModificationException 异常。

当使用foreach遍历一个list元素时, 因为foreach底层实现是使用iteator中的hasNext, next等, 源码中next执行时会checkForComdification:

3, ArrayList初始值大小是10, 每次扩容是增加2倍。优缺点是:

//默认的构造函数, 当然还有构造函数是可以指定大小的
public ArrayList() {
    this(10);
}

//jdk7中的扩容代码, 我看了jdk6中是扩容1.5倍的, 这里有点差别
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);
}

ArrayList的优点:
1、ArrayList底层以数组实现,是一种随机访问模式,再加上它实现了RandomAccess接口,因此查找也就是get的时候非常快
2、ArrayList在顺序添加一个元素的时候非常方便,只是往数组里面添加了一个元素而已
ArrayList的缺点:
1、删除元素的时候,涉及到一次元素复制,如果要复制的元素很多,那么就会比较耗费性能
2、插入元素的时候,涉及到一次元素复制,如果要复制的元素很多,那么就会比较耗费性能
因此,ArrayList比较适合顺序添加、随机访问的场景。

4,细节: 为什么ArrayList的elementData是用transient修饰的?
ArrayList实现了Serializable接口,这意味着ArrayList是可以被序列化的,用transient修饰elementData意味着我不希望elementData数组被序列化。这是为什么?因为序列化ArrayList的时候,ArrayList里面的elementData未必是满的,比方说elementData有10的大小,但是我只用了其中的3个,那么是否有必要序列化整个elementData呢?显然没有这个必要,因此ArrayList中重写了writeObject方法:

private transient Object[] elementData;
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 array length
    s.writeInt(elementData.length);

    // 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();
    }

}

每次序列化的时候调用这个方法,先调用defaultWriteObject()方法序列化ArrayList中的非transient元素,elementData不去序列化它,然后遍历elementData,只序列化那些有的元素,这样:
1、加快了序列化的速度
2、减小了序列化之后的文件大小

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇数据库优化以及SQL优化小结 下一篇shiro:Wildcard string cannot be..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目