HashMap原理分析

---

Java知识中最常用的一类数据结构，采用数组+链表的方式进行数据存储。看一下构造方法，下面是无参数的一个构造方法，其他传参的构造方法如传入数组容量和加载因子。

private static final int MINIMUM_CAPACITY = 4;
private static final Entry[] EMPTY_TABLE
            = new HashMapEntry[MINIMUM_CAPACITY >>> 1];//数组2个元素

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

table是内部HashMapEntry数组，HashMapEntry是内部存储对象，构造方法初始化数组，默认2个元素。
threshold代表数组的临界值，当数组元素大于该值时，数组将要扩容，默认值-1，这样看来，第一次向数组中放置元素时，就要扩容了。

static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;
    V value;
    final int hash;
    HashMapEntry<K, V> next;

    HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
        this.key = key;
        this.value = value;
        this.hash = hash;
        this.next = next;
    }
    ...
}

HashMap内部类，HashMapEntry存储对象，它内部包含键值key，value，hash，以及下一个HashMapEntry节点的引用。HashMap的存储数据结构图。 HashMap存储数据结构图.jpg

从结构图中可以看出，HashMap并不是按照数组顺序向数组中存入数据的，下面分析一下它的数据存取如何实现。先看put方法，它向HashMap中存入数据。

@Override 
public V put(K key, V value) {
    if (key == null) {
        return putValueForNullKey(value);
    }
    int hash = Collections.secondaryHash(key);//每个进来的kay先计算hash
    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值是空，调用putValueForNullKey方法。

private V putValueForNullKey(V value) {
    HashMapEntry<K, V> entry = entryForNullKey;
    if (entry == null) {
        addNewEntryForNullKey(value);
        size++;
        modCount++;
        return null;
    } else {
        preModify(entry);
        V oldValue = entry.value;
        entry.value = value;
        return oldValue;
    }
}

在HashMap内部，为空key单独保存一个HashMapEntry对象，它不在数组的某个bucket位置存储，如果之前已经put一个空key的键值，将修改HashMapEntry的value值。

void addNewEntryForNullKey(V value) {
    entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
}

空key对应hash是0，因此，可以得出结论，HashMap允许key值是空的情况存在。
当key不是空时，获取key的哈希值，然后，根据哈希值快速找到它在数组存放的具体位置，即index索引值。如果两个不同的key对象的hashCode发生碰撞，即已经有HashMapEntry对象在index索引处，采用链表解决冲突。
当hashCode相等，equals不一定相同。因此，遍历该坑位链表上的每个对象，查看key是否与新key相等(equals)，若找到equals相等的key键，直接更新HashMapEntry的value值，并返回旧value。若未找到，新建一个HashMapEntry对象，放置在数组index坑位链表头部。

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

新HashMapEntry存储了key，value，hash和当前坑位第一个对象的引用。
size代表数组元素当前存储大小，此次新put的值自增，当HashMap中元素不断增多，发生HashCode碰撞的概率将大大增加，导致链表长度增加，会影响存取速度和效率，因此，设置一个阀值，如果已经>threshold，数组需要扩容。

private HashMapEntry<K, V>[] doubleCapacity() {
    HashMapEntry<K, V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        return oldTable;
    }
    int newCapacity = oldCapacity * 2;
    HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
    //当数组没有元素时，直接返回新数组。
    if (size == 0) {
        return newTable;
    }

    for (int j = 0; j < oldCapacity; j++) {
        HashMapEntry<K, V> e = oldTable[j];
        if (e == null) {
            continue;
        }
        int highBit = e.hash & oldCapacity;
        HashMapEntry<K, V> broken = null;
        newTable[j | highBit] = e;
        for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
            int nextHighBit = n.hash & oldCapacity;
            if (nextHighBit != highBit) {
                if (broken == null)
                    newTable[j | nextHighBit] = n;
                else
                    broken.next = n;
                broken = e;
                highBit = nextHighBit;
            }
        }
        if (broken != null)
            broken.next = null;
    }
    return newTable;
}

如果数组的长度已经达到最大，不再扩容，返回旧数组。新数组的容量扩容2倍。makeTable方法，根据新容量，创建一个新数组。

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

新数组创建后，阀值设置为数组长度的3/4，如果继续put元素，当容量达到threshold，数组将继续扩充。threshold代表容量警戒阀值。
最后，遍历旧容量的元素，重新计算他们在新数组中的位置，并复制操作，数组扩容也比较耗时。
再看一下get方法，从HashMap中取出数据。

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;
}

数据取出和存入类似，比较简案，首先计算key的哈希值，再根据哈希值查找索引，遍历索引处的HashMapEntry链表。HashMapEntry的key与查询key对象相等。==表示指向同一地址，属于同一个对象，肯定equal相同的。另一种情况，就是key的equal相等，返回对应value值。
从数据存取的put与get方法来看，并没有实现同步，HashMap不是线程安全的数据结构。当多线程访问时，可以通过Collections.synchronziedMap创建HashMap实现线程同步，也可以使用线程安全的CorruntHashMap。
再看一下数组的容量设计成2的整数次幂，回到无参数的构造方法，HashMap的初始容量是2，扩容*2，发现它的容量都是2的整数次幂。我们在数据存取时，都要首先对键值key进行hash变换。然后根据下面的代码计算索引值。

int index = hash & (tab.length - 1);//计算索引

如果数组的容量是2的整数次幂，那么，与hash进行与操作的一定是11111..的二进制数据，操作效率较快。如果和hash进行与操作的有一位不是1，比如1101，那么，永远都不会有元素的hash值计算得到xx1x的数组索引，造成浪费。

---

任重而道远