图解JDK 8 HashMap

HashMap-简介

HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个

JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。

HashMap-数据结构

这是 HashMap 类中的一个成员变量，它是一个存储桶数组。table 数组用于存储键值对的实际数据。

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    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;
        }
}

这是 HashMap 内部定义的静态嵌套类 Node，它实现了 Map.Entry 接口。每个 Node 对象表示 HashMap 中的一个键值对，它包含键、值以及指向下一个节点的引用，从结构上来看，HashMap中链表结构与LinkedList相似。

测试示例

    public static void main(String[] args) {

        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("KING",100);
    }

图解HashMap-put方法

根据key获取hash值

Hash是将Key转换为一个短的、定长的值去替代源Key作为索引，以更快的查询。

通过hash方法得到"KING"对应的hash值为2306996。

计算方式：

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

通过hash值得到对应的桶的Index

计算方式：

(n - 1) & hash

如此，当调用put方法将元素添加到HashMap时，“KING”、100便被放入到Index为4的Node中。

由于index为4的Node节点并无除"KING"其他元素，所以它的下一个节点信息为null。用同样的方法将"CLARK"

，90放入HashMap。

不同的Key得到的Index值相同的情况

接下来我们把Key:“BLAKE”,value:10放入该Map，得到key值的hash为63281940：

根据63281940计算Index结果为4：

由于"KING"对应的Node节点也为4，Key："BLAKE"计算出的Index同样为4，不同的key通过哈希算法(n - 1) & hash计算出的索引位置相同时即为哈希冲突，HashMap在发生哈希冲突时，会将具有相同哈希码的键值对存储在同一个桶（bucket）中，通过链表或者在元素数量较多时转换为红黑树来处理冲突。如此，HashMap的结构将变为：

图解HashMap-get方法

HashMap的get方法用于获取指定键对应的值。

以获取"KING"的值为例：

Integer integer = hashMap.get("KING");

先计算出key的hash值，根据key值和key的hash值去获取Node信息。

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

在定位到的桶中查找与给定键相匹配的节点。如果找到了匹配的节点，则返回该节点的值。

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) {
        // 数组元素相等
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中可能存在不止一个节点
        if ((e = first.next) != null) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

先来明确一下各个变量的意义：

• key：要查询的指定key
• table：当前HashMap哈希表实际数据存储，用于存储节点的桶
• first：要查询的指定key匹配到某个桶的第一个节点
• e：临时节点，用于遍历桶中的节点链表或树结构。在这段代码中，e 用于遍历桶中的节点以查找匹配的键值对。
• n：这是一个整数，表示哈希表的长度，即桶的数量。
• k：这是一个键对象，表示 first 节点的键，即指定key计算后hash值对应桶的第一个节点的键。

链表

把上文源码链表部分翻译成一张图片：

图片局部放大：

当同一个Node<Key,Value>中存在多个元素时，开始根据key值和key的hash值在链表中匹配对应的value值。

红黑树

由于在链表中获取对应Value值的过程是通过for循环实现的，其时间复杂度为O(n)，当链表过长时，查询时间变长，JDK使用红黑树解决了该问题，当链表长度大于8时，链表进行树化。

红黑树结构

如果存储桶中的元素是一个红黑树，则通过红黑树的查找算法，在红黑树中查找具有相同哈希码并且键相等的节点。

后续内容文章持续更新中…

近期发布。

关于我

👋🏻你好，我是Debug.c。微信公众号：种棵代码技术树 的维护者，一个跨专业自学Java，对技术保持热爱的bug猿，同样也是在某二线城市打拼四年余的Java Coder。

🏆在掘金、CSDN、公众号我将分享我最近学习的内容、踩过的坑以及自己对技术的理解。

📞如果您对我感兴趣，请联系我。

若有收获，就点个赞吧，喜欢原图请私信我。