<commit_before>---
layout:     post
title:      "JDK 1.8 HashMap源码解析"
subtitle:   "领略JDK大师设计，了解HashMap的基本工作原理"
author:     "Chris"
header-img: "img/post-bg-1.jpg"
tags:
    - Java
    - 源码研读
---

## 简介

JDK 1.8的HashMap相较于JDK 1.7有了更多的优化，单纯在体量上HashMap的代码就足足增加了一倍。这些体量的增加更多的是底层的一些优化，如红黑树的引入和扩容时的rehash优化等。

![](https://4.bp.blogspot.com/-qWRZSkyBDGc/V6M41S237DI/AAAAAAAAGxQ/xKS9RMu57tAsLHPFzw7JfSTq6tLoBvIjACLcB/s1600/How%2Bdoes%2BHashMap%2Bworks%2Bin%2BJava%2B8.jpg)

## 内部结构

```java
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;

    transient Node<K,V>[] table;
    transient int size;
    int threshold;
    final float loadFactor;

  	// 链表节点
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
  
  	// 红黑树节点
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
    }
}
```

- DEFAULT_INITIAL_CAPACITY

  初始化HashMap时的默认容量，无论何时table的容量必然为2^n，如果在初始化时所传入的值不满足该条件，HashMap将会往上调节大小以达到2^n的要求。

- MAXIMUM_CAPACITY

  HashMap的最大容量为1 << 30，达到此数值后将不再扩容。

- DEFAULT_LOAD_FACTOR

  通常译为“负载因子”，是时间与空间上的一种平衡。

- TREEIFY_THRESHOLD

  将链表树化的阈值，这个值为8，表示如果一个哈希桶上的链表长度大于等于8后将**有机会尝试**将其转换成红黑树，但实际的转换条件还要根据下面的MIN_TREEIFY_CAPACITY来进行综合判断。

- MIN_TREEIFY_CAPACITY

  转换成红黑树时的最小容量，最小的值也应该为TREEIFY_THRESHOLD * 4，这个值默认为64，即如果table.length如果小于64的话则不选择将哈希桶转换成红黑树，而是选择扩容。

- table

  哈希表，在JDK1.8中是`Node<K,V>[]`，在JDK1.7是`Entry<K,V>[]`

- size

  实际上HashMap的实际元素的个数

- threshold

  进行扩容的容量阈值 (capacity * load factor)

- loadFactor

  哈希表的负载因子，一般默认为DEFAULT_LOAD_FACTOR，即0.75f

## 取模的位运算

取模同样也可以被位运算所替代，当除数为2^n时，且被除数不小于0的时候，以下等式成立

`x % 2^n == x & (2^n - 1)`

我们列举几个例子（x不为负数）

```java
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7
```

更多关于位运算取模的信息可以翻阅一下维基百科的[相关词条](https://en.wikipedia.org/wiki/Modulo_operation#Performance_issues)。

上述的操作是HashMap的优化点之一，同样也是HashMap的capacity为什么取2^n的原因之一。

## 负载因子

起初我学习的时候会有以下的疑问：为什么会有负载因子这个东西？不应该是物尽其用吗？其实当负载因子比较大的时候的确能够起到物尽其用的作用，但相对地哈希桶的长度也会增加，查找的效率就会降低，这是时间换空间；如果负载因子较小，则会引起更多的扩容，对于原本的哈希桶在扩容之后会有相应地减少长度，从而让哈希表有更高的检索效率，这是典型的空间换时间。HashMap中的负载因子默认为0.75，对于该数值我也是持有“默认即有理”的态度，一般也不会更改。

## 内部实现

以下将会介绍HashMap中的哈希计算、添加元素和扩容这几项操作。<commit_msg>mod the post of hashmap<commit_after>---
layout:     post
title:      "JDK 1.8 HashMap源码解析"
subtitle:   "领略JDK大师设计，了解HashMap的基本工作原理"
author:     "Chris"
header-img: "img/post-bg-1.jpg"
tags:
    - Java
    - 源码研读
---

## 简介

JDK 1.8的HashMap相较于JDK 1.7有了更多的优化，单纯在体量上HashMap的代码就足足增加了一倍。这些体量的增加更多的是底层的一些优化，如红黑树的引入和扩容时的rehash优化等。

![](https://4.bp.blogspot.com/-qWRZSkyBDGc/V6M41S237DI/AAAAAAAAGxQ/xKS9RMu57tAsLHPFzw7JfSTq6tLoBvIjACLcB/s1600/How%2Bdoes%2BHashMap%2Bworks%2Bin%2BJava%2B8.jpg)

## 内部结构

```java
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;

    transient Node<K,V>[] table;
    transient int size;
    int threshold;
    final float loadFactor;

  	// 链表节点
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
  
  	// 红黑树节点
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
    }
}
```

- DEFAULT_INITIAL_CAPACITY

  初始化HashMap时的默认容量，无论何时table的容量必然为2^n，如果在初始化时所传入的值不满足该条件，HashMap将会往上调节大小以达到2^n的要求。

- MAXIMUM_CAPACITY

  HashMap的最大容量为1 << 30，达到此数值后将不再扩容。

- DEFAULT_LOAD_FACTOR

  通常译为“负载因子”，是时间与空间上的一种平衡。

- TREEIFY_THRESHOLD

  将链表树化的阈值，这个值为8，表示如果一个哈希桶上的链表长度大于等于8后将**有机会尝试**将其转换成红黑树，但实际的转换条件还要根据下面的MIN_TREEIFY_CAPACITY来进行综合判断。

- MIN_TREEIFY_CAPACITY

  转换成红黑树时的最小容量，最小的值也应该为TREEIFY_THRESHOLD * 4，这个值默认为64，即如果table.length如果小于64的话则不选择将哈希桶转换成红黑树，而是选择扩容。

- table

  哈希表，在JDK1.8中是`Node<K,V>[]`，在JDK1.7是`Entry<K,V>[]`

- size

  实际上HashMap的实际元素的个数

- threshold

  进行扩容的容量阈值 (capacity * load factor)

- loadFactor

  哈希表的负载因子，一般默认为DEFAULT_LOAD_FACTOR，即0.75f

## 取模的位运算

取模同样也可以被位运算所替代，当余数为2^n时，且被余数不小于0的时候，以下等式成立

`x % 2^n == x & (2^n - 1)`

我们列举几个例子（x不为负数）

```java
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7
```

更多关于位运算取模的信息可以翻阅一下维基百科的[相关词条](https://en.wikipedia.org/wiki/Modulo_operation#Performance_issues)。

上述的操作是HashMap的优化点之一，同样也是HashMap的capacity为什么取2^n的原因之一。

## 负载因子

起初我学习的时候会有以下的疑问：为什么会有负载因子这个东西？不应该是物尽其用吗？其实当负载因子比较大的时候的确能够起到物尽其用的作用，但相对地哈希桶的长度也会增加，查找的效率就会降低，这是时间换空间；如果负载因子较小，则会引起更多的扩容，对于原本的哈希桶在扩容之后会有相应地减少长度，从而让哈希表有更高的检索效率，这是典型的空间换时间。HashMap中的负载因子默认为0.75，对于该数值我也是持有“默认即有理”的态度，一般也不会更改。

## 内部实现

以下将会介绍HashMap中的哈希计算、添加元素和扩容这几项操作。
{'fraction_non_alphanumeric': 0.11315789473684211, 'fraction_numerical': 0.02894736842105263, 'mean_word_length': 4.413021363173957, 'pattern_counts': {'":': 0, '<': 45, '<?xml version=': 0, '>': 33, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5556047', 'n_tokens_mistral': 3206, 'n_tokens_neox': 3467, 'n_words': 327}