集合类解析

JAVA集合类详解

Collection

collection接口为JAVA所有集合类的根接口，代表容器。它为实现类提供了一些基本的操作，但是没有类直接对它实现，一般是对它进行接口扩展。然后定义一些骨干实现，从而减少工作量，例如AbstractCollection。

Iterable

Collection接口扩展了Iterable接口，所以所有的集合的实现类都必须实现Iterator<T> iterator()方法，返回一个迭代器对集合进行迭代。
除此之外foreach的本质就是通过迭代器来实现的，因此实现了Iterable接口的都可以foreach

collection的主要子接口有三个，分别代表三种功能的容器 List Queue Set ,Map不是

List及其子类

List接口本身对Collection接口进行扩展，添加了listIterator()返回Iterator的子类ListIterator（可按任意方向遍历列表）

AbstractList

继承AbstractCollection提供了List接口的骨干实现

• Vector 最早的以数组实现的集合类，但是因为实现并发需要同步，而带来了性能的损失，因此基本上已经弃用，而它的子类Stack更是饱受诟病，是最早JDK的一个失误，之所以不去掉它或是重写只是为了兼容之前版本的项目，现在基本由LikedList实现
• ArrayList 内部以数组实现，后面进行详细解释

• AbstractSequentialList它的实现类只有LinkedList，可能在这里写一个骨干实现是为了之后的扩展。

  ###ListIterator
  ListIterator 没有当前元素；它的光标位置 始终位于调用 previous() 所返回的元素和调用 next() 所返回的元素之间。在长度为 n 的列表中，有 n+1 个有效的索引值，从 0 到 n（包含）。

  Element(0)   Element(1)   Element(2)   ... Element(n)   
^            ^            ^            ^               ^

Index: 0 1 2 3 n+1

ArrayList源码分析

package java.util;  
 
public class ArrayList<E> extends AbstractList<E>  
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
{  
    // 序列版本号  
    private static final long serialVersionUID = 8683452581122892189L;  
 
    // ArrayList基于该数组实现，用该数组保存数据 
    private transient Object[] elementData;  
 
    // ArrayList中实际数据的数量  
    private int size;  
 
    // ArrayList带容量大小的构造函数。  
    public ArrayList(int initialCapacity) {  
        super();  
        if (initialCapacity < 0)  
            throw new IllegalArgumentException("Illegal Capacity: "+  
                                               initialCapacity);  
        // 新建一个数组  
        this.elementData = new Object[initialCapacity];  
    }  
 
    // ArrayList无参构造函数。默认容量是10。  
    public ArrayList() {  
        this(10);  
    }  
 
    // 创建一个包含collection的ArrayList  
    public ArrayList(Collection<? extends E> c) {  
        elementData = c.toArray();  
        size = elementData.length;  
        if (elementData.getClass() != Object[].class)  
            elementData = Arrays.copyOf(elementData, size, Object[].class);  
    }  
 
 
    // 将当前容量值设为实际元素个数  
    public void trimToSize() {  
        modCount++;  
        int oldCapacity = elementData.length;  
        if (size < oldCapacity) {  
            elementData = Arrays.copyOf(elementData, size);  
        }  
    }  
 
 
    // 确定ArrarList的容量。  
    // 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”  
    public void ensureCapacity(int minCapacity) {  
        // 将“修改统计数”+1，该变量主要是用来实现fail-fast机制的  
        modCount++;  
        int oldCapacity = elementData.length;  
        // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”  
        if (minCapacity > oldCapacity) {  
            Object oldData[] = elementData;  
            int newCapacity = (oldCapacity * 3)/2 + 1;  
			//如果还不够，则直接将minCapacity设置为当前容量
            if (newCapacity < minCapacity)  
                newCapacity = minCapacity;  
            elementData = Arrays.copyOf(elementData, newCapacity);  
        }  
    }  
 
    // 添加元素e  
    public boolean add(E e) {  
        // 确定ArrayList的容量大小  
        ensureCapacity(size + 1);  // Increments modCount!!  
        // 添加e到ArrayList中  
        elementData[size++] = e;  
        return true;  
    }  
 
    // 返回ArrayList的实际大小  
    public int size() {  
        return size;  
    }  
 
    // ArrayList是否包含Object(o)  
    public boolean contains(Object o) {  
        return indexOf(o) >= 0;  
    }  
 
    //返回ArrayList是否为空  
    public boolean isEmpty() {  
        return size == 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;  
        }  
 
        // 反向查找，返回元素的索引值  
        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;  
    }  
 
    // 反向查找(从数组末尾向开始查找)，返回元素(o)的索引值  
    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;  
    }  
   
 
    // 返回ArrayList的Object数组  
    public Object[] toArray() {  
        return Arrays.copyOf(elementData, size);  
    }  
 
    // 返回ArrayList元素组成的数组
    public <T> T[] toArray(T[] a) {  
        // 若数组a的大小 < ArrayList的元素个数；  
        // 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中  
        if (a.length < size)  
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());  
 
        // 若数组a的大小 >= ArrayList的元素个数；  
        // 则将ArrayList的全部元素都拷贝到数组a中。  
        System.arraycopy(elementData, 0, a, 0, size);  
        if (a.length > size)  
            a[size] = null;  
        return a;  
    }  
 
    // 获取index位置的元素值  
    public E get(int index) {  
        RangeCheck(index);  
 
        return (E) elementData[index];  
    }  
 
    // 设置index位置的值为element  
    public E set(int index, E element) {  
        RangeCheck(index);  
 
        E oldValue = (E) elementData[index];  
        elementData[index] = element;  
        return oldValue;  
    }  
 
    // 将e添加到ArrayList中  
    public boolean add(E e) {  
        ensureCapacity(size + 1);  // Increments modCount!!  
        elementData[size++] = e;  
        return true;  
    }  
 
    // 将e添加到ArrayList的指定位置  
    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指定位置的元素  
    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;  
    }  
 
    // 删除ArrayList的指定元素  
    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;  
    }  
 
 
    // 快速删除第index个元素  
    private void fastRemove(int index) {  
        modCount++;  
        int numMoved = size - index - 1;  
        // 从"index+1"开始，用后面的元素替换前面的元素。  
        if (numMoved > 0)  
            System.arraycopy(elementData, index+1, elementData, index,  
                             numMoved);  
        // 将最后一个元素设为null  
        elementData[--size] = null; // Let gc do its work  
    }  
 
    // 删除元素  
    public boolean remove(Object o) {  
        if (o == null) {  
            for (int index = 0; index < size; index++)  
            if (elementData[index] == null) {  
                fastRemove(index);  
            return true;  
            }  
        } else {  
            // 便利ArrayList，找到“元素o”，则删除，并返回true。  
            for (int index = 0; index < size; index++)  
            if (o.equals(elementData[index])) {  
                fastRemove(index);  
            return true;  
            }  
        }  
        return false;  
    }  
 
    // 清空ArrayList，将全部的元素设为null  
    public void clear() {  
        modCount++;  
 
        for (int i = 0; i < size; i++)  
            elementData[i] = null;  
 
        size = 0;  
    }  
 
    // 将集合c追加到ArrayList中  
    public boolean addAll(Collection<? extends E> c) {  
        Object[] a = c.toArray();  
        int numNew = a.length;  
        ensureCapacity(size + numNew);  // Increments modCount  
        System.arraycopy(a, 0, elementData, size, numNew);  
        size += numNew;  
        return numNew != 0;  
    }  
 
    // 从index位置开始，将集合c添加到ArrayList  
    public boolean addAll(int index, Collection<? extends E> c) {  
        if (index > size || index < 0)  
            throw new IndexOutOfBoundsException(  
            "Index: " + index + ", Size: " + size);  
 
        Object[] a = c.toArray();  
        int numNew = a.length;  
        ensureCapacity(size + numNew);  // Increments modCount  
 
        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;  
    }  
 
    // 删除fromIndex到toIndex之间的全部元素。  
    protected void removeRange(int fromIndex, int toIndex) {  
    modCount++;  
    int numMoved = size - toIndex;  
        System.arraycopy(elementData, toIndex, elementData, fromIndex,  
                         numMoved);  
 
    // Let gc do its work  
    int newSize = size - (toIndex-fromIndex);  
    while (size != newSize)  
        elementData[--size] = null;  
    }  
 
    private void RangeCheck(int index) {  
    if (index >= size)  
        throw new IndexOutOfBoundsException(  
        "Index: "+index+", Size: "+size);  
    }  
 
 
    // 克隆函数  
    public Object clone() {  
        try {  
            ArrayList<E> v = (ArrayList<E>) super.clone();  
            // 将当前ArrayList的全部元素拷贝到v中  
            v.elementData = Arrays.copyOf(elementData, size);  
            v.modCount = 0;  
            return v;  
        } catch (CloneNotSupportedException e) {  
            // this shouldn't happen, since we are Cloneable  
            throw new InternalError();  
        }  
    }  
 
 
    // java.io.Serializable的写入函数  
    // 将ArrayList的“容量，所有的元素值”都写入到输出流中  
    private void writeObject(java.io.ObjectOutputStream s)  
        throws java.io.IOException{  
    // Write out element count, and any hidden stuff  
    int expectedModCount = modCount;  
    s.defaultWriteObject();  
 
        // 写入“数组的容量”  
        s.writeInt(elementData.length);  
 
    // 写入“数组的每一个元素”  
    for (int i=0; i<size; i++)  
            s.writeObject(elementData[i]);  
 
    if (modCount != expectedModCount) {  
            throw new ConcurrentModificationException();  
        }  
 
    }  
 
 
    // java.io.Serializable的读取函数：根据写入方式读出  
    // 先将ArrayList的“容量”读出，然后将“所有的元素值”读出  
    private void readObject(java.io.ObjectInputStream s)  
        throws java.io.IOException, ClassNotFoundException {  
        // Read in size, and any hidden stuff  
        s.defaultReadObject();  
 
        // 从输入流中读取ArrayList的“容量”  
        int arrayLength = s.readInt();  
        Object[] a = elementData = new Object[arrayLength];  
 
        // 从输入流中将“所有的元素值”读出  
        for (int i=0; i<size; i++)  
            a[i] = s.readObject();  
    }  
}

ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法。我们有必要对这两个方法的实现做下深入的了解。

