Java 容器---实现

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 这里是扩容的关键
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 批量添加，也有可能会直接等于相加之后的容量
    if(newCapacity - minCapacity < 0) newCapacity = minCapacity;
    if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 缩小容器的容量到元素的数量
public void trimToSize();
// 确保容量能覆盖 minCapacity 个元素
public synchronized void ensureCapacity(int minCapacity) ;

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // capacityIncrement 是构造函数中指定的值, 默认为0
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)  newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 小于64的时候增倍；大于64的时候增加50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
// queue是存放元素的数组
queue = Arrays.copyOf(queue, newCapacity);

// 添加一组映射的时候
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 容量超过threshold并且对应的hash值存在在冲突的时候，开始扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩展为之前的2倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

// 这个方法的作用在于将数组扩展到相应的容量，
// 并把原数组中的元素全部重新计算位置，转移到新数组中
// 重新计算下一个threshold
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// 这个方法在容器第一次添加元素的时候调用，使用toSize做参数的目的是避免第一次添加元素的时候多次扩容
private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

//这里的accessOrder要设置为true
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
}
// 缓存容量
private static final int MAX_ENTRIES = 100;
// 设置为超容量即删除
protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

public synchronized V put(K key, V value) {
    // ...
    // 容器中元素数量超过threshold时，扩容并重新计算hash，然后再添加元素
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();
        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // ...
}

protected void rehash() {
    int oldCapacity = table.length;
    Entry<K,V>[] oldMap = table;
    // 新容量是旧容量的2倍
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<K,V>[] newMap = new Entry[newCapacity];
    modCount++;
    // 这里计算新的阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    boolean rehash = initHashSeedAsNeeded(newCapacity);
    table = newMap;
    // 然后重新计算hash对应的位置
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;
            if (rehash) {
                e.hash = hash(e.key);
            }
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newMap[index];
            newMap[index] = e;
        }
    }
}

    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        V value;
        int hash;
        Entry<K,V> next;

        /**
         * Creates new entry.
         */
        Entry(Object key, V value,
              ReferenceQueue<Object> queue,
              int hash, Entry<K,V> next) {
            // key是弱引用持有的对象
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
    }

public V put(K key, V value) {
    // ...
    tab[i] = new Entry<>(k, value, queue, h, e);
    if (++size >= threshold)
        resize(tab.length * 2);
}

void resize(int newCapacity) {
    Entry<K,V>[] oldTable = getTable();
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry<K,V>[] newTable = newTable(newCapacity);
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(oldTable, newTable, rehash);
    table = newTable;
    /*
     * 如果在扩容过程中删除的元素非常的多，填充数不到阈值的一半的时候
     * 使用回之前容量的数组
     */
    if (size >= threshold / 2) {
        threshold = (int)(newCapacity * loadFactor);
    } else {
        expungeStaleEntries();
        transfer(newTable, oldTable, false);
        table = oldTable;
    }
}

/** Transfers all entries from src to dest tables */
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest, boolean rehash) {
    for (int j = 0; j < src.length; ++j) {
        Entry<K,V> e = src[j];
        src[j] = null;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object key = e.get();
            // 注意，这里在转移元素的过程中会删除一些已经被垃圾回收的元素
            if (key == null) {
                e.next = null;  // Help GC
                e.value = null; //  "   "
                size--;
            } else {
                if (rehash) {
                    e.hash = hash(key);
                }
                int i = indexFor(e.hash, dest.length);
                e.next = dest[i];
                dest[i] = e;
            }
            e = next;
        }
    }
}

    public V put(K key, V value) {
        // ...
        // 超过阈值，扩容
        if (++size >= threshold)
            resize(len); // len == 2 * current capacity.
        // ...
    }

    private void resize(int newCapacity) {
        // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
        // 原容量*2
        int newLength = newCapacity * 2;

        Object[] oldTable = table;
        int oldLength = oldTable.length;
        // 这里重新计算阈值
        if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
            if (threshold == MAXIMUM_CAPACITY-1)
                throw new IllegalStateException("Capacity exhausted.");
            threshold = MAXIMUM_CAPACITY-1;  // Gigantic map!
            return;
        }
        if (oldLength >= newLength)
            return;

        Object[] newTable = new Object[newLength];
        threshold = newLength / 3;
        // 重新计算位置， 由于这是闭散列，需要对所有元素重新计算
        for (int j = 0; j < oldLength; j += 2) {
            Object key = oldTable[j];
            if (key != null) {
                Object value = oldTable[j+1];
                oldTable[j] = null;
                oldTable[j+1] = null;
                int i = hash(key, newLength);
                while (newTable[i] != null)
                    i = nextKeyIndex(i, newLength);
                newTable[i] = key;
                newTable[i + 1] = value;
            }
        }
        table = newTable;
    }