ArrayList

作者: Tomy_Jx_Li | 来源:发表于2019-05-03 16:18 被阅读0次

    前期自己对于源码解析,以为看过既可以,然后就是类似翻译的动作而已。后期发现这种形式并没有什么好的。所以需要重新思考。
    看源码前的准备。

    1.ArrayList是什么

    首先根据如下图:


    ArrayList类图

    1.最顶级接口Iterable,这个是迭代器模式的顶级接口,忽略
    2.Collection接口,这个就是集合类的顶级接口了
    3.List接口,列表类顶级接口,于set集合区分
    4.RandomAccess接口,是一个标记接口。表明当前类可以进行快速随机访问。忽略
    5.Cloneable接口,标记接口。表明深拷贝。忽略
    6.其他的序列化接口,和集合的抽象实现,列表的抽象实现。
    所以从ArrayList的类图可以看出,ArrayList就是一个集合类。且是一个列表集合,即支持可重复的集合元素。

    2.ArrayList能干什么

    通过前面的分析,知道ArrayList是一个列表集合的具体实现。那么列表集合能干什么呢。最基础的应用就是存储。将数据存储到内存中。且存储的内容是按照存入的先后顺序进行存储的。

    3.分析准备

    在进行ArrayList分析之前,ArrayList是什么,能干什么我们已经很清楚了。那么首先我们自己先分析下,如果自己去写一个集合都需要干什么呢。

    3.1类比

    这种分析一般都是需要对照到生活中的例子进行类比分析,然后进行代码实现,才能更好的理解类。首先集合类似于我们生活中的仓库。

    3.2操作

    既然是仓库那么就需要存储货物。而存储货物的时候最基本的操作。
    1.入库
    2.出库
    3.清点货物总数
    4.查看货物

    3.3自己实现

    根据自己的思路实现一个ArrayList

    package com.jiyx.test.collect;
    
    /**
     *
     * auther: jiyx
     * date: 2019-05-02
     */
    public class MyArrayList {
    
        private Object[] items = new Object[64];
    
        private int currIndex;
    
        /**
         * 入库
         * @param item
         */
        public void add(Object item) {
            rangeCheckOut(currIndex);
            items[currIndex++] = item;
        }
    
        /**
         * 查看,不出库
         * @param index
         * @return
         */
        public Object get(int index) {
            rangeCheckOut(index);
            return items[index];
        }
    
        /**
         * 出库
         * @param index
         * @return
         */
        public Object remove(int index) {
            rangeCheckOut(index);
            Object value = items[index];
            if (items.length - index - 1 > 0) {
                System.arraycopy(items, index + 1, items, index, items.length - index - 1);
            }
            currIndex--;
            return value;
        }
    
        /**
         * 当前存储的元素个数
         * @return
         */
        public int size() {
            return currIndex;
        }
    
        /**
         * 角标越界校验
         * @param currIndex
         */
        private void rangeCheckOut(int currIndex) {
            if (currIndex > items.length - 1) {
                throw new ArrayIndexOutOfBoundsException();
            }
        }
    
        public static void main(String[] args) {
            MyArrayList list = new MyArrayList();
            list.add(1);
            list.add("aaa");
            list.add(list);
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
            list.remove(1);
            list.add("bbb");
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
        }
    }
    

    4.分析

    好了进入正题,进行ArrayList源码浅析。这里ArrayList无非也是上面的几个操作,不过可能比我写的更加完善,功能更多而已。
    那么同样的,还是按照基本功能,外加一个初始化进行分析。

    4.1初始化

    因为仓库是没有的,所以我们需要自己手动创建一个仓库的。那么new的过程就是创建这个仓库的过程。
    初始化分为三种,无参构造、传入初始容量构造器、传入老的集合的构造器。其实初始化的过程很简单。可以自行查看。不过这里有两个变量需要注意。EMPTY_ELEMENTDATADEFAULTCAPACITY_EMPTY_ELEMENTDATA。因为在创建的过程无参构造时需要用到后者。其他两个构造都是用到了前者。这两个虽然值和存在的意义都一样。区别是,在第一个元素添加的时候。前者的第一次扩容为1。而后者的第一次扩容为10。

    4.1入库

    Arraylist的入库入口为add方法。重载了两个方法。

        public boolean add(E e) {
            // 判断容量是否足够,如果不足进行扩容
            ensureCapacityInternal(size + 1);
            // 添加元素
            elementData[size++] = e;
            return true;
        }
        public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            // 判断容量是否足够,如果不足进行扩容
            ensureCapacityInternal(size + 1);
            // 腾出需要插入元素的位置,也就是将元素后移一位
            System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);
            // 添加元素
            elementData[index] = element;
            size++;
        }
    

    而且这里面必须介绍下方法ensureCapacityInternal及其设计到的方法,都不是很复杂。如下:

        private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    
        /**
         * 计算最小容量
         * @param elementData
         * @param minCapacity
         * @return
         */
        private static int calculateCapacity(Object[] elementData, int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
        /**
         * 根据最小容量确认是否需要进行扩容
         * @param minCapacity
         */
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        /**
         * 具体的扩容操作
         * @param 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);
        }
    

    4.2出库

    出库的动作是由remove完成的。这个也比较简单了。但是呢,重载了两个,因为在从仓库中移除物品的时候。可能根据编号,也可能根据某个物品。

        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);
            // 将最后一位设置为null
            elementData[--size] = null;
    
            return oldValue;
        }
        /**
         * 移出,不返回对象。因为我们知道要移出的是哪个对象
         * @param o
         * @return
         */
        public boolean remove(Object o) {
            if (o == null) {
                // 移除null值
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        // 真正的移出数据
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    // 对象的移出,是根据equals进行判断的,所以对象要重写这个方法
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    
        /**
         * 相对于remove(int index)方法,少了角标校验,也没有返回值
         * 因为调用方法的也就remove(Object o),而他是在循环遍历中调用的,所以这里不做角标校验
         * @param index
         */
        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;
        }
    

    4.3清点货物总数

    因为一般我们的仓库管理时,在物品入库的时候,会做一个记录。所以直接查看记录就知道有多少物品了。

        public int size() {
            return size;
        }
    

    4.4查看货物

    get方法,比较简单

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

    4.5其他方法

    当然了,ArrayList中还有很多实用的方法。如

        /**
         * 是否包含某对象
         * @param o
         * @return
         */
        public boolean contains(Object o) {
            return indexOf(o) >= 0;
        }
    
        /**
         * 查看对象在仓库arrayList中的位置
         * @param o
         * @return
         */
        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;
        }
        /**
         * 查找最近入库的相同的对象
         * @param o
         * @return
         */
        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;
        }
        /**
         * 批量的入库
         * @param c
         * @return
         */
        public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }
    
        /**
         * 从指定位置开始批量入库
         * @param index
         * @param c
         * @return
         */
        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);
    
            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;
        }
    
    

    5.可修改的问题

    1.方法中会出现a-b>0这种代码。感觉没有a>b来的清晰明了
    2.代码中存在很多重复代码。如remove(Object o)就是修改为如下

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

    相关文章

      网友评论

          本文标题:ArrayList

          本文链接:https://www.haomeiwen.com/subject/nojjtqtx.html