【Java】JDK8 HashMap 原理分析(上)——链表部分

【Java】JDK8 HashMap 原理分析(上)——链表部分

之前学习容器的时候缺少了一些笔记,现在补一下笔记顺便重新理解一遍这些容器的源码。

HashMap 是我们在 Java 开发中经常接触到的容器,今天就让我们从它的源码入手来了解它的实现原理。本文为上部分,不包含其有关红黑树的操作,下一篇文章将会介绍红黑树相关知识及 HashMap 中有关红黑树的实现。

链表节点 Node

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        // 1
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

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

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

从上面的代码中可以看到,其实每个数组中存放的就是一个链表,每个节点中存放了key、value、key 的 hash 值以及下一个节点的引用等信息。

同时可以看到注释 1 处,hashCode 是根据 key 的 hashCode 和 value 的 hashCode 通过异或求出的。

构造函数

下面我们看到 HashMap 的构造函数:

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

主要就是一些值的初始化,同时将阈值设定为了比 initialCapacity 大的 2 的次方的值。

它是怎么计算的呢?我们看看 tableSizeFor 方法:

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

可以看到,是通过位运算的形式将 n 同位数的每一位都设为1,之后再进行 +1 得到。

比如 01xx.xxx:

对n右移1位:001xx…xxx,再位或:011xx…xxx

对n右移2位:00011…xxx,再位或:01111…xxx

这样就可以得到比 cap 大的距 cap 最近的 2 的次方数。

那么为什么要先将 cap -1 再赋值给 n 呢?

因为可能 cap 本身就是 2 的次方数,如果 n 是 cap-1 就可以使得得到的数为 cap 本身。

扩容操作

下面我们来看一下 HashMap 的 resize 函数,代码有点长,我们慢慢分析:

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 1
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
        // 2
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 3
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 4
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 5
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                // 6
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                // 7
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                // 8
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

首先在注释 1 处,在当前容量大于 0 的情况下,若容量已经达到上限,并且设置阈值为 Integer.MAX_VALUE。

否则新容量为旧容量的两倍,同时如果旧容量大于默认容量,则新阈值变为旧阈值的两倍。

在注释 3 处,若当前表为空的,但有阈值,说明是初始化时指定了阈值、容量的情况,此时将新的容量赋值为旧的阈值

在注释 4 处,若当前表为空的,且没有阈值,说明是初始化时没有指定容量、阈值的情况,此时指定容量为默认的 16,而阈值为其 loadFactor(默认 0.75 )倍。

在注释 5 处,若新阈值为 0,则说明为初始化时指定了阈值、容量的情况,此时指定阈值为新容量的 loadFactor(默认为 0.75)倍。

在注释 6 处,如果桶中只有一个元素,则将这个元素放入新桶中(也就是高区对应的桶)

在注释 7 处,如果已经发生过 hash 碰撞,转化为了红黑树,这里先不研究

在注释 8 处,根据 hash 值位与上旧的容量的结果来决定是放在低区还是高区的桶中。

增添/修改操作

看到 HashMap 的 put 方法:

 public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
 }

可以看到,它调用了 putVal 函数,传入了经过 hash 函数计算后的 key 的 hash 值,以及一些必要参数。

key 的 hash 值计算

我们先了解一下 key 的 hash 值计算,看到 hash 函数:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

可以看到,key 的 hash 值,是综合了高位和低位的特征,并将值存放在低位从而得到的 hash 值,具体做法是将高位和低位进行了异或计算,得到了一个最终的 hash 值。

上面的这种做法就是所谓的扰动函数,通过这样的设计可以使得高位和低位全部加入到计算中,从而减少 hash 碰撞的概率

putVal 方法

我们看到 putVal 方法的实现:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        // 1
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 2
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 3
            e = p;
        else if (p instanceof TreeNode)
            // 4
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                // 5
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 6
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            // 7
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 8
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

可以看到注释 1 处,如果当前哈希表为空的,则直接调用 resize 进行扩容,并将扩容后长度赋值给 n。

然后我们继续看到注释 2 处,如果当前 index 节点为空,说明没有发生过 hash 碰撞,则我们直接构建一个新的节点,挂载在对应 index 上。关于 index 的计算之前有介绍,利用 hash 值与桶长度进行与运算从而得到(用于替代 取模运算)