首先来看Arrays.copyof()方法。它有很多个重载的方法，但实现思路都是一样的，我们来看泛型版本的源码：

public static <T> T[] copyOf(T[] original, int newLength) {
		        return (T[]) copyOf(original, newLength, original.getClass());
    }

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

这里可以很明显地看出，该方法实际上是在其内部又创建了一个长度为newlength的数组，调用System.arraycopy()方法，将原来数组中的元素复制到了新的数组中。

下面来看System.arraycopy()方法。该方法被标记了native，调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码。该函数实际上最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
        
```	 
	 同时应该注意的modcount这个变量，这个变量主要作用是针对Iterator的，当我们调用iterator()方法返回一个迭代器，之后对容器进行改变的操作，在调用迭代器进行迭代时，会报错。主要是防止并发情况下，对数据访问的不统一。
###Vector源码解析
```java
package java.util;  
 
public class Vector<E>  
    extends AbstractList<E>  
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
{  
     
    // 保存Vector中数据的数组  
    protected Object[] elementData;  
 
    // 实际数据的数量  
    protected int elementCount;  
 
    // 容量增长系数  
    protected int capacityIncrement;  
 
    // Vector的序列版本号  
    private static final long serialVersionUID = -2767605614048989439L;  
 
    // Vector构造函数。默认容量是10。  
    public Vector() {  
        this(10);  
    }  
 
    // 指定Vector容量大小的构造函数  
    public Vector(int initialCapacity) {  
        this(initialCapacity, 0);  
    }  
 
    // 指定Vector"容量大小"和"增长系数"的构造函数  
    public Vector(int initialCapacity, int capacityIncrement) {  
        super();  
        if (initialCapacity < 0)  
            throw new IllegalArgumentException("Illegal Capacity: "+  
                                               initialCapacity);  
        // 新建一个数组，数组容量是initialCapacity  
        this.elementData = new Object[initialCapacity];  
        // 设置容量增长系数  
        this.capacityIncrement = capacityIncrement;  
    }  
 
    // 指定集合的Vector构造函数。  
    public Vector(Collection<? extends E> c) {  
        // 获取“集合(c)”的数组，并将其赋值给elementData  
        elementData = c.toArray();  
        // 设置数组长度  
        elementCount = elementData.length;  
        // c.toArray might (incorrectly) not return Object[] (see 6260652)  
        if (elementData.getClass() != Object[].class)  
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);  
    }  
 
    // 将数组Vector的全部元素都拷贝到数组anArray中  
    public synchronized void copyInto(Object[] anArray) {  
        System.arraycopy(elementData, 0, anArray, 0, elementCount);  
    }  
 
    // 将当前容量值设为 =实际元素个数  
    public synchronized void trimToSize() {  
        modCount++;  
        int oldCapacity = elementData.length;  
        if (elementCount < oldCapacity) {  
            elementData = Arrays.copyOf(elementData, elementCount);  
        }  
    }  
 
    // 确认“Vector容量”的帮助函数  
    private void ensureCapacityHelper(int minCapacity) {  
        int oldCapacity = elementData.length;  
        // 当Vector的容量不足以容纳当前的全部元素，增加容量大小。  
        // 若 容量增量系数>0(即capacityIncrement>0)，则将容量增大当capacityIncrement  
        // 否则，将容量增大一倍。  
        if (minCapacity > oldCapacity) {  
            Object[] oldData = elementData;  
            int newCapacity = (capacityIncrement > 0) ?  
                (oldCapacity + capacityIncrement) : (oldCapacity * 2);  
            if (newCapacity < minCapacity) {  
                newCapacity = minCapacity;  
            }  
            elementData = Arrays.copyOf(elementData, newCapacity);  
        }  
    }  
 
    // 确定Vector的容量。  
    public synchronized void ensureCapacity(int minCapacity) {  
        // 将Vector的改变统计数+1  
        modCount++;  
        ensureCapacityHelper(minCapacity);  
    }  
 
    // 设置容量值为 newSize  
    public synchronized void setSize(int newSize) {  
        modCount++;  
        if (newSize > elementCount) {  
            // 若 "newSize 大于 Vector容量"，则调整Vector的大小。  
            ensureCapacityHelper(newSize);  
        } else {  
            // 若 "newSize 小于/等于 Vector容量"，则将newSize位置开始的元素都设置为null  
            for (int i = newSize ; i < elementCount ; i++) {  
                elementData[i] = null;  
            }  
        }  
        elementCount = newSize;  
    }  
 
    // 返回“Vector的总的容量”  
    public synchronized int capacity() {  
        return elementData.length;  
    }  
 
    // 返回“Vector的实际大小”，即Vector中元素个数  
    public synchronized int size() {  
        return elementCount;  
    }  
 
    // 判断Vector是否为空  
    public synchronized boolean isEmpty() {  
        return elementCount == 0;  
    }  
 
    // 返回“Vector中全部元素对应的Enumeration”  
    public Enumeration<E> elements() {  
        // 通过匿名类实现Enumeration  
        return new Enumeration<E>() {  
            int count = 0;  
 
            // 是否存在下一个元素  
            public boolean hasMoreElements() {  
                return count < elementCount;  
            }  
 
            // 获取下一个元素  
            public E nextElement() {  
                synchronized (Vector.this) {  
                    if (count < elementCount) {  
                        return (E)elementData[count++];  
                    }  
                }  
                throw new NoSuchElementException("Vector Enumeration");  
            }  
        };  
    }  
 
    // 返回Vector中是否包含对象(o)  
    public boolean contains(Object o) {  
        return indexOf(o, 0) >= 0;  
    }  
 
 
    // 从index位置开始向后查找元素(o)。  
    // 若找到，则返回元素的索引值；否则，返回-1  
    public synchronized int indexOf(Object o, int index) {  
        if (o == null) {  
            // 若查找元素为null，则正向找出null元素，并返回它对应的序号  
            for (int i = index ; i < elementCount ; i++)  
            if (elementData[i]==null)  
                return i;  
        } else {  
            // 若查找元素不为null，则正向找出该元素，并返回它对应的序号  
            for (int i = index ; i < elementCount ; i++)  
            if (o.equals(elementData[i]))  
                return i;  
        }  
        return -1;  
    }  
 
    // 查找并返回元素(o)在Vector中的索引值  
    public int indexOf(Object o) {  
        return indexOf(o, 0);  
    }  
 
    // 从后向前查找元素(o)。并返回元素的索引  
    public synchronized int lastIndexOf(Object o) {  
        return lastIndexOf(o, elementCount-1);  
    }  
 
    // 从后向前查找元素(o)。开始位置是从前向后的第index个数；  
    // 若找到，则返回元素的“索引值”；否则，返回-1。  
    public synchronized int lastIndexOf(Object o, int index) {  
        if (index >= elementCount)  
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);  
 
        if (o == null) {  
            // 若查找元素为null，则反向找出null元素，并返回它对应的序号  
            for (int i = index; i >= 0; i--)  
            if (elementData[i]==null)  
                return i;  
        } else {  
            // 若查找元素不为null，则反向找出该元素，并返回它对应的序号  
            for (int i = index; i >= 0; i--)  
            if (o.equals(elementData[i]))  
                return i;  
        }  
        return -1;  
    }  
 
    // 返回Vector中index位置的元素。  
    // 若index月结，则抛出异常  
    public synchronized E elementAt(int index) {  
        if (index >= elementCount) {  
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
        }  
 
        return (E)elementData[index];  
    }  
 
    // 获取Vector中的第一个元素。  
    // 若失败，则抛出异常！  
    public synchronized E firstElement() {  
        if (elementCount == 0) {  
            throw new NoSuchElementException();  
        }  
        return (E)elementData[0];  
    }  
 
    // 获取Vector中的最后一个元素。  
    // 若失败，则抛出异常！  
    public synchronized E lastElement() {  
        if (elementCount == 0) {  
            throw new NoSuchElementException();  
        }  
        return (E)elementData[elementCount - 1];  
    }  
 
    // 设置index位置的元素值为obj  
    public synchronized void setElementAt(E obj, int index) {  
        if (index >= elementCount) {  
            throw new ArrayIndexOutOfBoundsException(index + " >= " +  
                                 elementCount);  
        }  
        elementData[index] = obj;  
    }  
 
    // 删除index位置的元素  
    public synchronized void removeElementAt(int index) {  
        modCount++;  
        if (index >= elementCount) {  
            throw new ArrayIndexOutOfBoundsException(index + " >= " +  
                                 elementCount);  
        } else if (index < 0) {  
            throw new ArrayIndexOutOfBoundsException(index);  
        }  
 
        int j = elementCount - index - 1;  
        if (j > 0) {  
            System.arraycopy(elementData, index + 1, elementData, index, j);  
        }  
        elementCount--;  
        elementData[elementCount] = null; /* to let gc do its work */ 
    }  
 
    // 在index位置处插入元素(obj)  
    public synchronized void insertElementAt(E obj, int index) {  
        modCount++;  
        if (index > elementCount) {  
            throw new ArrayIndexOutOfBoundsException(index  
                                 + " > " + elementCount);  
        }  
        ensureCapacityHelper(elementCount + 1);  
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);  
        elementData[index] = obj;  
        elementCount++;  
    }  
 
    // 将“元素obj”添加到Vector末尾  
    public synchronized void addElement(E obj) {  
        modCount++;  
        ensureCapacityHelper(elementCount + 1);  
        elementData[elementCount++] = obj;  
    }  
 
    // 在Vector中查找并删除元素obj。  
    // 成功的话，返回true；否则，返回false。  
    public synchronized boolean removeElement(Object obj) {  
        modCount++;  
        int i = indexOf(obj);  
        if (i >= 0) {  
            removeElementAt(i);  
            return true;  
        }  
        return false;  
    }  
 
    // 删除Vector中的全部元素  
    public synchronized void removeAllElements() {  
        modCount++;  
        // 将Vector中的全部元素设为null  
        for (int i = 0; i < elementCount; i++)  
            elementData[i] = null;  
 
        elementCount = 0;  
    }  
 
    // 克隆函数  
    public synchronized Object clone() {  
        try {  
            Vector<E> v = (Vector<E>) super.clone();  
            // 将当前Vector的全部元素拷贝到v中  
            v.elementData = Arrays.copyOf(elementData, elementCount);  
            v.modCount = 0;  
            return v;  
        } catch (CloneNotSupportedException e) {  
            // this shouldn't happen, since we are Cloneable  
            throw new InternalError();  
        }  
    }  
 
    // 返回Object数组  
    public synchronized Object[] toArray() {  
        return Arrays.copyOf(elementData, elementCount);  
    }  
 
    // 返回Vector的模板数组。所谓模板数组，即可以将T设为任意的数据类型  
    public synchronized <T> T[] toArray(T[] a) {  
        // 若数组a的大小 < Vector的元素个数；  
        // 则新建一个T[]数组，数组大小是“Vector的元素个数”，并将“Vector”全部拷贝到新数组中  
        if (a.length < elementCount)  
            return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());  
 
        // 若数组a的大小 >= Vector的元素个数；  
        // 则将Vector的全部元素都拷贝到数组a中。  
    System.arraycopy(elementData, 0, a, 0, elementCount);  
 
        if (a.length > elementCount)  
            a[elementCount] = null;  
 
        return a;  
    }  
 
    // 获取index位置的元素  
    public synchronized E get(int index) {  
        if (index >= elementCount)  
            throw new ArrayIndexOutOfBoundsException(index);  
 
        return (E)elementData[index];  
    }  
 
    // 设置index位置的值为element。并返回index位置的原始值  
    public synchronized E set(int index, E element) {  
        if (index >= elementCount)  
            throw new ArrayIndexOutOfBoundsException(index);  
 
        Object oldValue = elementData[index];  
        elementData[index] = element;  
        return (E)oldValue;  
    }  
 
    // 将“元素e”添加到Vector最后。  
    public synchronized boolean add(E e) {  
        modCount++;  
        ensureCapacityHelper(elementCount + 1);  
        elementData[elementCount++] = e;  
        return true;  
    }  
 
    // 删除Vector中的元素o  
    public boolean remove(Object o) {  
        return removeElement(o);  
    }  
 
    // 在index位置添加元素element  
    public void add(int index, E element) {  
        insertElementAt(element, index);  
    }  
 
    // 删除index位置的元素，并返回index位置的原始值  
    public synchronized E remove(int index) {  
        modCount++;  
        if (index >= elementCount)  
            throw new ArrayIndexOutOfBoundsException(index);  
        Object oldValue = elementData[index];  
 
        int numMoved = elementCount - index - 1;  
        if (numMoved > 0)  
            System.arraycopy(elementData, index+1, elementData, index,  
                     numMoved);  
        elementData[--elementCount] = null; // Let gc do its work  
 
        return (E)oldValue;  
    }  
 
    // 清空Vector  
    public void clear() {  
        removeAllElements();  
    }  
 
    // 返回Vector是否包含集合c  
    public synchronized boolean containsAll(Collection<?> c) {  
        return super.containsAll(c);  
    }  
 
    // 将集合c添加到Vector中  
    public synchronized boolean addAll(Collection<? extends E> c) {  
        modCount++;  
        Object[] a = c.toArray();  
        int numNew = a.length;  
        ensureCapacityHelper(elementCount + numNew);  
        // 将集合c的全部元素拷贝到数组elementData中  
        System.arraycopy(a, 0, elementData, elementCount, numNew);  
        elementCount += numNew;  
        return numNew != 0;  
    }  
 
    // 删除集合c的全部元素  
    public synchronized boolean removeAll(Collection<?> c) {  
        return super.removeAll(c);  
    }  
 
    // 删除“非集合c中的元素”  
    public synchronized boolean retainAll(Collection<?> c)  {  
        return super.retainAll(c);  
    }  
 
    // 从index位置开始，将集合c添加到Vector中  
    public synchronized boolean addAll(int index, Collection<? extends E> c) {  
        modCount++;  
        if (index < 0 || index > elementCount)  
            throw new ArrayIndexOutOfBoundsException(index);  
 
        Object[] a = c.toArray();  
        int numNew = a.length;  
        ensureCapacityHelper(elementCount + numNew);  
 
        int numMoved = elementCount - index;  
        if (numMoved > 0)  
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);  
 
        System.arraycopy(a, 0, elementData, index, numNew);  
        elementCount += numNew;  
        return numNew != 0;  
    }  
 
    // 返回两个对象是否相等  
    public synchronized boolean equals(Object o) {  
        return super.equals(o);  
    }  
 
    // 计算哈希值  
    public synchronized int hashCode() {  
        return super.hashCode();  
    }  
 
    // 调用父类的toString()  
    public synchronized String toString() {  
        return super.toString();  
    }  
 
    // 获取Vector中fromIndex(包括)到toIndex(不包括)的子集  
    public synchronized List<E> subList(int fromIndex, int toIndex) {  
        return Collections.synchronizedList(super.subList(fromIndex, toIndex), this);  
    }  
 
    // 删除Vector中fromIndex到toIndex的元素  
    protected synchronized void removeRange(int fromIndex, int toIndex) {  
        modCount++;  
        int numMoved = elementCount - toIndex;  
        System.arraycopy(elementData, toIndex, elementData, fromIndex,  
                         numMoved);  
 
        // Let gc do its work  
        int newElementCount = elementCount - (toIndex-fromIndex);  
        while (elementCount != newElementCount)  
            elementData[--elementCount] = null;  
    }  
 
    // java.io.Serializable的写入函数  
    private synchronized void writeObject(java.io.ObjectOutputStream s)  
        throws java.io.IOException {  
        s.defaultWriteObject();  
    }  
}

