跳至主要内容

动手实现:用Java实现一个简单的ArrayList

动手实现:用Java实现一个简单的ArrayList

概述

ArrayList是一个可以自动扩容的List接口实现，由命名可以看出是由数组实现。本文尝试编写一个简单的ArrayList实现，通过对比来理解JDK中的ArrayList是如何实现的。本次主要实现ArrayList的常用方法，完成简单的CRUD和迭代器。

动手实现

成员变量和构造方法

首先看一下类声明，为了更方便实现列表的相关方法，以及面向接口编程，这里声明实现List接口，类命名为SimpleArrayList

public class SimpleArrayList<E> implements List<E> {}

然后再看一下成员变量，这里设计两个成员变量，第一个变量是实际存储数据的数组，第二个变量是数据的大小

private Object[] data;

private int size;

然后在构造方法中初始化数组

public SimpleArrayList() {
  data = new Object[10];
}

CRUD的实现

首先看一下add方法实现

@Override
public boolean add(E e) {
    //判断数组还有没有空间存放新的元素
    if( (size + 1) > data.length){
        Object[] newData = new Object[data.length + 10];
        System.arraycopy(data, 0, newData, 0, data.length);
        data = newData;
    }
    data[size++] = e;
    return true;
}

方法先判断数组中还有没有足够空间存放新元素。如果没有足够空间，就创建一个新数组，长度在原来的基础上增加10，再把原来数组的内容拷贝到新数组里，最后把新数组赋值给实际存储数据的成员变量data，这样就完成了扩容。最后再把add的元素放在最后一位，这样add方法就完成了。

然后再看一下get方法的实现

@SuppressWarnings("unchecked")
@Override
public E get(int index) {
    if(index < 0 || index >= size){
        throw new IndexOutOfBoundsException("索引越界");
    }
    return (E) data[index];
}

get方法的实现比较简单，首先检查一下传入索引的合法性，然后再返回数组中对应索引的元素。

下面是set方法实现

@SuppressWarnings("unchecked")
@Override
public E set(int index, E element) {
    if(index < 0 || index >= size){
     throw new IndexOutOfBoundsException("索引越界");
    }
    E e = (E) data[index];
    data[index] = element;
    return e;
}

set方法首先检查一下传入索引的合法性。通过查看List接口的set方法上的return注释，知道set方法返回的是旧元素，所以这里需要先声明旧元素的变量，再把新元素赋值，最后返回旧元素。

下面是remove方法，传入Object的版本

@Override
public boolean remove(Object o) {
    for (int i = 0; i < size; i++) {
        if ( o==null ? get(i)==null : o.equals(get(i)) ){
            if( i != (size-1))
             System.arraycopy(data, i + 1, data, i, size - (i + 1) );
            data[size--] = null;
            return true;
        }
    }
    return false;
}

方法传入的是一个object参数，所以要遍历所有元素，然后找到第一个对应的元素，再把后面的元素往前移动，覆盖被删除的元素。当被删除的元素是数组中最后一个时，就不再需要移动数组，所以在移动之前加一个判断。

迭代器

迭代器的实现类如下

private class SimapleIterator implements Iterator<E>{
  private int currentIndex = 0;

  @Override
  public boolean hasNext() {
   return currentIndex < size;
  }

  @SuppressWarnings("unchecked")
  @Override
  public E next() {
   return (E) data[currentIndex++];
  }
}

这是一个比较简单又能完成任务的实现。初始索引currentIndex是0，调用hasNext方法时，如果currentIndex小于size，表示还有下一个元素，如果currentIndex等于size，就表示已经没有下一个元素了。next方法在取出currentIndex下的元素之后，再自增移动currentIndex。

测试

目前主要的CRUD方法和迭代器都已经实现，现在可以测试一下这些方法能不能正常使用。测试方法如下

