ArrayList源码分析

╰半夏微凉° 2022-05-23 10:06 335阅读 0赞

# ArrayList源码分析 #

## 类的实现接口及继承父类 ##

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

### AbstractList 和 List ###

ArrayList 和AbstractList 都实现了List接口。  
并且AbstractList是ArrayList的父类。

### RandomAccess ###

RandomAccess接口里没有方法需要实现。这是一个很特别的空接口。这个接口的作用是：

List实现它能够支持快速随机访问。主要能提高随机访问的性能。
    	 for (int i=0, n=list.size(); i < n; i++)
            list.get(i);
    	比下面这种快。
    	for (Iterator i=list.iterator();i.hasNext(); )
            i.next();

### Cloneable ###

此接口也是一个空接口，实现次接口，需要重写object对象的clone()方法，并且方法是访问权限是public的。

clone()是值拷贝，即为浅拷贝。

测试是否为浅拷贝：

拷贝对象：

package xuelongjiang.ArrayListCloneTest;
    
    	/** * @author xuelongjiang */
    	public class User { 
    
        private String name ;
    
        private Integer sex;
    
        public User() { 
        }
    
        public User(String name, Integer sex) { 
            this.name = name;
            this.sex = sex;
        }
    
        public String getName() { 
            return name;
        }
    
        public void setName(String name) { 
            this.name = name;
        }
    
        public Integer getSex() { 
            return sex;
        }
    
        public void setSex(Integer sex) { 
            this.sex = sex;
        }
    
    
        @Override
        public String toString() { 
            return "User{" +
                    "name='" + name + '\'' +
                    ", sex=" + sex +
                            "//\n" +
                    getClass().getName() + "@" + Integer.toHexString(hashCode())+
                    '}';
        }
    }

测试类：

package xuelongjiang.ArrayListCloneTest;
    
    
    	import java.util.ArrayList;
    	import java.util.List;
    
    	/** * * 结论： clone 是浅拷贝 值相同，对象的引用相同 * @author xuelongjiang */
    	public class CloneObject { 
    
    
        public static void main(String[] args) { 
    
    
            ArrayList<User> userList = new ArrayList<>();
            userList.add(new User("xue",1));
            userList.add(new User("lisi",2));
    
            System.out.println("------------原始值-------------");
            for(User user : userList){ 
                System.out.println(user);
            }
    
    
            List<User> cloneList  = (List<User>) userList.clone();
            System.out.println("------------拷贝值-------------");
            for(User user : cloneList){ 
                System.out.println(user);
            }
    
    
        }
    
    	}

输出：

------------原始值-------------
    		User{ name='xue', sex=1//
    		xuelongjiang.ArrayListCloneTest.User@2d98a335}
    		User{ name='lisi', sex=2//
    		xuelongjiang.ArrayListCloneTest.User@16b98e56}
    		------------拷贝值-------------
    		User{ name='xue', sex=1//
    		xuelongjiang.ArrayListCloneTest.User@2d98a335}
    		User{ name='lisi', sex=2//
    		xuelongjiang.ArrayListCloneTest.User@16b98e56}

## 实现ArrayList的容器 ##

ArrayList的底层实现为数组。

transient Object[] elementData;

从上面我们可以看出数组为obejct。在取出值的时候利用范型转为声明的类型。

## 构造方法 ##

ArrayList 有三个构造方法

### 第一种构造方法： ###

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    	public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    	}

如果使用无参的构造方法，则初始化的数组为空（注意不为null）。

### 第二种构造方法 ###

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);
        }
    	}

如果初始化的容器值大于0，则初始化为这个值。如果等于0 则初始化为空

private static final Object[] EMPTY_ELEMENTDATA = {};

如果小于0则抛出异常。

### 第三种构造方法： ###

public ArrayList(Collection<? extends E> c) { 
        elementData = c.toArray();
        if ((size = elementData.length) != 0) { 
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    	}

由于ArrayList的底层实现是Object\[\] 需要把Collection转为Object\[\]。并且设置size为传入的Collection大小。

## 常用方法解析 ##

### size() list的元素数 ###

size方法很简单直接返回size值的大小。

private int size;
    
    	public int size() { 
      	  return size;
    	}

### add() ###

在add方法中会对elemenrData进行扩容，如果不需要扩容或者扩容完成了，就把需要添加的元素放入elementData中，并且size自增。

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

在ensureCapacityInternal中如果容器为空，比较需要扩容的大小和DEFAULT\_CAPACITY(= 10)  
如果大于DEFAULT\_CAPACITY，则使用本次传入的否则设置容量为DEFAULT\_CAPACITY。

private void ensureCapacityInternal(int minCapacity) { 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

ensureExplicitCapacity(minCapacity);
    }

ensureExplicitCapacity方法:

private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    	}

如果本次需要的扩容大于elementData的长度，则调用grow方法扩容。

private void grow(int minCapacity) { 
        // overflow-conscious code
        int oldCapacity = elementData.length;//1
        int newCapacity = oldCapacity + (oldCapacity >> 1);//2
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;//3
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);//4
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//5
    	}

1.  获取当前容器的大小
2.  计算新的扩容大小：扩容1.5倍
3.  如果默认扩容小于本次需要扩容的大小，则设置为本次需要的扩容大小，否则设为默认扩容
    
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        
        
          public static final int   MAX_VALUE = 0x7fffffff;//2的31次方，大于20多亿
4.  如果本次需要的扩容大于MAX\_ARRAY\_SIZE，则容器设置为Integer.MAX\_VALUE，如果等于MAX\_ARRAY\_SIZE则设为MAX\_ARRAY\_SIZE。
5.  拷贝生成扩容后的容器

### remove() ###

public E remove(int index) { 
        	rangeCheck(index);//1
    	   	modCount++;
      		 E oldValue = elementData(index);//2
    
      	  		int numMoved = size - index - 1;//3
      	  	if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//4
        	elementData[--size] = null; // clear to let GC do its work
        	return oldValue;
    		}

移除元素后，需要把它之后的虽有元素向前移动1位。

1.  检查索引是否超出范围
2.  返回被移除的元素
3.  需要向前移动的元素数
4.  移动元素：拷贝

### contains() 是否包含某元素 ###

public boolean contains(Object o) { 
        return indexOf(o) >= 0;
    	}
    
    	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;
    	}

循环容器判断每一个元素是否和目标值相等。  
**注意：如果是对象的话这里比较的对象的引用，在开发中很多时候我们要比较的实体，实体映射的是数据库里的一条记录，比较的其实是主键是否相等，所以如果  
是这种情况需要重写equal方法及hashCode方法**

### clear() ###

public void clear() { 
        modCount++;
    
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
    
        size = 0;
    	}

把容器中的每个元素的值设为null，之后垃圾回收机制会收回被使用的内存。

## 迭代器 ##

java5之后，集合框架可以使用迭代器，并且提供了foreach语法糖。

public Iterator<E> iterator() { 
       		 return new Itr();
    	}
    
    	
    	public E next()
    	public boolean hasNext()

迭代器模式：[https://blog.csdn.net/u013565163/article/details/79291801][https_blog.csdn.net_u013565163_article_details_79291801]

\#\#开发中的易犯错误

[https://blog.csdn.net/u013565163/article/details/64122639][https_blog.csdn.net_u013565163_article_details_64122639]

[https_blog.csdn.net_u013565163_article_details_79291801]: https://blog.csdn.net/u013565163/article/details/79291801
[https_blog.csdn.net_u013565163_article_details_64122639]: https://blog.csdn.net/u013565163/article/details/64122639