我们可以看到Vector的许多方法添加synchronized同步语句，来保证线程安全，因此导致单线程中性能较低，而多线程情况下多用CopyOnWriteArrayList，因此Vector现在基本很少用了。

###LinkedList源码
LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。

LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。

package java.util;  
 
public class LinkedList<E>  
    extends AbstractSequentialList<E>  
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
{  
    // 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。  
    private transient Entry<E> header = new Entry<E>(null, null, null);  
 
    // LinkedList中元素个数  
    private transient int size = 0;  
 
    // 默认构造函数：创建一个空的链表  
    public LinkedList() {  
        header.next = header.previous = header;  
    }  
 
    // 包含“集合”的构造函数:创建一个包含“集合”的LinkedList  
    public LinkedList(Collection<? extends E> c) {  
        this();  
        addAll(c);  
    }  
 
    // 获取LinkedList的第一个元素  
    public E getFirst() {  
        if (size==0)  
            throw new NoSuchElementException();  
 
        // 链表的表头header中不包含数据。  
        // 这里返回header所指下一个节点所包含的数据。  
        return header.next.element;  
    }  
 
    // 获取LinkedList的最后一个元素  
    public E getLast()  {  
        if (size==0)  
            throw new NoSuchElementException();  
 
        // 由于LinkedList是双向链表；而表头header不包含数据。  
        // 因而，这里返回表头header的前一个节点所包含的数据。  
        return header.previous.element;  
    }  
 
    // 删除LinkedList的第一个元素  
    public E removeFirst() {  
        return remove(header.next);  
    }  
 
    // 删除LinkedList的最后一个元素  
    public E removeLast() {  
        return remove(header.previous);  
    }  
 
    // 将元素添加到LinkedList的起始位置  
    public void addFirst(E e) {  
        addBefore(e, header.next);  
    }  
 
    // 将元素添加到LinkedList的结束位置  
    public void addLast(E e) {  
        addBefore(e, header);  
    }  
 
    // 判断LinkedList是否包含元素(o)  
    public boolean contains(Object o) {  
        return indexOf(o) != -1;  
    }  
 
    // 返回LinkedList的大小  
    public int size() {  
        return size;  
    }  
 
    // 将元素(E)添加到LinkedList中  
    public boolean add(E e) {  
        // 将节点(节点数据是e)添加到表头(header)之前。  
        // 即，将节点添加到双向链表的末端。  
        addBefore(e, header);  
        return true;  
    }  
 
    // 从LinkedList中删除元素(o)  
    // 从链表开始查找，如存在元素(o)则删除该元素并返回true；  
    // 否则，返回false。  
    public boolean remove(Object o) {  
        if (o==null) {  
            // 若o为null的删除情况  
            for (Entry<E> e = header.next; e != header; e = e.next) {  
                if (e.element==null) {  
                    remove(e);  
                    return true;  
                }  
            }  
        } else {  
            // 若o不为null的删除情况  
            for (Entry<E> e = header.next; e != header; e = e.next) {  
                if (o.equals(e.element)) {  
                    remove(e);  
                    return true;  
                }  
            }  
        }  
        return false;  
    }  
 
    // 将“集合(c)”添加到LinkedList中。  
    // 实际上，是从双向链表的末尾开始，将“集合(c)”添加到双向链表中。  
    public boolean addAll(Collection<? extends E> c) {  
        return addAll(size, c);  
    }  
 
    // 从双向链表的index开始，将“集合(c)”添加到双向链表中。  
    public boolean addAll(int index, Collection<? extends E> c) {  
        if (index < 0 || index > size)  
            throw new IndexOutOfBoundsException("Index: "+index+  
                                                ", Size: "+size);  
        Object[] a = c.toArray();  
        // 获取集合的长度  
        int numNew = a.length;  
        if (numNew==0)  
            return false;  
        modCount++;  
 
        // 设置“当前要插入节点的后一个节点”  
        Entry<E> successor = (index==size ? header : entry(index));  
        // 设置“当前要插入节点的前一个节点”  
        Entry<E> predecessor = successor.previous;  
        // 将集合(c)全部插入双向链表中  
        for (int i=0; i<numNew; i++) {  
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);  
            predecessor.next = e;  
            predecessor = e;  
        }  
        successor.previous = predecessor;  
 
        // 调整LinkedList的实际大小  
        size += numNew;  
        return true;  
    }  
 
    // 清空双向链表  
    public void clear() {  
        Entry<E> e = header.next;  
        // 从表头开始，逐个向后遍历；对遍历到的节点执行一下操作：  
        // (01) 设置前一个节点为null   
        // (02) 设置当前节点的内容为null   
        // (03) 设置后一个节点为“新的当前节点”  
        while (e != header) {  
            Entry<E> next = e.next;  
            e.next = e.previous = null;  
            e.element = null;  
            e = next;  
        }  
        header.next = header.previous = header;  
        // 设置大小为0  
        size = 0;  
        modCount++;  
    }  
 
    // 返回LinkedList指定位置的元素  
    public E get(int index) {  
        return entry(index).element;  
    }  
 
    // 设置index位置对应的节点的值为element  
    public E set(int index, E element) {  
        Entry<E> e = entry(index);  
        E oldVal = e.element;  
        e.element = element;  
        return oldVal;  
    }  
   
    // 在index前添加节点，且节点的值为element  
    public void add(int index, E element) {  
        addBefore(element, (index==size ? header : entry(index)));  
    }  
 
    // 删除index位置的节点  
    public E remove(int index) {  
        return remove(entry(index));  
    }  
 
    // 获取双向链表中指定位置的节点  
    private Entry<E> entry(int index) {  
        if (index < 0 || index >= size)  
            throw new IndexOutOfBoundsException("Index: "+index+  
                                                ", Size: "+size);  
        Entry<E> e = header;  
        // 获取index处的节点。  
        // 若index < 双向链表长度的1/2,则从前先后查找;  
        // 否则，从后向前查找。  
        if (index < (size >> 1)) {  
            for (int i = 0; i <= index; i++)  
                e = e.next;  
        } else {  
            for (int i = size; i > index; i--)  
                e = e.previous;  
        }  
        return e;  
    }  
 
    // 从前向后查找，返回“值为对象(o)的节点对应的索引”  
    // 不存在就返回-1  
    public int indexOf(Object o) {  
        int index = 0;  
        if (o==null) {  
            for (Entry e = header.next; e != header; e = e.next) {  
                if (e.element==null)  
                    return index;  
                index++;  
            }  
        } else {  
            for (Entry e = header.next; e != header; e = e.next) {  
                if (o.equals(e.element))  
                    return index;  
                index++;  
            }  
        }  
        return -1;  
    }  
 
    // 从后向前查找，返回“值为对象(o)的节点对应的索引”  
    // 不存在就返回-1  
    public int lastIndexOf(Object o) {  
        int index = size;  
        if (o==null) {  
            for (Entry e = header.previous; e != header; e = e.previous) {  
                index--;  
                if (e.element==null)  
                    return index;  
            }  
        } else {  
            for (Entry e = header.previous; e != header; e = e.previous) {  
                index--;  
                if (o.equals(e.element))  
                    return index;  
            }  
        }  
        return -1;  
    }  
 
    // 返回第一个节点  
    // 若LinkedList的大小为0,则返回null  
    public E peek() {  
        if (size==0)  
            return null;  
        return getFirst();  
    }  
 
    // 返回第一个节点  
    // 若LinkedList的大小为0,则抛出异常  
    public E element() {  
        return getFirst();  
    }  
 
    // 删除并返回第一个节点  
    // 若LinkedList的大小为0,则返回null  
    public E poll() {  
        if (size==0)  
            return null;  
        return removeFirst();  
    }  
 
    // 将e添加双向链表末尾  
    public boolean offer(E e) {  
        return add(e);  
    }  
 
    // 将e添加双向链表开头  
    public boolean offerFirst(E e) {  
        addFirst(e);  
        return true;  
    }  
 
    // 将e添加双向链表末尾  
    public boolean offerLast(E e) {  
        addLast(e);  
        return true;  
    }  
 
    // 返回第一个节点  
    // 若LinkedList的大小为0,则返回null  
    public E peekFirst() {  
        if (size==0)  
            return null;  
        return getFirst();  
    }  
 
    // 返回最后一个节点  
    // 若LinkedList的大小为0,则返回null  
    public E peekLast() {  
        if (size==0)  
            return null;  
        return getLast();  
    }  
 
    // 删除并返回第一个节点  
    // 若LinkedList的大小为0,则返回null  
    public E pollFirst() {  
        if (size==0)  
            return null;  
        return removeFirst();  
    }  
 
    // 删除并返回最后一个节点  
    // 若LinkedList的大小为0,则返回null  
    public E pollLast() {  
        if (size==0)  
            return null;  
        return removeLast();  
    }  
 
    // 将e插入到双向链表开头  
    public void push(E e) {  
        addFirst(e);  
    }  
 
    // 删除并返回第一个节点  
    public E pop() {  
        return removeFirst();  
    }  
 
    // 从LinkedList开始向后查找，删除第一个值为元素(o)的节点  
    // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点  
    public boolean removeFirstOccurrence(Object o) {  
        return remove(o);  
    }  
 
    // 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点  
    // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点  
    public boolean removeLastOccurrence(Object o) {  
        if (o==null) {  
            for (Entry<E> e = header.previous; e != header; e = e.previous) {  
                if (e.element==null) {  
                    remove(e);  
                    return true;  
                }  
            }  
        } else {  
            for (Entry<E> e = header.previous; e != header; e = e.previous) {  
                if (o.equals(e.element)) {  
                    remove(e);  
                    return true;  
                }  
            }  
        }  
        return false;  
    }  
 
    // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)  
    public ListIterator<E> listIterator(int index) {  
        return new ListItr(index);  
    }  
 
    // List迭代器  
    private class ListItr implements ListIterator<E> {  
        // 上一次返回的节点  
        private Entry<E> lastReturned = header;  
        // 下一个节点  
        private Entry<E> next;  
        // 下一个节点对应的索引值  
        private int nextIndex;  
        // 期望的改变计数。用来实现fail-fast机制。  
        private int expectedModCount = modCount;  
 
        // 构造函数。  
        // 从index位置开始进行迭代  
        ListItr(int index) {  
            // index的有效性处理  
            if (index < 0 || index > size)  
                throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);  
            // 若 “index 小于 ‘双向链表长度的一半’”，则从第一个元素开始往后查找；  
            // 否则，从最后一个元素往前查找。  
            if (index < (size >> 1)) {  
                next = header.next;  
                for (nextIndex=0; nextIndex<index; nextIndex++)  
                    next = next.next;  
            } else {  
                next = header;  
                for (nextIndex=size; nextIndex>index; nextIndex--)  
                    next = next.previous;  
            }  
        }  
 
        // 是否存在下一个元素  
        public boolean hasNext() {  
            // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。  
            return nextIndex != size;  
        }  
 
        // 获取下一个元素  
        public E next() {  
            checkForComodification();  
            if (nextIndex == size)  
                throw new NoSuchElementException();  
 
            lastReturned = next;  
            // next指向链表的下一个元素  
            next = next.next;  
            nextIndex++;  
            return lastReturned.element;  
        }  
 
        // 是否存在上一个元素  
        public boolean hasPrevious() {  
            // 通过元素索引是否等于0，来判断是否达到开头。  
            return nextIndex != 0;  
        }  
 
        // 获取上一个元素  
        public E previous() {  
            if (nextIndex == 0)  
            throw new NoSuchElementException();  
 
            // next指向链表的上一个元素  
            lastReturned = next = next.previous;  
            nextIndex--;  
            checkForComodification();  
            return lastReturned.element;  
        }  
 
        // 获取下一个元素的索引  
        public int nextIndex() {  
            return nextIndex;  
        }  
 
        // 获取上一个元素的索引  
        public int previousIndex() {  
            return nextIndex-1;  
        }  
 
        // 删除当前元素。  
        // 删除双向链表中的当前节点  
        public void remove() {  
            checkForComodification();  
            Entry<E> lastNext = lastReturned.next;  
            try {  
                LinkedList.this.remove(lastReturned);  
            } catch (NoSuchElementException e) {  
                throw new IllegalStateException();  
            }  
            if (next==lastReturned)  
                next = lastNext;  
            else 
                nextIndex--;  
            lastReturned = header;  
            expectedModCount++;  
        }  
 
        // 设置当前节点为e  
        public void set(E e) {  
            if (lastReturned == header)  
                throw new IllegalStateException();  
            checkForComodification();  
            lastReturned.element = e;  
        }  
 
        // 将e添加到当前节点的前面  
        public void add(E e) {  
            checkForComodification();  
            lastReturned = header;  
            addBefore(e, next);  
            nextIndex++;  
            expectedModCount++;  
        }  
 
        // 判断 “modCount和expectedModCount是否相等”，依次来实现fail-fast机制。  
        final void checkForComodification() {  
            if (modCount != expectedModCount)  
            throw new ConcurrentModificationException();  
        }  
    }  
 
    // 双向链表的节点所对应的数据结构。  
    // 包含3部分：上一节点，下一节点，当前节点值。  
    private static class Entry<E> {  
        // 当前节点所包含的值  
        E element;  
        // 下一个节点  
        Entry<E> next;  
        // 上一个节点  
        Entry<E> previous;  
 
        /**  
         * 链表节点的构造函数。  
         * 参数说明：  
         *   element  —— 节点所包含的数据  
         *   next      —— 下一个节点  
         *   previous —— 上一个节点  
         */ 
        Entry(E element, Entry<E> next, Entry<E> previous) {  
            this.element = element;  
            this.next = next;  
            this.previous = previous;  
        }  
    }  
 
    // 将节点(节点数据是e)添加到entry节点之前。  
    private Entry<E> addBefore(E e, Entry<E> entry) {  
        // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e  
        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);  
        newEntry.previous.next = newEntry;  
        newEntry.next.previous = newEntry;  
        // 修改LinkedList大小  
        size++;  
        // 修改LinkedList的修改统计数：用来实现fail-fast机制。  
        modCount++;  
        return newEntry;  
    }  
 
    // 将节点从链表中删除  
    private E remove(Entry<E> e) {  
        if (e == header)  
            throw new NoSuchElementException();  
 
        E result = e.element;  
        e.previous.next = e.next;  
        e.next.previous = e.previous;  
        e.next = e.previous = null;  
        e.element = null;  
        size--;  
        modCount++;  
        return result;  
    }  
 
    // 反向迭代器  
    public Iterator<E> descendingIterator() {  
        return new DescendingIterator();  
    }  
 
    // 反向迭代器实现类。  
    private class DescendingIterator implements Iterator {  
        final ListItr itr = new ListItr(size());  
        // 反向迭代器是否下一个元素。  
        // 实际上是判断双向链表的当前节点是否达到开头  
        public boolean hasNext() {  
            return itr.hasPrevious();  
        }  
        // 反向迭代器获取下一个元素。  
        // 实际上是获取双向链表的前一个节点  
        public E next() {  
            return itr.previous();  
        }  
        // 删除当前节点  
        public void remove() {  
            itr.remove();  
        }  
    }  
 
 
    // 返回LinkedList的Object[]数组  
    public Object[] toArray() {  
    // 新建Object[]数组  
    Object[] result = new Object[size];  
        int i = 0;  
        // 将链表中所有节点的数据都添加到Object[]数组中  
        for (Entry<E> e = header.next; e != header; e = e.next)  
            result[i++] = e.element;  
    return result;  
    }  
 
    // 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型  
    public <T> T[] toArray(T[] a) {  
        // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)  
        // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。  
        if (a.length < size)  
            a = (T[])java.lang.reflect.Array.newInstance(  
                                a.getClass().getComponentType(), size);  
        // 将链表中所有节点的数据都添加到数组a中  
        int i = 0;  
        Object[] result = a;  
        for (Entry<E> e = header.next; e != header; e = e.next)  
            result[i++] = e.element;  
 
        if (a.length > size)  
            a[size] = null;  
 
        return a;  
    }  
 
 
    // 克隆函数。返回LinkedList的克隆对象。  
    public Object clone() {  
        LinkedList<E> clone = null;  
        // 克隆一个LinkedList克隆对象  
        try {  
            clone = (LinkedList<E>) super.clone();  
        } catch (CloneNotSupportedException e) {  
            throw new InternalError();  
        }  
 
        // 新建LinkedList表头节点  
        clone.header = new Entry<E>(null, null, null);  
        clone.header.next = clone.header.previous = clone.header;  
        clone.size = 0;  
        clone.modCount = 0;  
 
        // 将链表中所有节点的数据都添加到克隆对象中  
        for (Entry<E> e = header.next; e != header; e = e.next)  
            clone.add(e.element);  
 
        return clone;  
    }  
 
    // java.io.Serializable的写入函数  
    // 将LinkedList的“容量，所有的元素值”都写入到输出流中  
    private void writeObject(java.io.ObjectOutputStream s)  
        throws java.io.IOException {  
        // Write out any hidden serialization magic  
        s.defaultWriteObject();  
 
        // 写入“容量”  
        s.writeInt(size);  
 
        // 将链表中所有节点的数据都写入到输出流中  
        for (Entry e = header.next; e != header; e = e.next)  
            s.writeObject(e.element);  
    }  
 
    // java.io.Serializable的读取函数：根据写入方式反向读出  
    // 先将LinkedList的“容量”读出，然后将“所有的元素值”读出  
    private void readObject(java.io.ObjectInputStream s)  
        throws java.io.IOException, ClassNotFoundException {  
        // Read in any hidden serialization magic  
        s.defaultReadObject();  
 
        // 从输入流中读取“容量”  
        int size = s.readInt();  
 
        // 新建链表表头节点  
        header = new Entry<E>(null, null, null);  
        header.next = header.previous = header;  
 
        // 从输入流中将“所有的元素值”并逐个添加到链表中  
        for (int i=0; i<size; i++)  
            addBefore((E)s.readObject(), header);  
    }  
 
}

