文档章节

0003--jcf(jdk1.7)-ArrayList源码

c
 cengy
发布于 2016/03/18 10:25
字数 2399
阅读 43
收藏 0

1.    ArrayList的定义

    其内部是基于数组实现的,是一个动态的数组(可以自动扩容),自动扩容会带来数组元素的复制。(怎么自动扩容的?)

    它不是线程安全的。

它的类声明如下:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

    实现了Serializable接口,表明它可以在序列化传输。实现了Cloneable,表明可以被复制。实现了RandomAccess接口,表明可以被快速随机访问。(为什么会有RandomAccess接口?它是一个标识性接口)从RandomAccess接口的API说明中,我们得知,当实现这个标识接口时,采用下标遍历list会有更好的性能。

    举个例子:

List<Integer> aList = new ArrayList<Integer>(10000000);
Random random = new Random();
for (int i = 0; i < 10000000; i++) {
    aList.add(random.nextInt(100));
}

long start = System.currentTimeMillis();

long sum = 0;
// 下标遍历方式
for (int i = 0; i < aList.size(); i++) {
    sum += aList.get(i);
}
long end = System.currentTimeMillis();
System.out.println("下标遍历方式(ms): " + (end - start));

long start2 = System.currentTimeMillis();
// 迭代器遍历方式
for (Integer i : aList) {
    sum += i;
}
long end2 = System.currentTimeMillis();
System.out.println("迭代器遍历方式(ms): " + (end2 - start2));

--控制台输出结果
下标遍历方式(ms): 46
迭代器遍历方式(ms): 68


2.    ArrayList结构的实现

a.    ArrayList属性以及构造方法

    实现了List接口,内部是采用数组存储方式实现的。因此可以说是对数组进行的操作。

内部有个Object[] elementData用来存储ArrayList里面的元素。

它有两个属性:

注意:这个size属性是用来保存已经存储元素的个数,不是elementData的长度。

有三个构造方法

带参数int的构造函数,以指定ArrayList的初始容量。不带参数的构造函数则默认初始容量为10。带Collection<? extend E>类型的参数以构造一个含Collection列表的元素列表.

public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}
public ArrayList() {
    this(10);
}
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

b.    数据操作

    ArrayList是一种数据结构,因此它应该提供一些对数据常见的一些增删改查的常用操作。

1).    数据的查询

indexOf(Object): int
lastIndexOf(Object): int
get(int): E

其方法内容比较简单,注意indexOf(Object)与lastIndexOf(Object)方法区分null与非null查找。写到了两个条件中循环,这样比在每个循环中做if判定,性能有提升。

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;    //未找到返回-1
}
//    反向遍历列表
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}
E elementData(int index) {
    return (E) elementData[index];
}

2).    数据的增加

add(E): boolean    --将元素添加到列表的末尾
add(int, E): void
addAll(Collection<? extends E>): boolean
addAll(int, Collection<? extends E): boolean

首先看add(E)方法

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
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);
}

add(E)对列表进行了结构性修改,所以modCount需要改变。(modCount是提供fail-fast行为机制的,它是定义在AbstractList中的)。首先进行list列表大小确定,是否需要扩容以容纳新元素。具体的扩容方法是group(int)方法。它会将list列表内部的Object[]数组长度扩展为现在的1.5倍。然后将所有元素复制到新数组中,这样就完成了扩容操作。

add(int,E)方法源码如下:

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

它将从index开始的元素往后移动,然后设置index处的元素为element.

addAll(Collection<? extends E>)

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

// 将c中的所有元素添加到list列表末尾

addAll(int, Collection<? extends E)

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

// 比addAll(Collection<? extends E> c)稍微复杂一点
// 判定index范围,然后检测是否需要扩容,在确定是否移动从index处开始的元素,然后将元素插入到指定位置处。

3).    数据的修改

set(int, E): E
//源码
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
//返回修改前的元素

4).    数据的删除

remove(int): E    --基于下标删除元素
remove(Object): E --根据元素删除
clear(): void

remove(int)源码:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

