Java基础之 JDK8 HashMap 源码分析（中间写出与JDK7的区别）

导言

1. HashMap 的源码分析，是面试中经常问到的地方，这也是写这篇博文的重要原因之一。
2. 源码中有很多基础知识，是平时用不到的，比如位运算法，所以这里第一节就是先了解和学习一下位运算符。

一、基础铺垫

导言中也说了，基础知识有位运算法，位运算符的基础知识又与原码、反码、补码紧密相关，所以首当其冲的也要了解一下原码、反码、补码的基础知识。网上有比较好的资料，我也就不总结了，直接贴上他们的链接了

1. 文档学习

这几篇博文质量都很高，值得细细观看～

1. 知乎上的文章：原码、反码、补码的基础了解
2. 位运算法的基础了解
3. java中常用的位运算符及其应用

2. 总结知识点

1. Java基础之位运算法

位运算 就是直接对整数在内存中的二进制位进行操作，针对与int类型进行操作
Java中常用的位运算符有以下7种：

• 左移（ << ） 整体左移，右边空出位补零，左边位舍弃 （-4 << 1 = -8）
• 右移（ >> ） 整体右移，左边空出位补零或补1（负数补1，正数补0），右边位舍弃 （-4 >> 1 = -2）
• 无符号右移（ >>> ）同>>,但不管正数还是负数都左边位都补0 （-4 >>> 1 = 2147483646）
• 与（ & ）每一位进行比较，两位都为1，结果为1，否则为0（-4 & 1 = 0）
• 或（ | ）每一位进行比较，两位有一位是1，结果就是1（-4 | 1 = -3）
• 非（ ~ ） 每一位进行比较，按位取反（符号位也要取反）（~ -4 = 3）
• 异或（ ^ ）每一位进行比较，相同为0，不同为1（^ -4 = -3）

3. 运算法-细节

1. 位运算是针对整数的二进制进行的位移操作
2. 整数 32位 , 正数符号为0，负数符号为1。十进制转二进制 不足32位的，最高位补符号位，其余补零
3. 在Java中，整数的二进制是以补码的形式存在的
4. 位运算计算完，还是补码的形式，要转成原码，再得出十进制值
5. 正数：原码=反码=补码 负数：反码=原码忽略符号位取反, 补码=反码+1

例如：十进制4 转二进制在计算机中表示为（补码） 00000000 00000000 00000000 00000100

例如：十进制-4 转二进制在计算机中表示为（补码） 11111111 11111111 11111111 11111100

负数转二进制过程（以-4为例）

1、原码：10000000 00000000 00000000 00000100（转二进制，最高位为符号位）  
2、反码：11111111 11111111 11111111 11111011（符号位不变，其余取反）  
3、补码：11111111 11111111 11111111 11111100（反码+1）

-4 << 1 计算过程

1、-4 补码  11111111 11111111 11111111 11111100  
2、左移一位 11111111 11111111 11111111 11111000 （这时候还是补码）
# 如果最高位符号位为0，就不需要继续操作了，因为正数的补码=原码，如果最高位是1，继续往下走
3、转成反码 11111111 11111111 11111111 11110111 （补码-1）  
4、转成原码 10000000 00000000 00000000 00001000 （忽略符号位取反）  
5、转十进制 -8

二、HashMap 源码分析

1. jdk对应

jdk7版本是：数组+链表
jdk8版本是：数组+链表 or 数组+红黑树

HashMap 的 源码主要分析和学习有下面几个点

• 常量（6个）
• 构造函数（4个）
• put() 函数
• get() 函数
• 扩容机制
• 其他知识点
  1. 哈希函数
  2. 哈希冲突
  3. 红黑树

2. jdk8 HashMap 中常量解析

// 默认的容量大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大的容量 为2 的 30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的加载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 与JDK7区别：jdk8专有，红黑树。 链表的阈值大雨8的时候，转化为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 与JDK7区别：jdk8专有，红黑树。 链表还原阈值，HashMap扩容时，会重新计算m，红黑树中的数量小于6时，红黑树转化为 链表 的结构
static final int UNTREEIFY_THRESHOLD = 6;

// 与JDK7区别：jdk8专有，红黑树。当哈希表中的容量大于64时，允许链表转化为红黑色。
// 存储箱可以树化的最小表容量。（否则，如果bin中的节点太多，则会调整表的大小。）应至少为4*TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;

3. jdk8 HashMap 构造函数解析

