关于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 的幂作为哈希表的大小。

数据结构

JDK 8版本的HashMap底层数据结构是数组+链表/红黑树结构，具体原因是：

    /**
     * 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[] table;

这是 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 implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;
 
        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
}

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

/**
 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
 * extends Node) so can be used as extension of either regular or
 * linked node.
 */
static final class TreeNode extends LinkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node next) {
        super(hash, key, val, next);
    }
 
    /**
     * Returns root of tree containing this node.
     */
    final TreeNode root() {
        for (TreeNode r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
 
}

这是 HashMap 内部定义的静态嵌套类 TreeNode，它是红黑树结构的节点。在 HashMap 中，当链表中的元素数量超过一定阈值时，会将链表转换为红黑树，以提高查找性能。

因此，transient Node[] table; 存储了实际的数据，static class Node 表示链表结构的节点，而 static final class TreeNode 表示红黑树结构的节点。这些组合在一起实现了 HashMap 数据结构的数组+链表（红黑树）的形式。

Hash

如果说HashMap的数据结构是其实现功能的基础，那么HashMap的Hash方法则是HashMap实现查找、插入的保障。

HashMap 并不是直接获取 key 的 hashCode 作为 hash 值的，它会通过一个扰动函数（所谓扰动函数指的是HashMap的hash方法）进行一些列位运算和混合操作，使得最终的哈希值更加均匀的分布在哈希表的桶中。使用hash方法就是为了减少hash碰撞的概率且提高HashMap的性能。

//扰动函数
static final int hash(Object key) {
	//用于存储key对应的hash码
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 
//等同于:
int h;
//当key是null时，hash值默认是0，即HashMap只能有一个为Null的key
if (key == null) {
    h = 0;
} else {
    h = key.hashCode();
}
//进行异或操作并将结果赋值给 h
return h = h ^ (h >>> 16);

构造方法

HashMap的类属性和构造方法：

  private static final long serialVersionUID = 362498820763181265L;
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1