Map

HashMap和HashTable

HashMap和HashTable的不同点

1. hashMap去掉了HashTable的contains方法，但是加上了containsValue()和containsKey()方法。
2. hashTable同步的，而HashMap是非同步的，效率上比hashTable要高。
3. hashMap允许NULL，而hashTable不允许。

影响Hashtable的性能有初始容量和加载因子。加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度（默认0.75）。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。

	package java.util;  
import java.io.*;  
 
public class HashMap<K,V>  
    extends AbstractMap<K,V>  
    implements Map<K,V>, Cloneable, Serializable  
{  
 
    // 默认的初始容量（容量为HashMap中槽的数目）是16，且实际容量必须是2的整数次幂。  
    static final int DEFAULT_INITIAL_CAPACITY = 16;  
 
    // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）  
    static final int MAXIMUM_CAPACITY = 1 << 30;  
 
    // 默认加载因子为0.75 
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  
 
    // 存储数据的Entry数组，长度是2的幂。  
    // HashMap采用链表法解决冲突，每一个Entry本质上是一个单向链表  
    transient Entry[] table;  
 
    // HashMap的底层数组中已用槽的数量  
    transient int size;  
 
    // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）  
    int threshold;  
 
    // 加载因子实际大小  
    final float loadFactor;  
 
    // HashMap被改变的次数  
    transient volatile int modCount;  
 
    // 指定“容量大小”和“加载因子”的构造函数  
    public HashMap(int initialCapacity, float loadFactor) {  
        if (initialCapacity < 0)  
            throw new IllegalArgumentException("Illegal initial capacity: " +  
                                               initialCapacity);  
        // HashMap的最大容量只能是MAXIMUM_CAPACITY  
        if (initialCapacity > MAXIMUM_CAPACITY)  
            initialCapacity = MAXIMUM_CAPACITY;  
		//加载因此不能小于0
        if (loadFactor <= 0 || Float.isNaN(loadFactor))  
            throw new IllegalArgumentException("Illegal load factor: " +  
                                               loadFactor);  
 
        // 找出“大于initialCapacity”的最小的2的幂  
        int capacity = 1;  
        while (capacity < initialCapacity)  
            capacity <<= 1;  
 
        // 设置“加载因子”  
        this.loadFactor = loadFactor;  
        // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。  
        threshold = (int)(capacity * loadFactor);  
        // 创建Entry数组，用来保存数据  
        table = new Entry[capacity];  
        init();  
    }  
 
 
    // 指定“容量大小”的构造函数  
    public HashMap(int initialCapacity) {  
        this(initialCapacity, DEFAULT_LOAD_FACTOR);  
    }  
 
    // 默认构造函数。  
    public HashMap() {  
        // 设置“加载因子”为默认加载因子0.75  
        this.loadFactor = DEFAULT_LOAD_FACTOR;  
        // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。  
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);  
        // 创建Entry数组，用来保存数据  
        table = new Entry[DEFAULT_INITIAL_CAPACITY];  
        init();  
    }  
 
    // 包含“子Map”的构造函数  
    public HashMap(Map<? extends K, ? extends V> m) {  
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,  
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  
        // 将m中的全部元素逐个添加到HashMap中  
        putAllForCreate(m);  
    }  
 
    //求hash值的方法，重新计算hash值
    static int hash(int h) {  
        h ^= (h >>> 20) ^ (h >>> 12);  
        return h ^ (h >>> 7) ^ (h >>> 4);  
    }  
 
    // 返回h在数组中的索引值，这里用&代替取模，旨在提升效率 
    // h & (length-1)保证返回值的小于length  
    static int indexFor(int h, int length) {  
        return h & (length-1);  
    }  
 
    public int size() {  
        return size;  
    }  
 
    public boolean isEmpty() {  
        return size == 0;  
    }  
 
    // 获取key对应的value  
    public V get(Object key) {  
        if (key == null)  
            return getForNullKey();  
        // 获取key的hash值  
        int hash = hash(key.hashCode());  
        // 在“该hash值对应的链表”上查找“键值等于key”的元素  
        for (Entry<K,V> e = table[indexFor(hash, table.length)];  
             e != null;  
             e = e.next) {  
            Object k;  
			//判断key是否相同
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
                return e.value;  
        }
		//没找到则返回null
        return null;  
    }  
 
    // 获取“key为null”的元素的值  
    // HashMap将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！  
    private V getForNullKey() {  
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
            if (e.key == null)  
                return e.value;  
        }  
        return null;  
    }  
 
    // HashMap是否包含key  
    public boolean containsKey(Object key) {  
        return getEntry(key) != null;  
    }  
 
    // 返回“键为key”的键值对  
    final Entry<K,V> getEntry(Object key) {  
        // 获取哈希值  
        // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值  
        int hash = (key == null) ? 0 : hash(key.hashCode());  
        // 在“该hash值对应的链表”上查找“键值等于key”的元素  
        for (Entry<K,V> e = table[indexFor(hash, table.length)];  
             e != null;  
             e = e.next) {  
            Object k;  
            if (e.hash == hash &&  
                ((k = e.key) == key || (key != null && key.equals(k))))  
                return e;  
        }  
        return null;  
    }  
 
    // 将“key-value”添加到HashMap中  
    public V put(K key, V value) {  
        // 若“key为null”，则将该键值对添加到table[0]中。  
        if (key == null)  
            return putForNullKey(value);  
        // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
 
        // 若“该key”对应的键值对不存在，则将“key-value”添加到table中  
        modCount++;
		//将key-value添加到table[i]处
        addEntry(hash, key, value, i);  
        return null;  
    }  
 
    // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置  
    private V putForNullKey(V value) {  
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
            if (e.key == null) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        // 如果没有存在key为null的键值对，则直接题阿见到table[0]处!  
        modCount++;  
        addEntry(0, null, value, 0);  
        return null;  
    }  
 
    // 创建HashMap对应的“添加方法”，  
    // 它和put()不同。putForCreate()是内部方法，它被构造函数等调用，用来创建HashMap  
    // 而put()是对外提供的往HashMap中添加元素的方法。  
    private void putForCreate(K key, V value) {  
        int hash = (key == null) ? 0 : hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
 
        // 若该HashMap表中存在“键值等于key”的元素，则替换该元素的value值  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            if (e.hash == hash &&  
                ((k = e.key) == key || (key != null && key.equals(k)))) {  
                e.value = value;  
                return;  
            }  
        }  
 
        // 若该HashMap表中不存在“键值等于key”的元素，则将该key-value添加到HashMap中  
        createEntry(hash, key, value, i);  
    }  
 
    // 将“m”中的全部元素都添加到HashMap中。  
    // 该方法被内部的构造HashMap的方法所调用。  
    private void putAllForCreate(Map<? extends K, ? extends V> m) {  
        // 利用迭代器将元素逐个添加到HashMap中  
        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {  
            Map.Entry<? extends K, ? extends V> e = i.next();  
            putForCreate(e.getKey(), e.getValue());  
        }  
    }  
 
    // 重新调整HashMap的大小，newCapacity是调整后的容量  
    void resize(int newCapacity) {  
        Entry[] oldTable = table;  
        int oldCapacity = oldTable.length; 
		//如果就容量已经达到了最大值，则不能再扩容，直接返回
        if (oldCapacity == MAXIMUM_CAPACITY) {  
            threshold = Integer.MAX_VALUE;  
            return;  
        }  
 
        // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中，  
        // 然后，将“新HashMap”赋值给“旧HashMap”。  
        Entry[] newTable = new Entry[newCapacity];  
        transfer(newTable);  
        table = newTable;  
        threshold = (int)(newCapacity * loadFactor);  
    }  
 
    // 将HashMap中的全部元素都添加到newTable中  
    void transfer(Entry[] newTable) {  
        Entry[] src = table;  
        int newCapacity = newTable.length;  
        for (int j = 0; j < src.length; j++) {  
            Entry<K,V> e = src[j];  
            if (e != null) {  
                src[j] = null;  
                do {  
                    Entry<K,V> next = e.next;  
                    int i = indexFor(e.hash, newCapacity);  
                    e.next = newTable[i];  
                    newTable[i] = e;  
                    e = next;  
                } while (e != null);  
            }  
        }  
    }  
 
    // 将"m"的全部元素都添加到HashMap中  
    public void putAll(Map<? extends K, ? extends V> m) {  
        // 有效性判断  
        int numKeysToBeAdded = m.size();  
        if (numKeysToBeAdded == 0)  
            return;  
 
        // 计算容量是否足够，  
        // 若“当前阀值容量 < 需要的容量”，则将容量x2。  
        if (numKeysToBeAdded > threshold) {  
            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);  
            if (targetCapacity > MAXIMUM_CAPACITY)  
                targetCapacity = MAXIMUM_CAPACITY;  
            int newCapacity = table.length;  
            while (newCapacity < targetCapacity)  
                newCapacity <<= 1;  
            if (newCapacity > table.length)  
                resize(newCapacity);  
        }  
 
        // 通过迭代器，将“m”中的元素逐个添加到HashMap中。  
        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {  
            Map.Entry<? extends K, ? extends V> e = i.next();  
            put(e.getKey(), e.getValue());  
        }  
    }  
 
    // 删除“键为key”元素  
    public V remove(Object key) {  
        Entry<K,V> e = removeEntryForKey(key);  
        return (e == null ? null : e.value);  
    }  
 
    // 删除“键为key”的元素  
    final Entry<K,V> removeEntryForKey(Object key) {  
        // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算  
        int hash = (key == null) ? 0 : hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        Entry<K,V> prev = table[i];  
        Entry<K,V> e = prev;  
 
        // 删除链表中“键为key”的元素  
        // 本质是“删除单向链表中的节点”  
        while (e != null) {  
            Entry<K,V> next = e.next;  
            Object k;  
            if (e.hash == hash &&  
                ((k = e.key) == key || (key != null && key.equals(k)))) {  
                modCount++;  
                size--;  
                if (prev == e)  
                    table[i] = next;  
                else 
                    prev.next = next;  
                e.recordRemoval(this);  
                return e;  
            }  
            prev = e;  
            e = next;  
        }  
 
        return e;  
    }  
 
    // 删除“键值对”  
    final Entry<K,V> removeMapping(Object o) {  
        if (!(o instanceof Map.Entry))  
            return null;  
 
        Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  
        Object key = entry.getKey();  
        int hash = (key == null) ? 0 : hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        Entry<K,V> prev = table[i];  
        Entry<K,V> e = prev;  
 
        // 删除链表中的“键值对e”  
        // 本质是“删除单向链表中的节点”  
        while (e != null) {  
            Entry<K,V> next = e.next;  
            if (e.hash == hash && e.equals(entry)) {  
                modCount++;  
                size--;  
                if (prev == e)  
                    table[i] = next;  
                else 
                    prev.next = next;  
                e.recordRemoval(this);  
                return e;  
            }  
            prev = e;  
            e = next;  
        }  
 
        return e;  
    }  
 
    // 清空HashMap，将所有的元素设为null  
    public void clear() {  
        modCount++;  
        Entry[] tab = table;  
        for (int i = 0; i < tab.length; i++)  
            tab[i] = null;  
        size = 0;  
    }  
 
    // 是否包含“值为value”的元素  
    public boolean containsValue(Object value) {  
    // 若“value为null”，则调用containsNullValue()查找  
    if (value == null)  
            return containsNullValue();  
 
    // 若“value不为null”，则查找HashMap中是否有值为value的节点。  
    Entry[] tab = table;  
        for (int i = 0; i < tab.length ; i++)  
            for (Entry e = tab[i] ; e != null ; e = e.next)  
                if (value.equals(e.value))  
                    return true;  
    return false;  
    }  
 
    // 是否包含null值  
    private boolean containsNullValue() {  
    Entry[] tab = table;  
        for (int i = 0; i < tab.length ; i++)  
            for (Entry e = tab[i] ; e != null ; e = e.next)  
                if (e.value == null)  
                    return true;  
    return false;  
    }  
 
    // 克隆一个HashMap，并返回Object对象  
    public Object clone() {  
        HashMap<K,V> result = null;  
        try {  
            result = (HashMap<K,V>)super.clone();  
        } catch (CloneNotSupportedException e) {  
            // assert false;  
        }  
        result.table = new Entry[table.length];  
        result.entrySet = null;  
        result.modCount = 0;  
        result.size = 0;  
        result.init();  
        // 调用putAllForCreate()将全部元素添加到HashMap中  
        result.putAllForCreate(this);  
 
        return result;  
    }  
 
    // Entry是单向链表。  
    // 它是 “HashMap链式存储法”对应的链表。  
    // 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数  
    static class Entry<K,V> implements Map.Entry<K,V> {  
        final K key;  
        V value;  
        // 指向下一个节点  
        Entry<K,V> next;  
        final int hash;  
 
        // 构造函数。  
        // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"  
        Entry(int h, K k, V v, Entry<K,V> n) {  
            value = v;  
            next = n;  
            key = k;  
            hash = h;  
        }  
 
        public final K getKey() {  
            return key;  
        }  
 
        public final V getValue() {  
            return value;  
        }  
 
        public final V setValue(V newValue) {  
            V oldValue = value;  
            value = newValue;  
            return oldValue;  
        }  
 
        // 判断两个Entry是否相等  
        // 若两个Entry的“key”和“value”都相等，则返回true。  
        // 否则，返回false  
        public final boolean equals(Object o) {  
            if (!(o instanceof Map.Entry))  
                return false;  
            Map.Entry e = (Map.Entry)o;  
            Object k1 = getKey();  
            Object k2 = e.getKey();  
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
                Object v1 = getValue();  
                Object v2 = e.getValue();  
                if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                    return true;  
            }  
            return false;  
        }  
 
        // 实现hashCode()  
        public final int hashCode() {  
            return (key==null   ? 0 : key.hashCode()) ^  
                   (value==null ? 0 : value.hashCode());  
        }  
 
        public final String toString() {  
            return getKey() + "=" + getValue();  
        }  
 
        // 当向HashMap中添加元素时，绘调用recordAccess()。  
        // 这里不做任何处理  
        void recordAccess(HashMap<K,V> m) {  
        }  
 
        // 当从HashMap中删除元素时，绘调用recordRemoval()。  
        // 这里不做任何处理  
        void recordRemoval(HashMap<K,V> m) {  
        }  
    }  
 
    // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。  
    void addEntry(int hash, K key, V value, int bucketIndex) {  
        // 保存“bucketIndex”位置的值到“e”中  
        Entry<K,V> e = table[bucketIndex];  
        // 设置“bucketIndex”位置的元素为“新Entry”，  
        // 设置“e”为“新Entry的下一个节点”  
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
        // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小  
        if (size++ >= threshold)  
            resize(2 * table.length);  
    }  
 
    // 创建Entry。将“key-value”插入指定位置。  
    void createEntry(int hash, K key, V value, int bucketIndex) {  
        // 保存“bucketIndex”位置的值到“e”中  
        Entry<K,V> e = table[bucketIndex];  
        // 设置“bucketIndex”位置的元素为“新Entry”，  
        // 设置“e”为“新Entry的下一个节点”  
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
        size++;  
    }  
 
    // HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。  
    // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。  
    private abstract class HashIterator<E> implements Iterator<E> {  
        // 下一个元素  
        Entry<K,V> next;  
        // expectedModCount用于实现fast-fail机制。  
        int expectedModCount;  
        // 当前索引  
        int index;  
        // 当前元素  
        Entry<K,V> current;  
 
        HashIterator() {  
            expectedModCount = modCount;  
            if (size > 0) { // advance to first entry  
                Entry[] t = table;  
                // 将next指向table中第一个不为null的元素。  
                // 这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。  
                while (index < t.length && (next = t[index++]) == null)  
                    ;  
            }  
        }  
 
        public final boolean hasNext() {  
            return next != null;  
        }  
 
        // 获取下一个元素  
        final Entry<K,V> nextEntry() {  
            if (modCount != expectedModCount)  
                throw new ConcurrentModificationException();  
            Entry<K,V> e = next;  
            if (e == null)  
                throw new NoSuchElementException();  
 
            // 注意！！！  
            // 一个Entry就是一个单向链表  
            // 若该Entry的下一个节点不为空，就将next指向下一个节点;  
            // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。  
            if ((next = e.next) == null) {  
                Entry[] t = table;  
                while (index < t.length && (next = t[index++]) == null)  
                    ;  
            }  
            current = e;  
            return e;  
        }  
 
        // 删除当前元素  
        public void remove() {  
            if (current == null)  
                throw new IllegalStateException();  
            if (modCount != expectedModCount)  
                throw new ConcurrentModificationException();  
            Object k = current.key;  
            current = null;  
            HashMap.this.removeEntryForKey(k);  
            expectedModCount = modCount;  
        }  
 
    }  
 
    // value的迭代器  
    private final class ValueIterator extends HashIterator<V> {  
        public V next() {  
            return nextEntry().value;  
        }  
    }  
 
    // key的迭代器  
    private final class KeyIterator extends HashIterator<K> {  
        public K next() {  
            return nextEntry().getKey();  
        }  
    }  
 
    // Entry的迭代器  
    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {  
        public Map.Entry<K,V> next() {  
            return nextEntry();  
        }  
    }  
 
    // 返回一个“key迭代器”  
    Iterator<K> newKeyIterator()   {  
        return new KeyIterator();  
    }  
    // 返回一个“value迭代器”  
    Iterator<V> newValueIterator()   {  
        return new ValueIterator();  
    }  
    // 返回一个“entry迭代器”  
    Iterator<Map.Entry<K,V>> newEntryIterator()   {  
        return new EntryIterator();  
    }  
 
    // HashMap的Entry对应的集合  
    private transient Set<Map.Entry<K,V>> entrySet = null;  
 
    // 返回“key的集合”，实际上返回一个“KeySet对象”  
    public Set<K> keySet() {  
        Set<K> ks = keySet;  
        return (ks != null ? ks : (keySet = new KeySet()));  
    }  
 
    // Key对应的集合  
    // KeySet继承于AbstractSet，说明该集合中没有重复的Key。  
    private final class KeySet extends AbstractSet<K> {  
        public Iterator<K> iterator() {  
            return newKeyIterator();  
        }  
        public int size() {  
            return size;  
        }  
        public boolean contains(Object o) {  
            return containsKey(o);  
        }  
        public boolean remove(Object o) {  
            return HashMap.this.removeEntryForKey(o) != null;  
        }  
        public void clear() {  
            HashMap.this.clear();  
        }  
    }  
 
    // 返回“value集合”，实际上返回的是一个Values对象  
    public Collection<V> values() {  
        Collection<V> vs = values;  
        return (vs != null ? vs : (values = new Values()));  
    }  
 
    // “value集合”  
    // Values继承于AbstractCollection，不同于“KeySet继承于AbstractSet”，  
    // Values中的元素能够重复。因为不同的key可以指向相同的value。  
    private final class Values extends AbstractCollection<V> {  
        public Iterator<V> iterator() {  
            return newValueIterator();  
        }  
        public int size() {  
            return size;  
        }  
        public boolean contains(Object o) {  
            return containsValue(o);  
        }  
        public void clear() {  
            HashMap.this.clear();  
        }  
    }  
 
    // 返回“HashMap的Entry集合”  
    public Set<Map.Entry<K,V>> entrySet() {  
        return entrySet0();  
    }  
 
    // 返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象  
    private Set<Map.Entry<K,V>> entrySet0() {  
        Set<Map.Entry<K,V>> es = entrySet;  
        return es != null ? es : (entrySet = new EntrySet());  
    }  
 
    // EntrySet对应的集合  
    // EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。  
    private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {  
        public Iterator<Map.Entry<K,V>> iterator() {  
            return newEntryIterator();  
        }  
        public boolean contains(Object o) {  
            if (!(o instanceof Map.Entry))  
                return false;  
            Map.Entry<K,V> e = (Map.Entry<K,V>) o;  
            Entry<K,V> candidate = getEntry(e.getKey());  
            return candidate != null && candidate.equals(e);  
        }  
        public boolean remove(Object o) {  
            return removeMapping(o) != null;  
        }  
        public int size() {  
            return size;  
        }  
        public void clear() {  
            HashMap.this.clear();  
        }  
    }  
 
    // java.io.Serializable的写入函数  
    // 将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中  
    private void writeObject(java.io.ObjectOutputStream s)  
        throws IOException  
    {  
        Iterator<Map.Entry<K,V>> i =  
            (size > 0) ? entrySet0().iterator() : null;  
 
        // Write out the threshold, loadfactor, and any hidden stuff  
        s.defaultWriteObject();  
 
        // Write out number of buckets  
        s.writeInt(table.length);  
 
        // Write out size (number of Mappings)  
        s.writeInt(size);  
 
        // Write out keys and values (alternating)  
        if (i != null) {  
            while (i.hasNext()) {  
            Map.Entry<K,V> e = i.next();  
            s.writeObject(e.getKey());  
            s.writeObject(e.getValue());  
            }  
        }  
    }  
 
 
    private static final long serialVersionUID = 362498820763181265L;  
 
    // java.io.Serializable的读取函数：根据写入方式读出  
    // 将HashMap的“总的容量，实际容量，所有的Entry”依次读出  
    private void readObject(java.io.ObjectInputStream s)  
         throws IOException, ClassNotFoundException  
    {  
        // Read in the threshold, loadfactor, and any hidden stuff  
        s.defaultReadObject();  
 
        // Read in number of buckets and allocate the bucket array;  
        int numBuckets = s.readInt();  
        table = new Entry[numBuckets];  
 
        init();  // Give subclass a chance to do its thing.  
 
        // Read in size (number of Mappings)  
        int size = s.readInt();  
 
        // Read the keys and values, and put the mappings in the HashMap  
        for (int i=0; i<size; i++) {  
            K key = (K) s.readObject();  
            V value = (V) s.readObject();  
            putForCreate(key, value);  
        }  
    }  
 
    // 返回“HashMap总的容量”  
    int   capacity()     { return table.length; }  
    // 返回“HashMap的加载因子”  
    float loadFactor()   { return loadFactor;   }  
}

