HashMap在JDK1.7版本头插法实现解析

先解释下何为头插法。大家都知道HashMap在JDK1.7版本的数据结构为数组+链表这样的形式。而头插法说的就是在往HashMap里面put元素时，此时新增在链表上元素的位置为链表头部，也就是数组桶位上的那个位置，故名头插法。

直接上源码，看看JDK1.7的元素插入代码实现：

    public V put(K key, V value) {
	    // 步骤1
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        // 步骤2
        if (key == null)
            return putForNullKey(value);
        // 步骤3
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

稍微解释下前面代码流程：
1、如果往HashMap里面put元素的时候，发现还是空的未初始化（HashMap采用懒加载，用到的时候再去初始化），那就调用inflateTable(threshold)先给它初始化了先。
2、如果put元素的时候key为null，则进入putForNullKey(value)方法处理，大概逻辑就是将key为0的key-value放入entry,如果之前已有key为null的key-value键值对，则返回原value,否则返回null。
3、接下来就是取key的hash再做位操作（之所以不直接使用hashCode是为了加大低位信息的随机性，变相让高位数据参与到计算中）、然后获取元素key值运算得到数组的下标，最后再判断是否有相同key存在于entry,有就新value覆盖旧value然后返回旧value。

直到addEntry(hash, key, value, i)才是头插法的实现开始：

    void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }

if里面判断是否需要扩容，可先忽略接着看 createEntry(hash, key, value, bucketIndex)：

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

大家注意这个参数bucketIndex，它是之前用key的哈希值做过位运算之后再去找数组运算得到的下标。如果要讲key-value这个键值对放入hashmap的话，就会放到数组的这个位置或者这个位置的链表上。

Entry<K,V> e = table[bucketIndex]这一句则取到数组上这个下标的元素，然后作为new Entry<>(hash, key, value, e)的参数e：

    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

从代码可以得知，这个构造方法，利用key-value构造了一个entry,然后把它的next属性（类似链表的后继节点）指向原table[bucketIndex]，然后在上一层方法中复制给了table[bucketIndex]，实际效果就是想当于把该下标下的链表整体往下移了一部，再用新构造的entry放在链表头（同时也是数组上该下标的位置）。这就是jdk1.7版本hashmap元素在put时的头插法。

至于为什么会采用头插法，据说是考虑到热点数据的原因，即最近插入的元素也很可能最近会被使用到。所以为了缩短链表查找元素的时间，所以每次都会将新插入的元素放到表头。

这里再稍微拓展下，大家都知道数组查找元素快，而插入或删除元素慢；而链表恰恰相反，查找元素慢，插入或删除快。这是因为两个的数据结构不同而导致的。
数组因为有下标的存在，可以直接根据下标定位到相应元素。而在插入元素或删除元素时，却需要移动该元素后面所有的元素，所以开销会比较大。
而链表没有下标的存在，想要查找元素只能从头结点顺着往下找，若链表非常长且目标元素恰巧在链表尾部，花费的时间相对而言也不短了。同时链表有前继节点与后继节点的存在，当需要插入或删除元素时，只需要修改两个节点的前继节点与后继节点的指向就行了，这也是为什么链表新增或删除元素要比数组快的原因。