HashMap是 Java 调集结构中的一个常用类，完结了依据哈希表的键值对存储和检索功用。它供应了高效的插入、查找和删去操作，并且在大多数场景下具有常数时间复杂度（O(1)）。

本文主要对HashMap中一些中心概念进行解说和阐明，其他基本概念能够先参看这篇文章：java根底_吃透Java调集系列九：HashMap

要害概念

哈希码（Hash Code）

在HashMap中，每个键都有一个对应的哈希码，它是依据键的hashCode()方法生成的。哈希码用于承认键值对在哈希表中的存储方位。
比方其间get方法，是通过Key的Hash方法去找其间的bucket的

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

hash方法也不是朴素的key的hashCode，详细如下

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

通过getNode能够了解到hashMap的数据结构是hash数组 链表 红黑树（JDK8下）

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

哈希表（Hash Table）

HashMap内部运用哈希表数据结构来存储键值对。哈希表是一个数组，每个元素称为桶（Bucket），通过哈希码将键值对映射到桶的索引方位。哈希表供应了快速的存储和检索操作。

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

桶（Bucket）

哈希表中的每个元素称为桶，它能够存储一个或多个键值对。当多个键值对的哈希码相一起，它们会被存储在同一个桶中，构成一个链表或红黑树结构。
对应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;
    }
}

负载因子（Load Factor）

HashMap运用负载因子来操控哈希表的填充程度。负载因子是指其时元素数量与哈希表容量的比值，当元素数量逾越负载因子和其时容量的乘积时，会触发扩容操作。

链表（Linked List）和红黑树（Red-Black Tree）

在 JDK 8 中的HashMap完结中，当链表长度逾越阈值时，会将链表转化为红黑树，然后提高在链表较长时的查找效率。

  1. 链表转化为红黑树：

    • 当链表长度到达TREEIFY_THRESHOLD（默许为 8）时，会将链表转化为红黑树。
    • 转化过程中，首要会创立一个新的红黑树节点作为根节点，并将链表中的元素逐个增加到红黑树中，坚持相对次第不变。
    • 在增加过程中，假如发现链表中的元素现已存在于红黑树中，则将链表元素的值更新到红黑树节点中。
    • 转化完结后，本来的链表将被丢掉，以节约内存。

  2. 红黑树转化为链表：

    • 当红黑树中的节点数量削减到UNTREEIFY_THRESHOLD（默许为 6）以下时，会将红黑树转化回链表。
    • 转化过程中，首要会将红黑树中的节点逐个遍历，并按照相对次第增加到链表中。
    • 转化完结后，本来的红黑树将被丢掉，以节约内存。

equals 方法和 hashCode 方法

为了正确存储和检索键值对，键的类必须正确完结equals和hashCode方法。equals方法用于判别键是否相等，hashCode方法用于生成键的哈希码。

参看

一文吃透hashmap的宿世与今生
java根底_吃透Java调集系列九：HashMap