技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

HashMap源码解读

 收录于 未分类
   约 2801 字   预计阅读 6 分钟 
https://bing.ee123.net/img/rand?artid=146296127

HashMap源码解读

HashMap 是 Java 中常用的哈希表实现，它允许存储键值对，并且可以根据键快速查找对应的值。

类定义和主要属性

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // 默认初始容量，必须是 2 的幂
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当链表长度达到 8 时，将链表转换为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当红黑树节点数小于 6 时，将红黑树转换为链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 当桶数组长度达到 64 时，才允许链表转换为红黑树
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储数据的数组
    transient Node<K,V>[] table;
    // 键值对的数量
    transient int size;
    // 修改次数
    transient int modCount;
    // 扩容阈值，当 size 达到该值时，进行扩容
    int threshold;
    // 负载因子
    final float loadFactor;
}
  • DEFAULT_INITIAL_CAPACITY ：默认初始容量为 16，必须是 2 的幂，这样可以通过 位运算来提高哈希计算的效率 。
  • DEFAULT_LOAD_FACTOR ：默认负载因子为 0.75f，当键值对数量 达到容量的 75% 时，会进行 扩容 操作。
  • TREEIFY_THRESHOLD 和 UNTREEIFY_THRESHOLD ：用于 链表和红黑树 之间的 转换 。当链表长度达到 8 时，会将链表转换为红黑树；当红黑树节点数小于 6 时，会将红黑树转换为链表。
  • MIN_TREEIFY_CAPACITY ：当桶数组长度达到 64 时，才允许链表转换为红黑树。

注意： transient 是 Java 中的一个关键字，用于修饰类的成员变量。它的主要作用是 标记某个字段不需要被序列化 。

核心内部类 - 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; }

    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;
    }
}
  • Node 是 HashMap 中存储键值对的基本单元，每个 Node 包含一个键、一个值、一个哈希值和一个指向下一个 Node 的引用。
  • hashCode()方法里面调用了Objects类中的hashCode(Object o)方法，这个方法内部又调用了Object类中的hashCode()方法。
public static int hashCode(Object o) {
	return o != null ? o.hashCode() : 0;
}
 public native int hashCode();

Object 类中的 hashCode 方法特点：

  • native 关键字：

    • 表示这个方法是一个本地方法 （Native Method），它的实现不是用 Java 编写的，而是由底层的 C/C++ 代码实现。
    • 具体来说， hashCode 方法的实现是由 JVM（Java 虚拟机）提供的 。

  • 默认行为：

    • 如果一个类 没有重写 hashCode 方法，那么它会 使用 Object 类的 默认实现 。
    • 默认实现 通常基于对象的内存地址生成一个哈希码 （具体行为取决于 JVM 实现）。

  • 很多类会重写 hashCode() 方法，例如 String、Integer 等，它们的哈希码是基于内容计算的，而不是内存地址。

核心方法 - put

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果桶数组（table）为空或长度为 0，调用 resize() 方法进行初始化。
	// resize() 方法会创建一个新的桶数组，默认大小为 16。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 使用 (n - 1) & hash 计算桶索引，这是高效的取模运算（因为 n 是 2 的幂次方）。
	// 如果桶为空（即没有发生哈希冲突），直接插入新节点。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 检查桶中的第一个节点是否与要插入的键相等。
		// 如果相等，记录该节点（e = p），稍后更新其值。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果桶中的第一个节点是红黑树节点，调用红黑树的插入方法。
		// 红黑树是一种自平衡二叉搜索树，用于提高查找效率。
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        	// 如果桶中的第一个节点是链表节点，遍历链表。
			// 如果找到相等的键，退出循环；否则在链表末尾插入新节点。
			// 如果链表长度达到阈值（默认 8），调用 treeifyBin 方法将链表转换为红黑树。
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果找到了相等的键（e != null），更新该节点的值，返回旧值。
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 每次插入键值对后，检查当前键值对数量是否超过扩容阈值。
	// 如果超过，调用 resize() 方法进行扩容。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
  • put 方法用于向 HashMap 中插入键值对。
  • putVal 方法是 put 方法的具体实现，它的主要步骤如下：
    1. 如果桶数组为空或长度为 0，调用 resize 方法进行初始化。
    2. 计算键的哈希值，并根据哈希值找到对应的桶位置。
    3. 如果桶为空，直接插入新节点。
    4. 如果桶不为空，检查第一个节点是否与要插入的键相等。如果相等，更新该节点的值。
    5. 如果第一个节点是红黑树节点，调用 putTreeVal 方法将键值对插入到红黑树中。
    6. 如果第一个节点是链表节点，遍历链表。如果找到相等的键，更新该节点的值；如果遍历到链表末尾仍未找到相等的键，插入新节点。如果链表长度达到 8，调用 treeifyBin 方法将链表转换为红黑树。
    7. 如果插入的键已经存在，返回旧值；否则，返回 null 。
    8. 如果键值对数量超过扩容阈值，调用 resize 方法进行扩容。

注意： 上述的桶指的是 数组的某一个元素 ，可以是单一值，也可以是链表，也可以是红黑树，毕竟HashMap1.8之后的数据结构就是数组+链表+红黑树。

核心方法 - get

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) {
            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;
}
  • get 方法用于根据键获取对应的值。
  • getNode 方法是 get 方法的具体实现，它的主要步骤如下：
    1. 计算键的哈希值，并根据哈希值找到对应的桶位置。
    2. 如果桶不为空，检查第一个节点是否与要查找的键相等。如果相等，返回该节点。
    3. 如果第一个节点是红黑树节点，调用 getTreeNode 方法在红黑树中查找键值对。
    4. 如果第一个节点是链表节点，遍历链表，查找与要查找的键相等的节点。如果找到，返回该节点；否则，返回 null 。

核心方法 - 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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        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)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    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;
}
  • resize 方法用于扩容或初始化桶数组。
  • 它的主要步骤如下：
    1. 计算新的容量和扩容阈值。
    2. 创建一个新的桶数组。
    3. 将旧桶数组中的键值对重新分配到新桶数组中。
    4. 返回新的桶数组。

在 HashMap 中，哈希冲突是指不同的键通过哈希函数计算得到了相同的哈希值，从而被映射到了哈希表的同一个位置。 HashMap 主要使用 链地址法（Chaining——拉链法） 来解决哈希冲突，并且在特定条件下会将链表转换为红黑树以提高查找效率。

https://i-blog.csdnimg.cn/direct/5e7d9dbc1ed44c7ca5499f4fcf1046ef.png

总结

HashMap 通过哈希表实现了快速的键值对查找和插入操作。它使用链表和红黑树来处理哈希冲突，当链表长度达到一定阈值时，将链表转换为红黑树，以提高查找效率。同时， HashMap 会在键值对数量达到扩容阈值时进行扩容操作，以保证哈希表的性能。

更新于 2025-03-16
 算法, 哈希算法
返回 | 主页