• HashMap共有四个构造方法。构造方法中提到了两个很重要的参数：初始容量和加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中槽的数量（即哈希数组的长度），初始容量是创建哈希表时的容量（从构造函数中可以看出，如果不指明，则默认为16），加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 resize 操作（即扩容）。

• 下面说下加载因子，如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。

• 另外，无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方

• HashMap中key和value都允许为null。

  要重点分析下HashMap中用的最多的两个方法put和get。先从比较简单的get方法着手，源码如下：

// 获取key对应的value    
public V get(Object key) {    
    if (key == null)    
        return getForNullKey();    
    // 获取key的hash值    
    int hash = hash(key.hashCode());    
    // 在“该hash值对应的链表”上查找“键值等于key”的元素    
    for (Entry<K,V> e = table[indexFor(hash, table.length)];    
         e != null;    
         e = e.next) {    
        Object k;    
/判断key是否相同  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))    
            return e.value;    
    }  
没找到则返回null  
    return null;    
}    
  
// 获取“key为null”的元素的值    
// HashMap将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！    
private V getForNullKey() {    
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
        if (e.key == null)    
            return e.value;    
    }    
    return null;    
}

• 首先，如果key为null，则直接从哈希表的第一个位置table[0]对应的链表上查找。记住，key为null的键值对永远都放在以table[0]为头结点的链表中，当然不一定是存放在头结点table[0]中。

