图解JDK 8 HashMap

站长

2024年04月14日 20:25 · 阅读数 2

图解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;
        }
}

图解JDK 8 HashMap

这是 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作为索引，以更快的查询。

图解JDK 8 HashMap

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

计算方式：

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

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

图解JDK 8 HashMap

计算方式：

(n - 1) & hash

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

图解JDK 8 HashMap

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

，90放入HashMap。

图解JDK 8 HashMap

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

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

图解JDK 8 HashMap

根据63281940计算Index结果为4：

图解JDK 8 HashMap

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

图解JDK 8 HashMap

图解HashMap-get方法

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

以获取"KING"的值为例：

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

图解JDK 8 HashMap

先计算出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;
}