在注释 3 处,若 hash 值与 key 都相同,则应当是覆盖的操作,将 p 的引用赋值给 e

在注释 4 处,则是红黑树部分的操作,我们留到下部分进行分析

在注释 5 处,则是遍历链表,当遍历到链表尾时,追加这个节点。其中 bin 用于记录链表中的节点数量,如果超过了 8,则会将其转化为红黑树

在注释 6 处,如果找到需要覆盖的节点,则跳出循环。

在注释 3 与 注释 6 处都是需要覆盖的操作,此时经过前面的步骤 e 都已经位于它需要覆盖的位置,此时就在注释 7 处统一进行处理。

在注释 7 处,先获取到旧的 value,之后将节点的 value 进行覆盖,此时如果指定了 onlyIfAbsent 为 true,则不会进行覆盖

之后调用的 afterNodeAccess 方法其实是一个没有实现的方法,将其实现延迟到了其子类(如 LinkedHashMap)中。

之后返回了该节点的原值。

在注释 8 处,也就是非覆盖操作的情况下,首先修改了 modCount,之后更新了 size 的大小,如果超过了阈值,则调用 resize 进行扩容。

而调用的 afterNodeInsertion 也是一个没有实现的方法,将其实现延迟到了子类(如 LinkedHashMap)中。

最后由于没有覆盖,因此返回了 null。

同时这里还需要注意一下 onlyIfAbsent 这个 boolean 值,如果为 true,则发现了已经存在对应 key 的数据则不会进行覆盖操作。(JDK8 加入了一个 putIfAbsent 方法就是保证了若已存在则不进行覆盖)。

虽然这里 evict 只是在 afterNodeInsertion 这个空实现的方法用到,但是还是在这里提一下它的用法。在它为 false 的情况下,则表示是在初始化的时候调用的。

若存在则不覆盖的 put 方法(JDK8)

在 JDK8 加入了一种若存在该 key 的节点,则不进行覆盖的 put 方法 putIfAbsent,它的代码如下:

@Override
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

可以看到,实际上就是调用 putVal 并将 onlyIfAbsent 置为了 true。

删除操作

我们看到根据 key 来删除对应数据的 remove 方法:

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

可以看到,它调用了 removeNode 方法,并设置 matchValue 为 false,moveable 为 true

removeNode 方法

我们看到 removeNode 方法的实现:

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 1
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 2
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

首先看到注释 1 处,若哈希表不为空,则通过 key 拿到对应的桶的首节点。

之后如果首节点就是对应 key 的节点,则将 node 赋值为该首节点。

否则在该链表中找到对应 key 的节点,并将 node 赋值为该节点,其中红黑树相关操作这篇先不做介绍。

然后看到 2 处,这里主要进行删除节点的操作。如果 matchValue 为 true 则再进行一次 value 的对比,都匹配才会进行删除。

删除的关于红黑树的操作在本篇文章先不讲解。

然后看到下面,如果要删除的是链表头的数据,则将头节点改为该节点的下一个节点。

否则是普通节点,p 为 node 的上一个节点,此时将 p 的 next 指向 node 的 next。

这个 afterNodeRemoval 方法也是一个空实现的方法,将实现延迟到了子类。

最终,remove 返回了删除的节点。

key value 同时匹配删除

remove 方法还有一个重载方法,它可以同时匹配 key 和 value 的情况下才进行删除,代码如下:

@Override
public boolean remove(Object key, Object value) {
    //这里传入了value 同时matchValue为true
    return removeNode(hash(key), key, value, true, true) != null;
}

可以看到,仅仅是将 matchValue 置为了 true,不再赘述。

查找操作

下面我们看到根据 key 获取对应 value 的 get 方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

可以看到这里调用了 getNode 方法以获取 key 对应的节点。

getNode 方法

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 1
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

首先在注释 1 处,找到了 key 对应的桶的第一个元素,先判断是否是我们需要的 key,如果是则直接返回该节点。

之后在注释 2 处则开始向后查询,其中关于红黑树的操作这里先不赘述,看到下面循环,实际上就是在链表中进行遍历寻找对应节点,找到则返回。