进行范围检查,保存被 删除元素,将元素往前移动,将list末尾元素置空。

remove(Object)源码:

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // Let gc do its work
}

根据元素是否是null,分开循环 查找删除。然后找到了就通过fastRemove私有函数删除元素(不调用remove(index),因为不需要进行index范围判断)。注意它返回的是boolean值。

clear()方法:

public void clear() {
    modCount++;

    // Let gc do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}
// 注意这个方法将所有元素置为null

c.    其它方法

1).    trimToSize()

public void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (size < oldCapacity) {
        elementData = Arrays.copyOf(elementData, size);
    }
}
// 这个方法是将List的当前容量调整为实际存储元素的大小

2).    subList(index fromIndex, int toIndex)

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

当fromIndex==toIndex的时候,subList返回的空列表。sublist相当于list的一个视图,对它的修改实际上是操作的list。

3).    toArray()

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
--数组的长度就是列表中包含元素的个数

        toArray(T[] a)

public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}
// 当数组长度大于列表元素个数,会将size处设置为null


--关于Arrays.asList(T... a)

数组转列表的桥梁方法,但是这个方法返回的List列表有如下特点:

1). 返回的List实现类是Arrays的一个内部类,不是java.util.ArrayList类

2). 它也继承了java.util.AbstractList类,但是没有实现如下几个方法,所以调用这些方法会抛出异常。(注意add(E e)方法,因为AbstractList它是调用add(index,e)所以也会抛出异常)

add(int index, E e);
remove(int index);

asList(T... a)参数是一个可变长度参数列表,这是JDK1.5中新增的泛型写法。在之前它是asList(Object[] a)定义形式。

其实编译器最终会将可变长度参数列表转化为数组形式。因此我们可以像使用数组一样遍历可变长度参数列表。

public class App {
	
	static public void main(String... args) {
		System.out.println("app...");
		test(1,2);
	}
	
	static void test(int... a) {
		for(int i=0; i<a.length;i++){
			System.out.println(a[i]);
		}
	}
}

// 通过javap -s查看方法签名,发现int... a类型是一个[I,表面它是一个int[]数组
Compiled from "App.java"
public class App {
  public App();
    Signature: ()V

