HashMap

继承AbstractMap, 实现了Cloneable,Serializable接口, 所以是可以被克隆以及序列化的.
K,V都允许为null.

使用

一般而言使用是这样的

Map<K, V> map = new HashMap();
map.put(k, v);

构造方法

• public HashMap() 无参构造方法,初始数组长度为2.
• public HashMap(int capacity) 指定数组长度,如果不是2的n次方,增大到离该数最近的一个2的n次方的数.
• public HashMap(int capacity, float loadFactor) 与上一个一样,并且在HashMap忽略了这个负载因子,与上一个构造方法无异.

这里只看无参的构造方法.

public HashMap() {
    table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
    threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}

EMPTY_TABLE是一个长度为2的空数组,同时,将threshold赋值为-1,这个threshold后面会讲到.

put

public V put(K key, V value) {
    if (key == null) {
        return putValueForNullKey(value);
    }

    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    int index = hash & (tab.length - 1);
    for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
        if (e.hash == hash && key.equals(e.key)) {
            preModify(e);
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }

    // No entry for (non-null) key is present; create one
    modCount++;
    if (size++ > threshold) {
        tab = doubleCapacity();
        index = hash & (tab.length - 1);
    }
    addNewEntry(key, value, hash, index);
    return null;
}

当KEY为null的时候,处理比较简单.不去看了.下来是对获取key的hash值,至于为什么是调用secondaryHash方法来求hash值,其目的在于下面这一句 int index = hash & (tab.length - 1); 这个hash跟数组的长度减1(数组长度为2n -1)进行与运算时,能尽可能的产生不同的index, 并且这个index是小于数组长度的.这样就能最大程度的使元素能排布数组当中,在查找时,较少的在链表中查找.接着在数组与链表中查找是否有hash以及key相同的元素.有则替换value值.没有则把元素添加到数组的index位置.链表是怎么回事?继续看addNewEntry(key, value, hash, index)方法

void addNewEntry(K key, V value, int hash, int index) {
        table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
    }

将要插入的元素放到数组的index位置,然后当前元素指向上一个插入index位置的元素.链表,就是这样来的.最先插入这个位置的元素在链表尾部,最后插入的在链表头部.

扩容

if (size++ > threshold) {
    tab = doubleCapacity();
    index = hash & (tab.length - 1);
}

当HashMap的size加上要添加的元素之后大于threshold,进行扩容.那这个threshold是什么?看makeTable方法就知道了.

private HashMapEntry<K, V>[] makeTable(int newCapacity) {
    @SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
            = (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
    table = newTable;
    threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
    return newTable;
}

原来是数组的长度的3/4,也就是说,当要在添加一个元素之后存储的元素达到了数组的3/4,则进行扩容到原来数组的两倍.

get

public V get(Object key) {
    if (key == null) {
        HashMapEntry<K, V> e = entryForNullKey;
        return e == null ? null : e.value;
    }

    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
            e != null; e = e.next) {
        K eKey = e.key;
        if (eKey == key || (e.hash == hash && key.equals(eKey))) {
            return e.value;
        }
    }
    return null;
}

get方法就比较简单了.计算出根据hash计算出index,在数组的index位置遍历链表.