时间戳

首页 > 技术文章 > HashMap(jdk7)原理分析总结

HashMap(jdk7)原理分析总结

buptleida 2020-05-13 19:16 原文

之所以标明“jdk7”，是因为jdk8和jdk7中的HashMap实现原理不一样。jdk7中使用“数组+链表”形式来实现哈希表，这与数据结构课上所学的一致。而jdk8在它的基础上，引入了红黑树。本博客先从最原始的“数组+链表”形式开始总结梳理。

首先在开始之前要有一个基本认识：HashMap是一个对象，对象中包含了一个Entry<K,V>[]数组，即哈希表数组，其中每一项代表一个bucket。键值对会按照一定索引顺序存储进bucket中。

哈希与索引的计算

哈希计算的目的在于，当程序获得一个key时，需要通过计算key的哈希值来得到key的索引值，即在Entry数组中的下标。然后进行增删改查等操作。

通过如下两行代码获取索引值

int hash = hash(key);
int i = indexFor(hash, table.length);

其中，hash()方法：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
  • 一次哈希：hashCode()是获取首次散列的哈希值的方法，由k所属的包装类实现；
  • 二次哈希：上面代码中有大量的无符号右移以及异或操作。这些操作的目的是，在进行下面indexFor方法时，不至于破坏 h 的特异性。

indexFor方法：

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);//仅保留h的后半部分，保证不越界
}

首先要说明，length必须是2的次方数。这样的话，length-1的后n位一定全是1，跟hash值进行与运算之后，相当于只保留hash的右边n位。

对于一个哈希表来说，往往希望插入的节点在数组中尽量地分散，减少链表出现的情况，这样可以减少冲突。通过以上这些手段，便可最大化键与键之间哈希值的差异，增强了散列性。

扩容机制

addEntry方法

在put等操作时，若在哈希表中没有找到对应 key ，需要新建一个新的节点时，会调用此方法。

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

//将键值对放入table中
    createEntry(hash, key, value, bucketIndex);
}

扩容的条件

1. size >= threshold

threshold 是一个决定是否扩容的阈值。根据capacity * loadFactor来决定。如下代码：

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

该方法用于初始化哈希数组，并设置threshold。

loadFactor是负载因子，默认值为0.75

2. null != table[bucketIndex]

当需要插入的位置为null时，就算超过阈值，也可以无需扩容。在JDK8中没有这个条件。

resize方法

当满足条件时，将数组长度扩容至两倍，执行以下resize方法

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

transfer方法

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //遍历所有节点，转移到新table上去
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

put操作

了解上面所有内容，再来看一个put方法就很简单了

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    //根据hash值计算索引值
    int i = indexFor(hash, table.length);
    //在该索引值位置顺序遍历链表，如果找到目标key就修改，返回
    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++;//结构发生修改的次数+1
    //进行到这一步说明需要新增一个key-value对
    addEntry(hash, key, value, i);
    return null;
}

addEntry方法中会调用createEntry方法，通过头插法新建一个结点

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

结点置换的操作十分精妙，本科C语言指针基础扎实的话很容易理解。
其它的删除、查询等操作都大同小异。

其它问题

多线程环境下的问题

当两个线程同时操作transfer时。若线程A先于线程B完成，B操作中的e和next指针会调头，因为是头插法，导致线程B的transfer循环中两个节点形成循环链表，陷入死循环。

当然，可以在初始化的时候设置容量和负载因子，防止扩容，可避免这个问题

参数设置

两个影响性能的参数：初始容量、负载因子

不设置默认是16和0.75

  • 负载因子过小，或者初始容量过大时，虽然索引效率高，但会造成空间的浪费；影响Collection视图迭代效率。
  • 负载因子过高，可减少空间上的开销，但是引发哈希冲突概率更高，产生的链表可能更长，会增加索引的成本；

因此需要寻求一种“空间效率”与“冲突概率”之间的平衡与折衷。典型的时空矛盾问题。

推荐阅读