  public static void main(java.lang.String...);
    Signature: ([Ljava/lang/String;)V

  static void test(int...);
    Signature: ([I)V
}

--public class App {
	
	static public void main(String... args) {
		System.out.println("app...");
		test(1,2);
	}
	
	static <T> void test(T... a) {
		for(int i=0; i<a.length;i++){
			System.out.println(a[i]);
		}
	}	
}
Compiled from "App.java"
public class App {
  public App();
    Signature: ()V

  public static void main(java.lang.String...);
    Signature: ([Ljava/lang/String;)V

  static <T extends java/lang/Object> void test(T...);
    Signature: ([Ljava/lang/Object;)V
}
// 对于泛型,会转化成Object[]数组。

看一段代码:

int[] a = {1, 2, 3, 4};
Integer[] b = {1, 2, 3, 4};
List aList = Arrays.asList(a);
List bList = Arrays.asList(b);
LogUtils.LOG.info("aList.size:{0}", aList.size());
LogUtils.LOG.info("bList.size:{0}", bList.size());
-- 输出结果
[INFO ] App.java 39 [main] - aList.size:1
[INFO ] App.java 40 [main] - bList.size:4

你会发现输出结果一个是1,一个是4。因为int[]这个整体才能算一个Object对象,没有int这个对象。int[] a会当作new Object[]{a},元素个数肯定是1了。

而对于Integer[] b类型,它会被当作new Object[]{1,2,3,4}。因为你按照JDK1.5之前的语法,它就是传入了一个对象数组,这个对象数组里面的元素是4个。


ArrayList(Arrays中的)类源码如下,它实现了RandomAccess接口。

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable
{
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] array) {
        if (array==null)
            throw new NullPointerException();
        a = array;
    }

    public int size() {
        return a.length;
    }

    public Object[] toArray() {
        return a.clone();
    }

    public <T> T[] toArray(T[] a) {
        int size = size();
        if (a.length < size)
            return Arrays.copyOf(this.a, size,
                                 (Class<? extends T[]>) a.getClass());
        System.arraycopy(this.a, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    public E get(int index) {
        return a[index];
    }

    public E set(int index, E element) {
        E oldValue = a[index];
        a[index] = element;
        return oldValue;
    }

    public int indexOf(Object o) {
        if (o==null) {
            for (int i=0; i<a.length; i++)
                if (a[i]==null)
                    return i;
        } else {
            for (int i=0; i<a.length; i++)
                if (o.equals(a[i]))
                    return i;
        }
        return -1;
    }

    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
}



    








© 著作权归作者所有

上一篇: 0004--java nio
c
粉丝 1
博文 22
码字总数 16864
作品 0
成都
私信 提问
JCF框架源码分析系列-ArrayList(二)

1、揭开ArrayList真面目 作者将在本文详细赘述日常开发中最常用集合类-ArrayList,本次JCF源码分析基于JDK1.7,主要从以下几个方向分析: UML类图关系 数据结构 接口介绍 常用、重要方法的实...

Ambitor
2015/11/30
361
0
Java集合之ArrayList源码解析

ArrayList是我们在开发中经常使用的一个集合,继续按照以前的风格来解析源码(JDK1.7)。 ArrayList简要概括: 1.ArrayList的底层数据结构是一个数组,确切地说是一个动态数组,每次扩容的时...

GeneralAndroid
2017/11/30
0
0
Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理

Java2的集合框架,抽其核心,主要有三种:List、Set和Map。如下图所示: 需要注意的是,这里的 Collection、List、Set和Map都是接口(Interface),不是具体的类实现。 List lst = new Array...

止静
2014/09/19
0
1
【javac添加python 列表特性5】修改openJDK的Javac,使得支持List k...

先把附件和测试文件发上来:Javac.rar (我使用的是JDK1.7) 经过前一阶段的学习,对javac前端Parser阶段已经有了足够的理解,要使javac支持类似python的列表语法: List k=[1,'a',[2,3],"abc...

guoliang
2012/11/19
0
0
Comment Remover 0003 发布

Comment Remover 0003 修复了删除包含在字符串内部注释的 bug。 Comment Remover 用来删除各种源码文件中的注释,支持的语言包括:汇编, Pascal, Java, C, C++, D, and Python....

oschina
2013/01/06
621
3

没有更多内容

加载失败,请刷新页面

加载更多

从濒临解散到浴火重生,OceanBase 这十年经历了什么?

阿里妹导读:谈及国产自研数据库,就不得不提 OceanBase。与很多人想象不同的是,OceanBase 并非衔着金钥匙出生的宠儿。相反,它曾无人看好、困难重重,整个团队甚至数度濒临解散。 从危在旦...

阿里云云栖社区
24分钟前
2
0
比特币第三方API大全

在开发比特币应用时,除了使用自己搭建的节点,也可以利用第三方提供的比特币api,来获取市场行情、进行交易支付、查询账户余额等。这些第三方api不一定遵循标准的比特币rpc接口规范,但往往...

汇智网教程
35分钟前
1
0
Dozer:Dozer异常java.lang.ClassCastException

这个问题是个很难发现的问题,因为代码本身没有错误,但就是无法找到报错原因 现记录下这个报错 java.lang.ClassCastException:com.XXX.ObjectA cannot be cast to com.XXX.ObjectA 代码中并...

琴兽
今天
2
0
Feign Retryer的默认重试策略测试

1、Feign配置 @Configurationpublic class FeignConfig { @Value("${coupon_service.url:http://localhost:8081}") private String couponServiceUrl; @Bean publ......

moon888
今天
2
0
关于不同域名下的session共享问题

如果登录,首页,分类,列表,产品都在不同的二级域名下,主域名不变,一定要保证里面的版本问题,不能为了更新而更新,这样哪个下面的session都访问不了。

dragon_tech
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部