@Test
public void testSimpleArrayList(){
    for (int i = 0; i < 100; i++) {
        list.add(i);
    }

    list.add(null);

    System.out.println("size=" + list.size());

    System.out.println(list.remove(Integer.valueOf(0)));
    System.out.println(list.remove(null));
    System.out.println(list.remove(Integer.valueOf(100)));

    System.out.println("size=" + list.size());

    int count = 0;
    for (int i = 0; i < list.size(); i++) {
        count += list.get(i);
    }
    System.out.println("count = " + count);

    int count2 = 0;
    for (Integer i : list) {
        count2 += i;
    }
    System.out.println("count2 = " + count2);

    System.out.println("get(0)=" + list.get(0));
    list.set(0, 1000);
    System.out.println("get(0)=" + list.get(0));

}

输出

size=101
true
true
false
size=99
count = 4950
count2 = 4950
get(0)=1
get(0)=1000

可以看到输出正常，表示这个简单的实现的基本功能都已经完成了。下面再来看看JDK中是如何实现的。

jdk8的ArrayList实现

现在来看看jdk8的是如何实现ArrayList的，下面源码基于jdk1.8.0_121。

成员变量和构造方法

先来看一下主要的成员变量

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;

    private int size;

这里主要看一下elementData变量，这个变量是实际存储数据的数组，但是又声明为transient ，这表示ArrayList没法序列化吗？其实并不是，因为ArrayList实现了自己的readObject和writeObject方法来用于序列化。

下面再来看一下构造方法

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

public ArrayList(int initialCapacity)：这个构造方法主要用于初始化数组的大小，当创建时就能知道有多少元素时，用这个构造方法能让时间和空间都达到最好的效果。比如，如果在创建时就知道会有1000个元素，用这个构造方法能避免在调用add方法时频繁地复制数组。

public ArrayList()：这是默认构造方法，初始化时会构造一个默认的空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，被所有ArrayList共用。

public ArrayList(Collection<? extends E> c)：这个构造方法接收一个集合作为基础元素返回一个新的ArrayList。

CRUD实现

首先看一下add方法，主要看一下ArrayList是如何扩容的，扩容的主要方法是private void grow(int minCapacity)

public boolean add(E e) {
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//数组修改标记

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //计算扩容长度
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果新计算出的数组长度，小于需求的数组长度，就丢弃计算出的结果，把需求的数组长度赋值给newCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //考虑新计算出的数组长度过大的情况
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    //这里主要考虑int值溢出的情况，当需求的数组长度超过int的最大值时，就会发生溢出，此时主动抛出异常
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

在add方法实现的流程上SimpleArrayList与ArrayList差别不是很大，都是先判断数组大小，再把新元素赋值，不过ArrayList考虑得更多：

  • 第一个是多考虑了数组结构修改的情况，modCount++在这里表示数组结构发生了变化。对于在使用迭代器之类的情况时，如果数组结构发生变化，会导致结果不正确，所以通过这个值来监控数组结构的变化，并在发生变化的时候抛出ConcurrentModificationException。

  • 第二个是更仔细地考虑了扩容的长度，包括数组长度过长，就主动抛出异常等，详细可以查看上面的private void grow(int minCapacity)和private static int hugeCapacity(int minCapacity)方法上的注释。

ArrayList扩容长度的计算方法是int newCapacity = oldCapacity + (oldCapacity >> 1);，表示新的长度是在旧的长度基础之上，增加旧长度的50%（oldCapacity >> 1在oldCapacity为正整数的情况下，等于oldCapacity / 2）。

那么为什么JDK设计扩容长度是在原基础上增加50%呢？其实这是基于普遍性能上的考虑，在原基础上增加50%的长度，在一定程度上能保证add方法执行为常数时间（在扩容期间会有一定的性能损失）。

在早期的Java版本中，扩容长度的计算方式是int newCapacity = (oldCapacity * 3)/2 + 1;

现在再来看一下get方法的实现

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

    return elementData(index);
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

在get方法实现的流程上，SimpleArrayList与ArrayList类似，先检查边界，再从数组中取出元素。

现在到set方法的实现

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

set方法相对也比较简单，SimpleArrayList实现类似。

再来看看remove方法

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; // clear to let GC do its work
}

在remove方法上，ArrayList先判断了null，然后再进行循环判断，最后再进行移动覆盖删除。同时也考虑到了数组结构修改的情况，修改modCount变量来标记。