判断是否包含 key 或 value

判断是否包含某个 key 的代码如下:

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

非常简单,实际上就是调用 getNode 查看返回值是否为 null。

而判断是否包含 value 的代码如下:

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

代码也很简单,可以看到,就是遍历每个桶中的所有节点,看是否具有 value 为该值的元素。

带默认值的 get 方法(JDK8)

在 JDK8 加入了一种带默认值的 get 方法 getOrDefault,代码如下:

@Override
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

其实就是调用的时候找不到不再返回 null 而是默认值,不再赘述。

总结

HashMap 具有如下的特点:

  • HashMap 是线程不安全的
  • HashMap 允许 key 为 null,value 为 null。
  • 遍历 HashMap 时是无序的。

哈希桶及其扩容

HashMap 的底层数据结构是数组,称其为哈希桶,每个桶中存放了链表,链表中的每个节点,就是 HashMap 中的每个元素

在 JDK8 中,当链表长度达到 8 时,会被转化为红黑树,以提升其插入、查找的效率。而当长度较小时,红黑树又会转变回链表。这样的设计是为了节省空间。

哈希桶一个是数组,因此也会有扩容的操作。当 HashMap 的容量达到了 threshold 这个阈值时,会触发扩容操作。并且哈希桶的长度一定是 2 的次方。

为什么要将长度限定为 2 的次方呢?

因为这样在根据 key 的 hash 值寻找对应哈希桶的时候,可以用位与运算代替取余操作,提高效率。

在扩容时,会 new 一个新的 Node 数组作为哈希桶,将原哈希表中所有数据移动到新的哈希桶中,也就是每个数据都做了一次 put 操作,可以想象到这样的性能消耗是较大的。哈希表的容量越大时,扩容操作的性能消耗越明显

扩容时,若节点数小于 8 个,则根据每个节点的 hash 值依次放入新的哈希桶对应位置。

扩容后会容量翻倍,原链表上的每个节点,可能会存在于原来的下标(低区)或者是原来的下标+原哈希桶长度(高区)两种位置。(取余导致的)。

如果追加节点后,链表的数量大于等于 8,则将转化为红黑树。

下面是 HashMap 的示意图:

image-20190319151049053

hash 值的计算

我们都知道, HashMap 需要求出 key 的 hash 值,并通过它寻找该节点存放的桶的下标。那么 key 的 hash 值仅仅是 key 对象的 hashCode() 方法的返回值么?

其实不是的,它的返回值还会经过扰动函数的扰动,使得 hash 值更加均衡。

为什么要这么做呢?我们需要提到一个叫做 hash 碰撞的情况。

由于 HashMap 的哈希桶长度远小于 hash 值可以取到的范围(默认为 16),并且当对 hash 值以桶长度取余时,只有 hash 值的低位参加了运算。这就会导致不同 hash 值得到相同 index 的几率会大大增加,这就是所谓的hash 碰撞

而前面提到的扰动函数,就是为了解决这种 hash 碰撞的现象。它会结合 hash 值的高位和低位的特性计算出一个值,从而使得高位和低位都参与了这个求余运算,从而使得 hash 碰撞的概率减小。

HashMap 中的位运算

HashMap 中经常为了提高效率,用一些位运算替代了常规运算。比如:

  • 求余运算,使用hash & (table.length-1) 替代了 hash % (table.length),这也就是为什么哈希桶的长度需要是 2 的次方倍。

  • 使用if ((e.hash & oldCap) == 0) 来判断扩容后的节点应该是处于低区(原下标)的桶还是高区(原下标加原长度)的桶中

  • 获取大于等于 capcity 的二次方数时,使用了如下的位运算,具体解析可以看构造函数部分:

    static final int tableSizeFor(int cap) {
      int n = cap - 1;
      n |= n >>> 1;
      n |= n >>> 2;
      n |= n >>> 4;
      n |= n >>> 8;
      n |= n >>> 16;
      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    

参考资料

面试必备:HashMap源码解析:https://blog.csdn.net/zxt0601/article/details/77413921

HashMap原理分析put get remove:[https://blog.csdn.net/gaoanchen/article/details/52956250](

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: