JCF

JCF 即 java collections framework，有 Collection 和 Map 两个接口，下面来谈谈我学习的 JCF 的学习历程和看法。

Map

如何做到key唯一不重复的?每次都循环拿key equals?

JDK 1.7 HashMap put 源码分析

public V put(K key, V value) {
	//从头开始找，找到 key 为 null 的 entity，将其 value 替换为传入的 value
    if (key == null)
        return putForNullKey(value);  
    //由 key 计算 hash 值
    int hash = hash(key);   
    //由 hash 值和 Entity 数组长度计算存放这一对key-value的位置
    int i = indexFor(hash, table.length);  
    //从计算的位置开始遍历，中途没有跳出，就会一直遍历到 Entity 数组末尾
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
	    //临时存放当前 entity 的 key
        Object k;  
        //如果当前 entity 的 hash 值与传入 key 计算的 hash 值相等，且 (key 的地址相等 或 两个 key eq)，
        //使用 传入的 value 替换当前 entity 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;
        }
    }

	//用于 fast-fail ，通过 modCount 值是否和预期相等来判断是否线程安全
    modCount++;  
    //如果在 HashMap 的 Entity 数组中没有找到传入的 key，新增一个 Entity
    addEntry(hash, key, value, i);  
    return null;
}

简单的流程图：

结论：

• 如果传入相同的key，value值会被替换成新的
• 每次都是从计算得到的索引往后找，判断table中是否有相同的key

List

ArrayList 长度探究

JDK 1.7 ArrayList 构造器源码分析

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    super();
    //如果传入的数组初始长度小于0，抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    //创建一个 Object数组 来存放元素
    this.elementData = new Object[initialCapacity];  
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
	//如果没有指定长度，默认是10
    this(10);
}

JDK 1.7 ensureCapacity 源码分析，ensureCapacity 被用于改变 ArrayList 的数组长度 ArrayList.class

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
//指定ArrayList长度的方法，实际上就是设置Object数组的长度
public void ensureCapacity(int minCapacity) {
	//校验设置的长度是否大于0
    if (minCapacity > 0)
        ensureCapacityInternal(minCapacity);
}

private void ensureCapacityInternal(int minCapacity) {
	//用于标示当前ArrayList长度是否改变，用于线程安全
    modCount++;
    // overflow-conscious code
    //更改的长度必须比现有长度大
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    //存储以前的长度
    int oldCapacity = elementData.length;
    //"oldCapaticy>>1"表示baseValue右移1位，即除以2
    int newCapacity = oldCapacity + (oldCapacity >> 1);  
    //如果 newCapacity 比设定长度小，把设定长度放入 newCapacity 
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果 newCapacity 比数组的最大值大
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    //如果 newCapacity>minCapacity 且 newCapacity<MAX_ARRAY_SIZE，
    //原来的数组数据拷贝到新数组，并设置新数组长度是 newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
//最大数组长度设置成 Integer 最大值减 8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
	//如果设置的值小于0，抛出异常
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //如果设置值比数组最大长度长，返回 Integer 最大值；
    //否则，返回 数组最大值
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Array.class

public static <T> T[] copyOf(T[] original, int newLength) {
	//拷贝数组original到新数组，新数组长度是newLength
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
	//判断传入的newType是不是一个对象数组的类型
	//如果是，创建一个对象数组给 copy
	//如果不是，创建一个 newType 数组给 copy
    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;
}
//创建一个新的数组，元素类型是 componentType，长度是 length
public static Object newInstance(Class<?> componentType, int length)
        throws NegativeArraySizeException {
    return newArray(componentType, length);
}
//创建新数组是一个 native 方法
private static native Object newArray(Class componentType, int length)
        throws NegativeArraySizeException;

System.class

//拷贝数组也是一个 native 方法
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

JDK 1.7 HashMap add 源码分析 ArrayList.class

public boolean add(E e) {
	//判断添加元素位置是否越界
	//size当前数组已添加的元素个数，可以理解为指向数组的位置
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //添加元素
    elementData[size++] = e;
    return true;
}

//判断添加元素数组是否越界
private void ensureCapacityInternal(int minCapacity) {
	//长度标志自增
    modCount++;
    // overflow-conscious code
    //判断新增元素位置是否越界
    //如果越界，调用 grow 方法
    if (minCapacity - elementData.length > 0)
	    //扩容
        grow(minCapacity);
}

//扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    //存储以前的长度
    int oldCapacity = elementData.length;
    //"oldCapaticy>>1"表示baseValue右移1位，即除以2
    int newCapacity = oldCapacity + (oldCapacity >> 1);  
    //如果 newCapacity 比设定长度小，把设定长度放入 newCapacity 
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果 newCapacity 比数组的最大值大
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    //如果 newCapacity>minCapacity 且 newCapacity<MAX_ARRAY_SIZE，
    //原来的数组数据拷贝到新数组，并设置新数组长度是 newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

JDK 1.7 ArrayList trimToSize 源码分析

//去掉多余的数组预留位，内存较为紧缺的时候会用到
public void trimToSize() {
    modCount++;
    //把当前数组长度存储到 oldCapacity 
    int oldCapacity = elementData.length;
    //如果当前数组长度比 size（数组指针指向的位置）大
    //提取数组中的前size个元素，多余的元素去掉
    if (size < oldCapacity) {
        elementData = Arrays.copyOf(elementData, size);
    }
}