• 如果key不为null，则先求的key的hash值，根据hash值找到在table中的索引，在该索引对应的单链表中查找是否有键值对的key与目标key相等，有就返回对应的value，没有则返回null。

put方法稍微复杂些，代码如下：

  // 将“key-value”添加到HashMap中    
  public V put(K key, V value) {    
      // 若“key为null”，则将该键值对添加到table[0]中。    
      if (key == null)    
          return putForNullKey(value);    
      // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。    
      int hash = hash(key.hashCode());    
      int i = indexFor(hash, table.length);    
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
          Object k;    
          // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！    
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {    
              V oldValue = e.value;    
              e.value = value;    
              e.recordAccess(this);    
              return oldValue;    
          }    
      }    
  
      // 若“该key”对应的键值对不存在，则将“key-value”添加到table中    
      modCount++;  
//将key-value添加到table[i]处  
      addEntry(hash, key, value, i);    
      return null;    
  }

如果key为null，则将其添加到table[0]对应的链表中，putForNullKey的源码如下：

// putForNullKey()的作用是将“key为null”键值对添加到table[0]位置    
private V putForNullKey(V value) {    
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
        if (e.key == null) {    
            V oldValue = e.value;    
            e.value = value;    
            e.recordAccess(this);    
            return oldValue;    
        }    
    }    
    // 如果没有存在key为null的键值对，则直接题阿见到table[0]处!    
    modCount++;    
    addEntry(0, null, value, 0);    
    return null;    
}

