ArrayList与HashSet存储的异同探究

【构造方法】

 

ArrayList通过数组来存储对象，构造ArrayList会新建一个数组。默认情况下这个数组的初始化大小是10，可通过传入参数initialCapacity修改它的初始化大小。（See Code）

 

    private transient Object[] elementData;

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

    public ArrayList() {
	this(10);
    }

 

HashSet通过HashMap来存储对象，构造HashSet时会新建一个HashMap作为成员属性。（See Code）

 

    private transient HashMap<E,Object> map;

    public HashSet() {
	map = new HashMap<E,Object>();
    }

 

 

【添加元素】

 

 ArrayList添加元素时，会对数组的容量大小作判断并根据ArrayList容量的增长策略作调整。ArrayList提供两个方法来添加元素，分别是直接将新元素添加到数组第一个空位置上和添加数组的指定位置，若是添加到指定的位置，则原来该位置上的元素及其后的元素都要往后移动一个位置。（See Code）

 

    public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }

    public void add(int index, E element) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

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

 

值得注意的，是ArrayList的数组存储容量的增长策略。通过公式：(原来的容量大小*3)/2+1求得新的容量值newCapacity，将newCapacity与所要求的最小容量minCapacity进行比较，若比minCapacity大的话，则取newCapacity作为扩大后的容量大小，若比minCapacity小的话，则取minCapacity作为扩大后的大小。（See Code）

    public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

 

HashSet添加新对象时， 将新对象作为Map的Key，将常量对象PRESENT作为Value，以标识这个新对象已被添加。（See Code）

 

    private static final Object PRESENT = new Object();

    public boolean add(E e) {
	return map.put(e, PRESENT)==null;
    }

 

 值得注意的是，Set不存储重复的对象，它是通过equals方法来判断的。（若是null，通过==来判断）

 

【移除元素】

 

跟add方法一样，ArrayList的remove方法也提供两种重载的方式。remove(int index)方法移除数组某个位置上的对象，移除之后，index位置后面的所有元素都前移一个位置。而原来的最后的位置上则置空。remove(Object o)方法有所不同，它选遍历数组，通过equals方法来找到与o匹配的对象的位置，再根据位置来移除。所以，后者比前者多了一个查找的过程。

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

	modCount++;
	E oldValue = (E) 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;
    }

    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
    }

 

HashSet的remove(Object o)方法，是通过HashMap的remove(Object o)方法来移除元素的。（代码略）

 

【查找元素】

ArrayList通过E get(int index)方法返回数组指定位置的对象。在此过程中，会作一个范围检查，若index大于或等于数组的长度，则抛IndexOutOfBoundsException异常。（代码略）

 

HashSet因为是无序的，所以不具有根据位置获取元素的方法。

 

此外，java.lang.System类的arraycopy方法常常在集合类中出现，它实现的功能是将某数组连续位置上的若干元素复制到另一数组的某段连续位置上。它是一个native的方法，我们来看一下它的声明。（See Code）

    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

arraycopy方法的5个参数分别表示什么？src指原数组，srcPos是从原数组的什么位置开始复制，dest复制的若干元素放置的目的地数组，destPos是将复制的数组元素放置不目标数组的什么位置上，length指复制的长度，即复制多少个连续的元素。