ArrayList中迭代器的hasNext和next使用modCount来判断数组结构是否发生修改，SimpleArrayList只是简单的实现数据的获取。

总结

本文通过对比来加深对ArrayList常用方法的理解。

最后基于本文，总结了以下几个点：

  • ArrayList内部使用Object数组来存储元素
  • 当数组需要扩容时，每次增加原来长度的50%
  • 当元素被删除时，删除元素后面的数组会往前移动（当被删除的元素在最后一个时除外），所以在很多情况下，想通过每次删除单个元素来提高遍历ArrayList的性能是不靠谱的（见过一些人尝试这样做），通常更可能损失性能
  • 当使用public boolean remove(Object o)方法删除元素时，只会删除第一个找到的对应元素
标签：

评论

发表评论

此博客中的热门博文

国密SM2签名封装成PKCS7格式

在国内做金融行业，难免会有被强制使用国密算法的情况，而且一般还会指定必须使用硬件加密机之类的设备，所以我也稍微的研究了一下国密算法，使用软算法签名并封装 PKCS7 格式（文档中的一个交互）。 以下是基于 Bouncy Castle 的示例，密钥对的生成可以参考 Bouncy Castle 中 test 包下 SM2 相关代码 public static String sign ( ) throws Exception { //加载公钥 byte [ ] plainText = "hello, world" . getBytes ( ) ; FileInputStream input = new FileInputStream ( "F:\\certificate\\public.cer" ) ; CertificateFactory certificateFactory = new CertificateFactory ( ) ; X509Certificate certificate = ( X509Certificate ) certificateFactory . engineGenerateCertificate ( input ) ; input . close ( ) ; //加载私钥，private为换成实际的私钥 PKCS8EncodedKeySpec spec = new PKCS8EncodedKeySpec ( "private" . getBytes ( ) ) ; //SM2算法实际上为ECC算法，并指定了一些参数值，所以这里的参数是EC KeyFactory factory = KeyFactory . getInstance ( "EC" , "BC" ) ; PrivateKey privateKey = factory . generatePrivate ( spec ) ; //以下为签名并封装成PKCS7格式 byte [ ] signedMessag
发表评论
阅读全文

Spring Boot Actuator 2 示例

Welcome file 简介 Spring Boot Actuator为应用程序提供了各种开箱即用的运维特性，可以与应用方便的交互和监控。 使用环境：Java 11 和 Spring Boot 2.4.3.RELEASE 集成Spring Boot Actuator 在Spring Boot中集成Spring Boot Actuator与集成其他的框架类似，在 pom.xml 里引入相关的starter就可以： < dependency > < groupId > org.springframework.boot </ groupId > < artifactId > spring-boot-starter-actuator </ artifactId > </ dependency > < dependency > < groupId > org.springframework.boot </ groupId > < artifactId > spring-boot-starter-web </ artifactId > </ dependency > 由于大部分的使用场景还是web，所以这里也用Spring MVC做示例。 配置好 pom.xml 后，默认actuator仅暴露一些基本功能，实际使用中，根据需求暴露对应功能。为了简便测试，这里在 application.yml 中配置暴露全部功能： management : endpoints : web : exposure : include : "*" endpoint : health : enabled : true show-details : always probes : enabled : true shutdown : enabled : true metr
发表评论
阅读全文

NextCloud数据目录迁移

最近服务器的环境坏了，所以迁移了NextCloud的数据目录。不过在迁移过程中有点小问题。 环境： Ubuntu 18.04 Docker 19.03.7 1.NextCloud页面不正常，Docker日志显示XX目录permission denied 参考了 这里 的做法，不过是把  /var/www/html/   整个目录的权限都修改为  chown -R www-data:www-data ，之后就不再报权限问题了。 2.数据库配置修改 因为NextCloud是在初始化时填的数据库连接信息，所以直接迁移数据目录的情况下，会导致应用连不到新的数据库环境。此时可以找到数据目录下的  config/config.php 文件，直接修改数据库连接配置。
发表评论
阅读全文