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时的头插法。

 

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

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