Home > Java > javaTutorial > body text

Java practice: a simple dynamic array implementation

php是最好的语言
Release: 2018-08-09 14:07:02
Original
1970 people have browsed it

A simple dynamic array implementation

Based on the array implementation, adding 10w of capacity and deleting all the capacity takes an average of 0.4 seconds. This efficiency is considerable. Let’s take a look at the code.

package com.array;

import java.util.List;
import java.util.Random;

/**
 * 
 * @author XiaoTian
 * @date 2018-08-08
 */
//基于动态数组的实现 E 是泛型
//借用了一下 Java中的ArrayList的代码
//研究源码也是一种乐趣
//还能让我们技术有所提高
public class ArrayList<E> implements java.io.Serializable{
	/**
     * 初始容量
    */
    private static final int DEFAULT_CAPACITY = 10;
    
    /**
     * 用于空实例的共享空数组实例。
     */
    transient Object[] EMPTY_ELEMENTDATA = {};
    
    /**
     * 数组缓冲区,其中存储ArrayList的元素。
     * ArrayList的容量是这个数组缓冲区的长度。
     */
    transient Object[] elementData;
    
    /**
     * 用于默认大小的空实例的共享空数组实例。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    /**
     * 大小
     */
    private int size;
    
    /**
     * 默认为空
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 自定义空间大小
     * @param initialCapacity
     */
    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 int size() {
		return size;
	}

    /**
     * 添加一个元素 元素位置是最后
     * @param e
     */
    public void add(E e) {
    	ExtendElement(size + 1);
    	this.elementData[size++] = e;
    }
    /**
     * 在头部添加元素
     * @param e
     */
    public void addHead(E e) {
    	this.elementData[0] = e;
    }
    
    /**
     * 扩展元素
     */
    private void ExtendElement(int size) {
    	//容量
    	if(this.elementData.length == 0) {
    		elementData = new Object[DEFAULT_CAPACITY];
    	}else if(this.elementData.length < size) {
    		EMPTY_ELEMENTDATA = elementData;
    		//获取当前容量
    		int oldCapacity = elementData.length;
    		//扩展容量 i + i >> 1 就是 i的1.5倍
    		int newCapacity = oldCapacity + (oldCapacity >> 1);
    		elementData = new Object[newCapacity];
    		//1.源数组 2.源数组要复制的起始位置 3.目的数组 4.目的数组放置的起始位置 5.复制的长度
    		/**
    		 * 调用 System的静态方法 arraycopy() 进行数组拷贝
    		 * 标识为native意味JDK的本地库
    		 * 如果频繁扩容会降低ArrayList的使用性能
    		 * 赋值过程
    		 */
    		System.arraycopy(EMPTY_ELEMENTDATA,0,elementData,0,size-1);
    	}
    }
    
    /**
     * 删除一个元素
     */
    public E remove(int index) {
    	rangeCheck(index);
    	E oldValue = elementData(index);
    	int numMoved = size - index - 1;
    	if (numMoved > 0)
    		//index + 1 是当前 index 下一个 之 赋给 index 就全部替换了
            System.arraycopy(elementData, index+1, elementData, index,
            		numMoved);
    	elementData[--size] = null; // 清楚地让GC完成它的工作
    	//判断容量是否是当前的1/4 是就 缩容 不要浪费不必要的内存空间
    	ShrinkageCapacity();
    	return oldValue;
    }
    
    /**
     * 删除最后一个
     * @return
     */
    public E removeLast() {
    	return remove(this.size - 1);
    }
    
    /**
     * 判断是否大于size
     * @param index
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    //输出 Index 和 Size
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    /**
     * 获取元素
     * @param index
     * @return
     */
    public E get(int index) {
    	rangeCheck(index);
    	return elementData(index);
    }
    /**
     * 查询当前元素的值
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    E elementData(int index) {
    	//获取索引位置的元素
        return (E) elementData[index];
    }
    
    /**
     * 缩容
     * @param args
     */
    public void ShrinkageCapacity() {
    	if(size == elementData.length / 4 && elementData.length / 2 != 0) {
    		EMPTY_ELEMENTDATA = elementData;
    		//缩二分之一
    		int oldCapacity = elementData.length / 2;
    		elementData = new Object[oldCapacity];
    		System.arraycopy(EMPTY_ELEMENTDATA,0,elementData,0,size-1);
    	}
    }
    //测试
    public static void main(String[] args) {
    	long then = System.currentTimeMillis();
		ArrayList<Integer> arrayList = new ArrayList<>();
		Random random = new Random();
		for (int i = 0; i < 100000; i++) {
			arrayList.add(random.nextInt());
		}
		for (int i = 0; i < 99999; i++) {
			arrayList.remove(0);
		}
		long now = System.currentTimeMillis();
		System.out.println("Elapsed time:" + (now - then)+" 毫秒");
 	}
}
Copy after login

Java practice: a simple dynamic array implementation

This is the time to run the above code. Everyone’s machine is different, and the running effect is also different. For reference only

Related recommendations:

Java's dynamic proxy class implements a simple example of log

java A simple implementation of dynamically loading classes using the java reflection mechanism

The above is the detailed content of Java practice: a simple dynamic array implementation. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template