Java简记

        这里随手做一些记录，以便有空时整理。

        HashMap

        HashMap是这么设计的，key和value实际上是存在于一个内部类Entry中，作为这个内部类的成员变量，有多少key-value就生成多少个Entry对象。这些Entry对象又存放在一个名为table的数组中。所以，HashMap实际的存储结构就是一个存有Entry对象的数组。

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
        ………………
}

        HashMap中有一个hash算法（HashTable则没有这个算法，而是直接用key的hashcode）来对key进行hash计算，这决定了这个Entry对象放到table的哪个位置。但是会出现hash值相同的key，table的同一个位置会对应多个不同的Entry对象，因此Entry内部类中还有一个成员变量next，存放的是Entry类型的引用。所以，table的同一位置如果有多个Entry对象，这些对象会通过其next引用来构成一个链表。
这是hash算法

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

存放元素的put方法，当key值存在时，更新value。如果不存在，调用addEntry方法

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        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;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

        以上大体就是HashMap的框架，等有时间再做详细补充。

        LinkedHashMap

        LinkedHashMap继承了HashMap，绝大多数的实现都是继承了HashMap，而没有进行重写。但是由于LinkedHashMap除了使用HashMap的Entry数组来保存其元素之外，还将各元素连接为一个链表。
        HashMap的Entry中有next成员变量，保存的是Entry类型的引用。LinkedHashMap中的Entry内部类继承了HashMap的Entry，而且还多了两个Entry类型的引用，before和after。
        HashMap的put方法在添加一个新元素(不是key值相同的元素更新，而是新添加的元素)实际调用的是addEntry方法，由于LinkedHashMap的Entry中多了两个成员变量，因此为了维护before和after，LinkedHashMap重写了addEntry方法。当然在删除元素时也需要维护这两个成员变量，所以删除方法也进行了重写。
重写的addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold)
                resize(2 * table.length);
        }
    }

        HashSet

        HashSet其实就是用HashMap实现的，只不过将HashMap的value统一用一个Object对象填充。也就是说，HashSet是只用了key的HashMap。

        ArrayDeque

        发现一个不错的类，貌似是1.6加入的。在使用上相比LinkedList没什么特别，但是在队列性能上貌似要好于LinkedList，用做stack也比Stack好。
        ArrayDeque是用环形数组实现的，有头尾两个指示器(通过在数组上加两个指示器，类似形成了一个环状结构)，通过检查头尾指示器是否相等来判断数组是否已满。下面是API上文档的一段介绍：

        Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited. This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.