按源码顺序 拿过来的代码

a、HashMap(int initialCapacity, float loadFactor)

可以自定义初始容量和加载因子

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 如果自定义的容量 大于 最大的容量，则使用默认的最大容量             
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 初始化加载因子
    this.loadFactor = loadFactor;
    // 与JDK7区别：与JDK7功能一致，JDK7名为，jdk8换了一个名称。将当前桶的大小变为2的幂。
    this.threshold = tableSizeFor(initialCapacity);
}

// 返回给定目标容量的二次方大小。
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

b、HashMap(int initialCapacity)

仅自定义初始化容量大小，使用默认的加载因子，还是调用的上一节的有参构造函数

public HashMap(int initialCapacity){
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

c、HashMap()

无参构造函数
默认的加载因子0.75，默认的容量176

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

d、HashMap(Map<? extends K, ? extends V> m)

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

4. jdk8 HashMap put方法 解析

a、put(K key, V value)

public V put(K key, V value) {
    // 四个参数，第一个hash()值，第四个参数表示如果该key存在值，
    // 如果为null的话，则插入新的value，最后一个参数，在hashMap中没有用，可以不用管，使用默认的即可
    return putVal(hash(key), key, value, false, true);
}

b、hash(Object key)

// hash():哈希函数，根据key值通过hash()函数计算出哈希值，找到对应的table当中的位置。
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

c、putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab 哈希数组， p: 该哈希桶的首节点， n: hashmap 的长度， i:计算出的数组下标
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 先判断，然后获取长度 并 进行扩容，使用的是懒加载，table 一开始是没有加载的，等put后才开始加载
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /**
    计算插入存储的数组索引i：根据键值key计算的hash值得到 i
        此处的数组下标方式 i=(n - 1) & hash, 同JDK 1.7 中的 indexFor()一致，JDK8变成了一句话
    插入时，需判断是否存在Hash冲突：
        若不存在（即当前tab[i]==null）,则直接在该数组位置新建节点，插入完毕
    **/
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 插入新节点
        tab[i] = newNode(hash, key, value, null);
    // 否则，代表存在Hash冲突，即当前存储位置已存在节点，则依次往下判断：
    else {
        // e: 临时节点的作用， k 存放该当前节点的key
        Node<K,V> e; K k;
        // 第一种：当前位置的key是否与需插入的key相同，若相同 则 直接用 新value 覆盖 旧value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 第二种：判断需插入的数据结构是否为 红黑树 or 链表发生哈希冲突的几种情况
        else if (p instanceof TreeNode)
            /**
            如果是红黑树的节点，向红黑树插入 or 更新数据（键值对）
            过程：遍历红黑树 判断该节点的key 是否与需插入的key相同：
                a、若相同，则新value 覆盖 旧value
                b、若不相同，则插入
            **/
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 第三种：hash值 不等于首节点，不为红黑树的节点，则为链表的节点
        else {
            // 遍历该链表
            for (int binCount = 0; ; ++binCount) {
                // 如果找到尾部，则表明添加的 key-value 没有重复，在尾部进行添加
                if ((e = p.next) == null) {
                    // 与JDK7区别，JDK8是在链表尾部添加，JDK7在头部添加
                    p.next = newNode(hash, key, value, null);
                    // 判断是否要转换为红黑树结构 TREEIFY_THRESHOLD值为8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果 链表中有重复的 key ,e 则为当前重复的节点，结束循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 有重复的 key,则用待插入值进行覆盖，返回旧值。
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 到了此步骤，则表明待插入的key-value 是没有key 的重复，因为插入成功e节点的值为null
    // 修改次数 +1
    ++modCount;
    // 实际长度 +1，判断是否大于临界值，大于则扩容
    if (++size > threshold)
        resize();
    // 调用 LinkedHashMap的实现方法，其实什么也没做，因为这里 evict=true
    afterNodeInsertion(evict);
    // 添加成功
    return null;
}

d、resize() 扩容

e、putTreeVal(this, tab, hash, key, value) 插入到红黑树

f、treeifyBin(tab, hash);链表转红黑树

5. jdk8 HashMap get方法 解析

a、get(Object key)

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

b、getNode(int hash, Object key)

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) {
        // 判断第一个key是否为想要查询的key，如果是则返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 判断如果第一个节点的next节点不为null
        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;
}

c、getTreeNode(hash, key) 红黑树查询

final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

d、find(int h, Object k, Class<?> kc)红黑树查询节点

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}