HashMap 原理

HashMap 是 Java 中最常见的一种数据结构，数组+链表的存储数据，无参的构造方法，(其他构造方法，如传入数组容量和加载因子)。

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

public HashMap() {
    table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
    threshold = -1; 
}

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内部类，字段包含 key、value、hash和 HashMapEntry 引用。

HashMap 数据结构图

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

@Override 
public V put(K key, V value) {
    if (key == null) {
        return putValueForNullKey(value);
    }
    //每个进来的kay先计算hash
    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;
        }
    }
    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;
    }
}

空 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 的数组索引，造成浪费。

总结

HashMap 存储，无序，无索引，需要调用 hashCode 方法，key 不能是基本类型，必须是引用才能调用对象的 hashCode() 方法和 equals() 方法。

负载因子3/4，当达到时，扩容数组x2，rehashing 将原来对象放到新数组坑位处，容量设计成2的整数次幂，在 hash 计算index过程中，保证与值全是1。否则会造成 index 浪费。

Collections.synchronizeMap 可以让其线程同步。

HashMap 允许 key 值是空，此时 hash=0。

若两个 key 对象 hashCode 相同，还需要再比较 equals() 方法，再相同，才能定位到同一个坑位链表中的同一个 value 值。

任重而道远