四.Java 集合

4.1 声明为接口类

List list=new ArrayList();

4.2 fast-fail机制

	for (Iterator<Integer> iter = list.iterator(); iter.hasNext();)
	{
		 int i = iter.next();
		 if (i == 3)
		 {
		     list.remove(i);
		 }
	}

如果一边循环List，一边更改list中的数据，就会报错：
java.util.ConcurrentModificationException
API中此异常的解释：当方法检测到对象的并发修改，但不允许这种修改时，抛出此异常。
以HashMap为例：

 	 final Entry<K,V> nextEntry() {
   	if (modCount != expectedModCount)
   		throw new ConcurrentModificationException();
   //...

modCount为修改次数，每次更改HashMap(put,remove等等)会使modCount发生改变，
而迭代的时候会检查modCount和expectedModCount是否相等，不相等就抛出ConcurrentModificationException异常。
这也是java Iterator的fast-fail机制。源码中有注释：
int expectedModCount; // For fast-fail

解决方法：
(1)倒过来遍历list
(2)用iterator.remove()方法
(3)每移除一个元素以后再把i移回来

4.3 ArrayList和LinkedList的速度

随机读取：

		List<String> list = new ArrayList<String>();
		for(int i=0;i<1000;i++)
		{
			list.add("ArrayList");
		}
		long start=System.nanoTime();
		String s1=list.get(99);
		long end=System.nanoTime();
		System.out.println("ArrayList 耗时: "+(end-start));

ArrayList 耗时: 4141
LinkedList 耗时: 11150


可以看出来随机读取，ArrayList要快于LinkedList，
通过源码可以看出来:
ArrayList.java
private transient Object[] elementData;
LinkedList.java
transient Node<E> first;
transient Node<E> last;
ArrayList采用数组结构,而LinkedList采用链表数据结构。所以ArrayList要快些。


LinkedList在API中有一句解释：在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。
所以list.get(p)，p越靠近中间，需要的时间越久。
测试：

list.size()=1000 p=7   LinkedList 耗时: 8283
list.size()=1000 p=500 LinkedList 耗时: 18795
list.size()=1000 p=987 LinkedList 耗时: 8601

4.4 ArrayList的实现原理

创建ArrayList：
List<String> list = new ArrayList<String>();
当new 一个ArrayList时，最后会调用这段代码：

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

可以看到，ArrayList底层使用数组实现，java会默认创建一个长度为10的数组，


添加一个元素：
先计算容量（Capacity）是否合适，在把元素添加到数组末尾，add操作会使modCount增加，源码中也有注释。

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

在ensureCapacityInternal()中：

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

因为底层用的数组实现，所以add时候如果数组容量不够，就去调用grow()给数组扩容，
调整数组容量，具体实现是将老数组按照新的大小copy到新的数组。
elementData = Arrays.copyOf(elementData, newCapacity);
新的大小是按照原来数组大小的1.5倍（不超过最大容量MAX_ARRAY_SIZE）：
int newCapacity = oldCapacity + (oldCapacity >> 1);
如果有必要也可以指定ArrayList的实际容量，最后也是通过ensureCapacityInternal()来实现。


删除一个元素：
remove(int index) 最后使元素=null

elementData[--size] = null

remove(Object o)则是通过遍历来确定元素的index，然后用fastRemove(int index)来删除，
所以remove(int index)效率要高于remove(Object o)

4.5 其他集合的实现原理

以HashSet为例：
public HashSet() {
map = new HashMap<>();
}
底层实际上还是一个HashMap。也就是说，其实HashSet底层是采用HashMap实现的。
而HashMap底层又是采用数组实现：
transient Entry<K,V>[] table;
!变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。
多看看JDK的源码，也就了解了。