HashMap梳理

概述

HashMap是基于哈希表的 Map 接口的实现。数据以键值对的形式存储，和HashTab的差别在于HashMap可以以null作为键值，但是HashMap是线程不安全的。如果要实现线程同步可以使用：

• Map map = Collections.synchronizedMap(new HashMap());
• ConcurrentHashMap

HashMap的数据结构

HashMap是通过数组和链表（散列链表）来实现数据存储的。之所以HashMap查询速度很快，是因为它是通过散列码来决定存储位置。通过获取key的hashcode和数组的长度的&值来确定存储的位置，如果有相同的key的hashcode，那么就是所谓的hash冲突，就添加到对应的链表结构的数据中。

image.png

紫色代表数组代表哈希表，也称为哈希数组，绿色代表链表。数组存储具有相同key值hashcode的链表的表头。数组的元素和链表的节点都是Entry对象。

HashMap源码分析（Android中的源码）

• HashMapEntry对象：

/** HashMapEntry是单向链表。    
    * 它是 “HashMap链式存储法”对应的链表。    
    * 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数  
    **/
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;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override public final boolean equals(Object o) {
            if (!(o instanceof Entry)) {
                return false;
            }
            Entry<?, ?> e = (Entry<?, ?>) o;
            return Objects.equal(e.getKey(), key)
                    && Objects.equal(e.getValue(), value);
        }

        @Override public final int hashCode() {
            return (key == null ? 0 : key.hashCode()) ^
                    (value == null ? 0 : value.hashCode());
        }

        @Override public final String toString() {
            return key + "=" + value;
        }
    }

HashMapEntry就是一个单向链表，每个节点包含了key、value、hash值、和下一个节点。

• 重要属性：

private static final int MINIMUM_CAPACITY = 4;//最小的容量，也是默认的初始容量
static final float DEFAULT_LOAD_FACTOR = .75F;//默认的加载因子
transient HashMapEntry<K, V>[] table;//哈希表
transient int modCount;//被修改的次数
transient int size;//存放元素的个数
private transient int threshold;//阈值，当前的元素个数查过阈值进行扩容，阈值 = 加载因子*总容量

加载因子在Android 的源码中被阉割了，固定为0.75，这是和在jdk中不同的地方

public HashMap(int capacity, float loadFactor) {
        this(capacity);

        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Load factor: " + loadFactor);
        }

        /* 加载因子固定为3/4
         * Note that this implementation ignores loadFactor; it always uses
         * a load factor of 3/4. This simplifies the code and generally
         * improves performance.
         */
    }

加载因子表示HashMap填充的程度，加载因子越大，HashMap填充的越满才进行扩容，空间利用率越高，造成的问题是存放的数据越多，hash冲突的可能性越大，查找的效率越低。反之亦反。这是一个空间和效率的之间的取舍。一般用默认的就行了。

• put方法：

public V put(K key, V value) {
        if (key == null) {
            //存放null的key值，则将该键值对添加到table[0]中。
            return putValueForNullKey(value);
        }
        //对key的hashcode值进行再次计算得到hash。
        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        //通过hash值和数组长度来确定数组的下标，这里的值不是随便取的
        int index = hash & (tab.length - 1);
        //遍历对应的数组下标的链表，如果存在相同的key值就替换原来的value
        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++;
        //否则加载列表的头部（也就是数组对应的位置）
        //在添加新的数据之前检查是否需要扩容。如果数据的大小超过阈值，数组的容量就扩大到原来的2倍
        if (size++ > threshold) {
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
        }
        //把数据添加到表头
        addNewEntry(key, value, hash, index);
        return null;
    }

hash & (tab.length - 1)的算法来取到数组的下标值，这个方式即可实现均匀的散列，还可以使数组不越界。那为什么扩容需要2的次幂呢，因为hash & (tab.length - 1)中，如果括号中的结果数奇数的话最后一位为1，hash&xx最后的接口有可能是奇数也有可能是偶数；如果括号中的值是偶数的话，那最后的结果也只能是偶数，那么数组存放的值只能存放在偶数下标中，浪费了一般的资源，如果是2的倍数减一，刚好能够控制能过取到所有的下标值。因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
扩容：

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++) {
            /*
             * Rehash the bucket using the minimum number of field writes.
             * This is the most subtle and delicate code in the class.
             */
            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;
    }

新建了一个数组，是原来数组容量的两倍，然后重新计算hashcode在数组中的位置，并且存放在数组中。
那为什么扩容呢？随着HashMap存放的数据越来越多，hash冲入产生的概率就越来越大，造成查找效率越来越低，所以进行扩容，但是扩容需要把所有的元素遍历重新赋值，还要新建一个数组，这是HashMap很消耗资源的地方。
在达到阈值的时候开始扩容，如：现在的容量大小为8,8*0.75 = 6，当HashMap中的元素个数达到6的时候就开始扩容。