JavaHashMap分析之一:基本结构

先来看一下数组的定义：

/**     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

static class Entry implements Map.Entry {        final K key;        V value;        Entry next;        final int hash;        /**         * Creates new entry.         */        Entry(int h, K k, V v, Entry n) {            value = v;            next = n;            key = k;            hash = h;        }        ....        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;        }        public final int hashCode() {            return (key==null   ? 0 : key.hashCode()) ^                   (value==null ? 0 : value.hashCode());        }        ....

public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity <0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        // Find a power of 2 >= initialCapacity        int capacity = 1;        while (capacity 


第三,什么时候应该调整数组的大小？


算法是这样，有一个变量size保存了实际数组已经使用了多少个元素，并且如果size的值达到了变量threshold的值，就必须扩充数组的容量。threshold=capicity*loadFactor.capicity是数组最大的容纳元素个数，loadFactor可以在构造函数中制定，否则采用默认值0.75f。capicity的最大值是1<<30(也就是2的30次方,1073741824).由此我们可以看到HashMap最多存放10亿多个链表。


第四，如何调整数组大小？


答案是2倍，很像C++里面的vector的分配策略。




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


第五，为什么数组大小必须是2的倍数？


在后面介绍散列值算法的时候会回答。