如果key不为null，则同样先求出key的hash值，根据hash值得出在table中的索引，而后遍历对应的单链表，如果单链表中存在与目标key相等的键值对，则将新的value覆盖旧的value，比将旧的value返回，如果找不到与目标key相等的键值对，或者该单链表为空，则将该键值对插入到改单链表的头结点位置（每次新插入的节点都是放在头结点的位置），该操作是有addEntry方法实现的，它的源码如下：

// 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。    
void addEntry(int hash, K key, V value, int bucketIndex) {    
    // 保存“bucketIndex”位置的值到“e”中    
    Entry<K,V> e = table[bucketIndex];    
    // 设置“bucketIndex”位置的元素为“新Entry”，    
    // 设置“e”为“新Entry的下一个节点”    
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
    // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小    
    if (size++ >= threshold)    
        resize(2 * table.length);    
}

• 注意这里倒数第三行的构造方法，将key-value键值对赋给table[bucketIndex]，并将其next指向元素e，这便将key-value放到了头结点中，并将之前的头结点接在了它的后面。该方法也说明，每次put键值对的时候，总是将新的该键值对放在table[bucketIndex]处（即头结点处）。
  两外注意最后两行代码，每次加入键值对时，都要判断当前已用的槽的数目是否大于等于阀值（容量*加载因子），如果大于等于，则进行扩容，将容量扩为原来容量的2倍。

关于扩容。上面我们看到了扩容的方法，resize方法，它的源码如下：

// 重新调整HashMap的大小，newCapacity是调整后的单位    
void resize(int newCapacity) {    
    Entry[] oldTable = table;    
    int oldCapacity = oldTable.length;    
    if (oldCapacity == MAXIMUM_CAPACITY) {    
        threshold = Integer.MAX_VALUE;    
        return;    
    }    
  
    // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中，    
    // 然后，将“新HashMap”赋值给“旧HashMap”。    
    Entry[] newTable = new Entry[newCapacity];    
    transfer(newTable);    
    table = newTable;    
    threshold = (int)(newCapacity * loadFactor);    
}

很明显，是新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。transfer方法的源码如下：

// 将HashMap中的全部元素都添加到newTable中    
void transfer(Entry[] newTable) {    
    Entry[] src = table;    
    int newCapacity = newTable.length;    
    for (int j = 0; j < src.length; j++) {    
        Entry<K,V> e = src[j];    
        if (e != null) {    
            src[j] = null;    
            do {    
                Entry<K,V> next = e.next;    
                int i = indexFor(e.hash, newCapacity);    
                e.next = newTable[i];    
                newTable[i] = e;    
                e = next;    
            } while (e != null);    
        }    
    }    
}

很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。

• 注意containsKey方法和containsValue方法。前者直接可以通过key的哈希值将搜索范围定位到指定索引对应的链表，而后者要对哈希数组的每个链表进行搜索。

• 我们重点来分析下求hash值和索引值的方法，这两个方法便是HashMap设计的最为核心的部分，二者结合能保证哈希表中的元素尽可能均匀地散列。

  计算哈希值的方法如下：

  static int hash(int h) {

  h ^= (h >>> 20) ^ (h >>> 12);  
  return h ^ (h >>> 7) ^ (h >>> 4);  
  

  }

它只是一个数学公式，JDK这样设计对hash值的计算，自然有它的好处，至于为什么这样设计，我们这里不去追究，只要明白一点，用的位的操作使hash值的计算效率很高。

由hash值找到对应索引的方法如下：

static int indexFor(int h, int length) {  
    return h & (length-1);  
}

这个我们要重点说下，我们一般对哈希表的散列很自然地会想到用hash值对length取模（即除法散列法），Hashtable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是HashMap对Hashtable的一个改进。

接下来，我们分析下为什么哈希表的容量一定要是2的整数次幂。首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。

针对Hashtable，我们同样给出几点比较重要的总结，但要结合与HashMap的比较来总结。

1. 二者的存储结构和解决冲突的方法都是相同的。
2. HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
3. Hashtable中key和value都不允许为null，而HashMap中key和value都允许为null（key只能有一个为null，而value则可以有多个为null）。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。
4. Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。
5. Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在求hash值对应的位置索引时，用取模运算，而HashMap在求位置索引时，则用与运算，且这里一般先用hash&0x7FFFFFFF后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变。

LinkedHashMap源码解析

HashSet和TreeSet

直接用的HashMap和TreeMap来实现，值为new Object()