【编程基础】字典查找树

发表于 更新于 分类于 本文字数： 7.5k 阅读时长 ≈ 27 分钟

字典查找

其实做 Java 的应该都知道 Map 和 HashMap，这个类其实就是字典查找实现。他的前身是 Dictionary 以及 Hashtable。因为之前的类库，大部分方法都被加上 synchronized 标记，导致这些类库在运行的时候，效率都不高。所以后期都是使用 HashMap 这一类来进行操作。 不过现在我们要看的是 字典 是什么，我们看书的时候基本都有一个东西叫做 目录，这个东西就可以用来查询哪个标题大概在哪一页开始，而我们程序所说的就是这个东西，一个类似于 目录 的 Key-Value 对应的结构，当我们为了实现一些需求的时候需要将一类数据作为 Key，另外一类数据作为 Value 存入从而实现计算的时候，就可以使用 字典 这种数据结构了。 而实现 字典 也有不同方式，我们还是慢慢的一步一步接近，目的就是为了设计一个高性能的字典。 那 API 我们可以定义类似于 Map 接口，然后使用不同的结构来实现我们的功能，首先我们先定义我想要的接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
public interface Dictionary<K extends Comparable<K>, V> {

  /**
   * 存储键和值，键值均不允许为null.
   *
   * @param key 键.
   * @param val 值.
   */
  void put(K key, V val);

  /**
   * 根据键获取对应的值，如果不存在返回null.
   *
   * @param k
   * @return
   */
  V get(K k);

  /**
   * 删除指定键的值.并返回被删除的值.
   *
   * @param key
   * @return
   */
  V delete(K key);

  /**
   * 判断一个键是否存在.
   *
   * @param key
   * @return
   */
  boolean contains(K key);

  /**
   * 当前字典是否为空.
   *
   * @return
   */
  boolean isEmpty();

  /**
   * 返回当前字典的长度.
   *
   * @return
   */
  int size();

  /**
   * 最小的键.
   *
   * @return
   */
  K min();

  /**
   * 最大的键.
   *
   * @return
   */
  K max();

  /**
   * 小于或者等于的最大的指定Key的键
   *
   * @param key
   * @return
   */
  K floor(K key);

  /**
   * 大于或等于的最小的指定的Key键
   * @param key
   * @return
   */
  K ceiling(K key);

  /**
   * 小于指定Key键的数量.
   *
   * @param key
   * @return
   */
  int rank(K key);

  /**
   * 查询第k个键.
   *
   * @param k
   * @return
   */
  K select(int k);

  /**
   * 返回所有键的迭代器.
   *
   * @return
   */
  Iterable<K> keys();

}

顺序查找

那最简单的就是使用一个 数组 或者 链表 来做存储，然后我们需要的所有操作，都需要通过遍历这个存储来做。由于操作数量还是蛮多的，用 链表 可以很简单的操作，所以我们直接使用链表来做了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class UnorderedDictionary<K extends Comparable<K>, V> implements Dictionary<K, V> {

  private Node first;

  /**
   * 定义Node内部结构
   * 用来记录Key和Value
   * 顺带有个next指针指向下一条.
   */
  private class Node {
    K key;
    V val;
    Node next;

    public Node(K key, V val, Node next) {
      this.key = key;
      this.val = val;
      this.next = next;
    }
  }

  public void put(K key, V val) {
    Node newNode = new Node(key, val, null);
    if (first != null) {
      // 尝试命中同样的Key
      for (Node f = first; f != null; f = f.next) {
        if (f.key.equals(key)) {
          f.val = val;
          return;
        }
      }
      // 没有命中，则将链表最后一个设置为新的Node
      Node f = first;
      while (f.next != null) {
        f = f.next;
      }
      f.next = newNode;
    }
    else {
      first = newNode;
    }
  }

  public V get(K k) {
    if (first == null) {
      return null;
    }

    for (Node f = first; f != null; f = f.next) {
      if (f.key.equals(k)) {
        return f.val;
      }
    }
    return null;
  }

  public static void main(String[] args) {
    Dictionary<Integer, Integer> unordered = new UnorderedDictionary<>();
    for (int i = 0; i < 100_000; i++) {
      unordered.put(i, i);
    }
    System.out.println("开始查找...");
    long start = System.nanoTime();
    Integer val = unordered.get(10_000 - 1);
    System.out.println("查找到：" + val + " 共用时" + (System.nanoTime() - start));
  }

  // ......
}
// ------
开始查找...
查找到：999 共用时143015

OK，没有任何辅助的结构，单纯简单粗暴的进行循环遍历，get(K k) 每次都需要通过遍历整个链表，这种实现方式无疑效率是最低的，因为随着链表的长度增加，时间成本将会原来越长。这种好比 选择排序 一样，遍历每个元素与后面的元素依次遍历。这就可以通过证明，我们查找第一个元素需要比较 1次，查找第二个元素需要比较 2次，而如果我们元素刚好在最后一位的话就需要 1 + 2 + 3 + ... + N = N / 2 而 put(K key, V val) 更加离谱，每次加入都需要循环整个链表。

二分查找

二分查找比较简单，我们可以使用一个 Key[] 和 Value[] 来存储 Key和Value。然后先查询 Key 对应的下标，然后直接命中 Value[indexOf(Key)] 即可，查找 Key 的过程我们就可以使用 二分查找 的方法来查找。至于插入，我们需要根据顺序来进行整容，将原有的 Key和Value数组 进行整理再将新的值插入到对应的位置，查找的过程也是使用到了 二分查找法。 实现并不太难，不写了-,-

二叉查找树

那么，通过上面的实践，我们可以再进一步优化成树形结构（其实编程貌似万物都可用树-,-），首先我们先用简单的 二叉查找树 来做，二叉查找 具有以下的特点：

  1. 所有节点的左节点的值都比当前节点小；
  2. 所有节点的右节点的值都比当前节点大；
  3. 左右子树也是二叉查找树；
  4. 没有键值相等的节点。

一颗典型的 二叉查找树：

那么我们可以很简单的写出实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class BSTDictionary<K extends Comparable<K>, V> implements Dictionary<K, V> {

  private Node root;

  private class Node {
    K key;
    V val;
    Node left, right;

    public Node(K key, V val) {
      this.key = key;
      this.val = val;
    }
  }

  @Override
  public void put(K key, V val) {
    root = put(root, key,val);
  }

  private Node put(Node n, K key, V val) {
    if (n == null) {
      return new Node(key, val);
    }

    int compare = key.compareTo(n.key);
    if (compare == 0) {
      n.val = val;
    } else if (compare > 0) {
      n.right = put(n.right, key, val);
    } else {
      n.left = put(n.left, key, val);
    }
    return n;
  }

  @Override
  public V get(K k) {
    return get(root, k);
  }

  private V get(Node n, K key) {
    if (n == null) {
      return null;
    }

    int compare = key.compareTo(n.key);
    if (compare == 0) {
      return n.val;
    } else if (compare > 0) {
      return get(n.right, key);
    } else {
      return get(n.left, key);
    }
  }

  public static void main(String[] args) {
    Dictionary<Integer, Integer> unordered = new BSTDictionary<>();
    for (int i = 0; i < 1_000; i++) {
      // 因为目前我们在put的时候并没有对树进行整理
      // 所以防止构建的树形总是最差情况，加入随机数
      unordered.put((int) (i + 100 * Math.random()), i);
    }
    System.out.println("开始查找...");
    long start = System.nanoTime();
    Integer val = unordered.get(1_000 - 1);
    System.out.println("查找到：" + val + " 共用时" + (System.nanoTime() - start));
  }
}
// ------
开始查找...
查找到：915 共用时73567

上面的代码是一个及其简单的实现，我们也加入了假设，假设每次插入的 Key 总是均匀分布的。不然这棵树就会变成这样的：

不仅仅插入的时候会导致这种情况，当我们调用 del 删除节点的时候，也可能会出现这种情况，所以怎么维护这棵树的最佳查找性能，就成了现在的话题了。接下来的结构基本都会围绕这个问题来展开。

平衡查找树（2-3树）

从上面的 二叉查找树 我们可以看到，即使随机的情况下树的性能还是不错的，但是如果我们顺序插入就会导致上面最后一个图中最坏的情况，当我们需要查询 节点4 的时候，我们一直在右树查找，这么看来性能已经达到了线性的程度了。那这样下去肯定是不行的（带去河边？） 所以有了 平衡查找树，又称为 2-3树，为啥，因为在上面 二叉查找树 中，节点都是 2节点，何为 2，因为每个节点只有2个子节点。那么我们现在插入一个概念就是 3节点，意思就是有些节点他有 3个 子节点。如图：

我们可以看到，在上面这棵树中，存在 2 个 3节点，3节点 左边的节点是比节点左边的值小的节点，中间则是介于 3节点 两个数值之间，右边就是比 右边的数 大的节点了。那么这种有什么好处，答案就是整容方便。那么怎么整容呢，那就出现两种情况了：

如果查找插入的节点是一个 2节点

如果插入的节点是一个 2节点，那么操作显然要简单很多，我们只需要简单把原来 2节点 转换为 3节点 即可。

如果查找插入的节点是一个 3节点

那如果我们需要插入的数是 60，就会碰到 59-69 这个节点，那能咋办，往上生长呗：

那如果碰上父父父节点到根节点都是 3节点 的情况，树的高度就会增加 1：

红黑树

直接进入红黑树，红黑树如果没有上面 2-3树 的理解的话，完全不知道是什么鬼东西，不过现在看来一切将会清晰： 首先我取上面动图一颗左子树来示例：

用红黑树表示：

然后再把红线拉平：

那么很显然，她就是一颗 2-3树 了，只不过通过连接线的颜色来表示他是 2节点 还是 3节点。 那么很显然为了编码方便，红黑树 加入一些定义：

  1. 红链接 均为 左链接；
  2. 没有任何一个节点同时和 两个红链接 相连；
  3. 所有叶子都是黑色（叶子是NUIL节点）；
  4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点；
  5. 根节点是黑色。

同样的，我们需要一个内部 Node 类来表示节点：

1
2
3
4
5
6
7
8
private class Node {
  K key;
  V val;
  Node left, right;
  // 如果父节点指向我自己的线是红色的
  // 则该值为true
  boolean isRed;
}

红黑树的增删

当我们对树进行插入操作或者删除操作的时候，在 2-3树 说到这棵树就需要通过变型，让树来达到平衡，那么 红黑树 同样也需要进行变型，而变型就是通过 旋转 来做的。 先来解释什么是旋转，旋转又分为 左旋转 和 右旋转：

那么最后这棵子树就变成这个样子：

那右旋转基本和左旋一样，这个动图比较好画-,-：

什么时候需要旋转： 其实每次插入的时候，一般都需要旋转，而旋转的地方，就是我们插入的那一小部分树： 那我分别插入最小值、最大值和中间值来看这棵树：

  • 插入最小值

那么我们现在要插入 9：

出现了两个红色的左连接，那么我们右旋转一次：

出现了 10节点 有两个红色链接，那么我们只需要将 10节点 和 根节点 转换颜色即可：

对应的转换颜色的代码：

1
2
3
4
5
private void changeColor(Node node) {
  node.isRed = true;
  node.left.isRed = false;
  node.right.isRed = false;
}

那 20节点 和 25节点 之间应该是红色才对？没关系，如果我们插入的值是 10 - 20 之间的数值的时候，他不就平衡了咩~

  • 插入中间值

那先在刚好，在上一节我们说插入 10 - 20 之间的数值的时候就会平衡，那我们现在就来插入 15：

  • 插入最大值

比方说插入 101：

出现了右红色链接，这时候需要对 100节点 进行一次左旋转：

即可达到稳定。 那现在我们就可以来编写 put 的代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
public class RBTDictionary<K extends Comparable<K>, V> implements Dictionary<K, V> {

  private Node root;

  private class Node {
    K key;
    V val;
    Node left, right;
    boolean isRed;

    public Node(K key, V val, boolean isRed) {
      this.key = key;
      this.val = val;
      this.isRed = isRed;
    }
  }

  /**
   * 左旋转
   * @return
   */
  private Node routateLeft(Node node) {
    // 首先拿到右边的节点
    Node right = node.right;
    // 把右节点的左节点连接到被旋转的父节点的右边；
    node.right = right.left;
    // 然后需要将右边的节点替换成当前传递进来的父节点
    right.left = node;
    // 保留之前父节点的颜色
    right.isRed = node.isRed;
    // 把之前父节点的颜色设置为红色
    node.isRed = true;
    return right;
  }

  /**
   * 右旋转
   * @return
   */
  private Node rotateRight(Node node) {
    // 首先拿到左节点
    Node left = node.left;
    // 把左节点的右边连接到被旋转的父节点的左边；
    node.left = left.right;
    // 右边则是传递的父节点
    left.right = node;
    // 左节点称为父节点了，需要保留原来的颜色
    left.isRed = node.isRed;
    // 原来的节点变成右节点了，所以需要染色
    node.isRed = true;
    // 返回旋转之后的左节点
    return left;
  }

  private void changeColor(Node node) {
    node.isRed = true;
    node.left.isRed = false;
    node.right.isRed = false;
  }

  private boolean isRed(Node node) {
    if (node == null) {
      return false;
    }
    return node.isRed;
  }

  @Override
  public void put(K key, V val) {
    root = put(root, key, val);
    root.isRed = false;
  }

  private Node put(Node node, K key, V val) {
    if (node == null) {
      return new Node(key, val, true);
    }

    // 比较大小，看是要在左边插入还是右边插入
    int compare = key.compareTo(node.key);
    if (compare < 0) {
      node.left = put(node.left, key, val);
    } else if (compare > 0) {
      node.right = put(node.right, key, val);
    } else {
      node.val = val;
    }

    // 如果出现红色右链接，左旋转
    if (isRed(node.right) && !isRed(node.left)) {
      node = routateLeft(node);
    }
    // 如果连续出现两个左红链接，右旋转
    if (isRed(node.left) && isRed(node.left.left)) {
      node = rotateRight(node);
    }
    // 如果左右都是红色链接，需要将红色网上传递给父节点，当前链接均变成黑色
    if (isRed(node.left) && isRed(node.right)) {
      changeColor(node);
    }
    return node;
  }

  @Override
  public V get(K k) {
    return get(root, k);
  }

  private V get(Node n, K key) {
    if (n == null) {
      return null;
    }

    int compare = key.compareTo(n.key);
    if (compare == 0) {
      return n.val;
    } else if (compare > 0) {
      return get(n.right, key);
    } else {
      return get(n.left, key);
    }
  }

  public static void main(String[] args) {
    Dictionary<Integer, Integer> dic = new RBTDictionary<>();
    for (int i = 0; i < 20; i++) {
      dic.put(i, i);
    }
  }

  // ......
}

红黑树的查找

红黑树的查找过程上面代码已经体现，跟 普通二叉查找树 的算法一致。

红黑树的删除

红黑树的删除，可能会使一个 2节点 的子节点是 NULL，我们为了避免这种事情的发生，需要对树进行调整，分为以下几种情况：

  1. 如果根节点不是 2节点，完成；
  2. 如果当前节点的左节点是 2节点 而兄弟节点不是，则可以从 兄弟节点 借一个过来，然后再做删除处理；
  3. 如果当前节点和兄弟节点都是 2节点，则需要从父节点中借出一个节点来辅助变成 4节点 然后再进行删除。

优秀点

那么 红黑树 我们可以看到跟 普通查找二叉树 的查找算法是一致的，那他优秀在哪里。因为规定了 红黑链接，所以他在插入删除的时候，也需要进行特定操作，但是具体的性能基本上都是 logN。即使在最差的情况下，也可以将保持树形的平衡，并且需要移动的节点很少。

散列表

散列表的说法相信用 Java 的多少有听说过 HashMap 的实现原理，那就是通过一个对象，通过 jvm 给定的 hashCode 进行一系列操作得出来一个数组的下标，那么这个 Key对象 就会被散落在对应的数组下标。

1
2
3
4
5
6
7
8
// j8的HashMap的Hash算法
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 插入的代码片段，通过长度跟hash值计算，得到下标
if ((p = tab[i = (n - 1) & hash]) == null)
  tab[i] = newNode(hash, key, value, null);

那么首先将 hashCode 向右移动 16 位，目的是打乱 hashCode 低位，然后再跟数组长度进行与操作，尽可能的散落均匀。 但是，无论再怎么均匀，总会出现 hash碰撞 的情况。那么就有以下两种方式来进行解决：

HASH碰撞拉链法

我们假设，node[] 是用来存储对象的数组，那么如果我们插入的时候通过计算，得到的数组下标那个位置已经有对象存在了，那这个位置就会形成一个单向链表，即 node.next = newObj，这种就是拉链法，HashMap 在树形化之前也是采用这种方式来解决 Hash碰撞 的问题，那搜索的时候我们就需要拿到下标，然后一步一步 next 的去 equals 再取出对象的 Key对象 和 Value值。

HASH碰撞线性探测法

如果不使用链表来解决碰撞问题的话，那么可以使用数组探测的形式来做，如果插入一个值，这个值的 hash 过以后对应数组的位置上已经存在其他值了，那么将 hash后的 数组下标 自增1（遇到数组尾部折回去头部），然后再插入。查找的时候就需要先得到 hash 后的数组下标，然后使用比较 equals 接下去数组位去探测是否相同，相同则返回。 删除的时候会显得麻烦很多，因为我们在使用线性探测的时候，会使用 null 来标记查找结束，如果简单粗暴的设置为 null，则被删除后面的元素也会顺带着被删除，正确的做法则是：我删除了这个位置上的元素，那后面的相同 hash 的键值都需要被重新排位。

HashMap解析

HashMap 的面试题如此之多，网络上的文章也很多时候我们只看一半，就我目前来说，就知道达到一定阈值的时候，Hash散列表 会被转换成 红黑树，但是怎么转的，我居然是简单的认为将整个 Hash表 都进行树化，目前看来，这是错误的看法哈，其实是 Hash碰撞 的时候，当这个碰撞位的链表达到阈值的时候，只有这个链表被转化为 红黑树。 也就是有时候，你的 HashMap 结构是这样的：

不得不说，jdk 开发者的脑袋真的不是 人做的 orz。

默认容量和平衡因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

  // 默认的平衡因子
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  // 使用空构造器默认的初始化容量，必须是2的倍数
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

  // 全参构造
  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;
    // 会将需要使用的容量整容成2的倍数，为了散列的时候更加均匀
    this.threshold = tableSizeFor(initialCapacity);
  }
  public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }
  public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  }

  // 提供给构造器整形传递容量的方法
  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;
  }
}

这个还算是简单点的，不过需要注意的就是，我们在初始化需要使用的容量的时候，就需要结合我们所需要的容量和计算因子来计算总共需要提供的容量，不然很快就会进入重新拷贝扩容的过程，不过日常我更喜欢使用这个，因为他会帮我算好刚刚好的容量，而且可读性更高：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
使用的时候：Maps.newHashMapWithExpectedSize(list.size());

public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
  return new HashMap<>(capacity(expectedSize));
}
static int capacity(int expectedSize) {
  if (expectedSize < 3) {
    checkNonnegative(expectedSize, "expectedSize");
    return expectedSize + 1;
  }
  if (expectedSize < Ints.MAX_POWER_OF_TWO) {
    return (int) ((float) expectedSize / 0.75F + 1.0F);
  }
  return Integer.MAX_VALUE; // any large value
}

HashMap拉链法

那么我们要实现 Hash冲突，也不是很难，首先我们准备一个类，然后重写 hashCode() 方法总是让他返回一个常亮即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class ABean {

  private String s;

  public ABean(String s) {
    this.s = s;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null  getClass() != o.getClass()) return false;
    ABean aBean = (ABean) o;
    return Objects.equals(s, aBean.s);
  }

  @Override
  public int hashCode() {
    return 1;
  }

  public static void main(String[] args) {
    Map<ABean, Integer> map = new HashMap<>();
    for (int i = 0; i < 16; i++) {
      map.put(new ABean(i + ""), i);
    }
  }

}

接下来看看 put 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

  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;
    // 我们使用的时候，new HashMap() 其实并没有初始化里面的属性
    // 所以我们在第一次put的时候，会进入这个分支，其实就是初始化
    // table[] 和 容量.
    if ((tab = table) == null  (n = tab.length) == 0)
      n = (tab = resize()).length;
    // 拉链法，如果拿到的 table[] 对应下标的位置为null，直接就可以插入了
    if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null);
    else {
      // 进入这个分支就是开始解决冲突的问题：
      Node<K,V> e; K k;
      // hash相同并且equals，说明是同个对象，重新把Value更新
      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 {
        for (int binCount = 0; ; ++binCount) {
          // 如果当前 Node 的下一个是 null，插入到下一个
          if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);

            /* TREEIFY_THRESHOLD = 8;也就是链表长度为8的时候，就会进行红黑树的转换 */
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
              treeifyBin(tab, hash);
            break;
          }
          // 如果下一个 Node 不是 null，并且值相等，则更新这个 Node 的 Value 值
          if (e.hash == hash &&
              ((k = e.key) == key  (key != null && key.equals(k))))
            break;
          p = e;
        }
      }
      // 上面查找后，均在此处更新
      if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent  oldValue == null)
          e.value = value;
        afterNodeAccess(e);
        return oldValue;
      }
    }
    ++modCount;
    // 如果有必要扩容，则重新扩容。
    if (++size > threshold)
      resize();
    afterNodeInsertion(evict);
    return null;
  }

}

HashMap树化

在上面的 putVal 方法中有个很重要的分支，就是 if (binCount >= TREEIFY_THRESHOLD - 1) 这个分支，他表示当 链表 的长度大于 8 的时候，进入树化，不过表面说是树化，其实…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
  * Replaces all linked nodes in bin at index for given hash unless
  * table is too small, in which case resizes instead.
  * 如果表的长度太小了，直接使用扩容方式处理.
  * 如果足够长了（64个，指的是数组的长度而不是我们put的个数），则将表进行树化
  */
final void treeifyBin(Node<K,V>[] tab, int hash) {
  int n, index; Node<K,V> e;
  // 如果 hash数组 的长度 < 64，则直接扩容.
  if (tab == null  (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
  // 判断如果 Node 对应的下标 != null 的时候，开始进行整个数组的替换
  else if ((e = tab[index = (n - 1) & hash]) != null) {
    // 开始循环对应的数组下标，将数组下标从原来的 HashMap$Node 
    // 转换为 HashMap$TreeNode，也就是红黑树结构的节点表示.
    // 下面的操作实际上只是将原来的 HashMap$Node 的 Key和Value 值
    // 读取出来，然后连接每一个节点的前后节点，也就是 prev和next 指针
    TreeNode<K,V> hd = null, tl = null;
    do {
      // 双向链表，也就是说，目前树化的时候还保留之前链表的顺序
      TreeNode<K,V> p = replacementTreeNode(e, null);
      if (tl == null)
        hd = p;
      else {
        p.prev = tl;
        tl.next = p;
      }
      tl = p;
    } while ((e = e.next) != null);
    // 将原来的链表对象替换成当前的树节点对象
    if ((tab[index] = hd) != null)
      // 开始链表节点内的树化
      hd.treeify(tab);
  }
}
// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
  return new TreeNode<>(p.hash, p.key, p.value, next);
}

这个树化函数就都封装在 HashMap$TreeNode 的内部类中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
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
  // 是否是红色节点
  boolean red;
  // next的值永远是null，有这个参数其实是为了能够实现父级的构造器
  TreeNode(int hash, K key, V val, Node<K,V> next) {
    super(hash, key, val, next);
  }

  final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // 两两循环，也就是第0个和第1个参与比较，取大小
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
      next = (TreeNode<K,V>)x.next;
      // 清除左右节点
      x.left = x.right = null;
      // 先确定父节点是第一个
      if (root == null) {
        x.parent = null;
        x.red = false;
        root = x;
      }
      else {
        // 从下标为1的Node开始，均走这个逻辑，意在比较大小
        K k = x.key;
        int h = x.hash;
        Class<?> kc = null;
        for (TreeNode<K,V> p = root;;) {
          // 由于我们改写了hashCode方法让其一直返回1，
          // 所以前两个if尝试比较我们自己手写的hashCode的
          // 时候总是不会进入
          int dir, ph;
          K pk = p.key;
          if ((ph = p.hash) > h)
            dir = -1;
          else if (ph < h)
            dir = 1;
          // 然后尝试使用Comparable比较顺序，但是还是没有得到期望的比较
          else if ((kc == null &&
                    (kc = comparableClassFor(k)) == null) 
                   (dir = compareComparables(kc, k, pk)) == 0)
            // 开始放弃治疗，使用系统级别的hashCode来计算
            dir = tieBreakOrder(k, pk);

          TreeNode<K,V> xp = p;
          // 开始按照红黑树的定义连接左右节点，这个循环也是按照左右子树来遍历
          // 由于上面的没有提供 Compareable接口 的类是根据系统的HashCode来做
          // 计算的，我现在修改 ABean 实现 Compareable接口，并且比较属性（修改为Integer）
          // 来做排序。
          if ((p = (dir <= 0) ? p.left : p.right) == null) {
            x.parent = xp;
            // 小于或者等于，连接左边
            if (dir <= 0)
              xp.left = x;
            // 大于连接右边
            else
              xp.right = x;
            // 开始调整树的平衡
            root = balanceInsertion(root, x);
            break;
          }
        }
      }
    }
    moveRootToFront(tab, root);
  }

  static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null  b == null 
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
      // 调用系统类计算原生的hashCode
      d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
           -1 : 1);
    return d;
  }

  static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                              TreeNode<K,V> x) {
    // 每次进来就进行一次红色的染色，然后再做调整
    x.red = true;
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
      // 只有一层，把这层的节点染成黑色，直接返回作为root节点
      if ((xp = x.parent) == null) {
        x.red = false;
        return x;
      }
      // 如果只有两层，就不做调整
      else if (!xp.red  (xpp = xp.parent) == null)
        return root;
      // 判断需要发生插入并且旋转的位置是发生在左子树还是右子树
      // 想要走进来也很简单，就是把我们的示例的递增换成递减就可以了
      if (xp == (xppl = xpp.left)) {
        if ((xppr = xpp.right) != null && xppr.red) {
          xppr.red = false;
          xp.red = false;
          xpp.red = true;
          x = xpp;
        }
        else {
          if (x == xp.right) {
            root = rotateLeft(root, x = xp);
            xpp = (xp = x.parent) == null ? null : xp.parent;
          }
          if (xp != null) {
            xp.red = false;
            if (xpp != null) {
              xpp.red = true;
              root = rotateRight(root, xpp);
            }
          }
        }
      }
      else {
        // 那我们是递增的，所以发生在右子树，会经常的走进这里来
        if (xppl != null && xppl.red) {// 情况一：发生了变色，也就是左右两个红色的连接往上浮一层
          xppl.red = false;
          xp.red = false;
          xpp.red = true;
          x = xpp;
        }
        else {// 情况二：判断要发生左旋转还是右旋转
          if (x == xp.left) {
            root = rotateRight(root, x = xp);
            xpp = (xp = x.parent) == null ? null : xp.parent;
          }
          if (xp != null) {
            xp.red = false;
            if (xpp != null) {
              xpp.red = true;
              root = rotateLeft(root, xpp);
            }
          }
        }
      }
    }
  }

}

那这个情况的搜索或者是旋转跟上面简单的红黑树示例差不多，我也就不继续画图了。那我们现在要跳出去，也就是看看 moveRootToFront(tab, root); 做了什么：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
  int n;
  if (root != null && tab != null && (n = tab.length) > 0) {
    // 查找目前root的Key值锁需要存在的下标
    int index = (n - 1) & root.hash;
    // 可能为空，但只要不是跟之前的值一致，就需要进行替换
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
    if (root != first) {
      Node<K,V> rn;
      tab[index] = root;
      // 把之前放在链表的第一个往后移动，并且把root节点放在链表的第一位
      TreeNode<K,V> rp = root.prev;
      if ((rn = root.next) != null)
        ((TreeNode<K,V>)rn).prev = rp;
      if (rp != null)
        rp.next = rn;
      if (first != null)
        first.prev = root;
      root.next = first;
      root.prev = null;
    }
    assert checkInvariants(root);
  }
}

HashMap扩容

HashMap 在扩容的时候，jdk7 和 jdk8 使用的方式是不一样的，jdk7 要好理解一点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// JDK1.7版本的HashMap：
// 我们在调用put(K key, V value)方法插入数据的时候，就会进入这个方法
void addEntry(int hash, K key, V value, int bucketIndex) {
  if ((size >= threshold) && (null != table[bucketIndex])) {
    // 重点关注这里，可以看到扩容的时候是2倍2倍的在扩容
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }

  createEntry(hash, key, value, bucketIndex);
}

void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  if (oldCapacity == MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return;
  }

  // 创建一个新的Entry数组
  Entry[] newTable = new Entry[newCapacity];
  // 将旧的数组拷贝过去
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  table = newTable;
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
  int newCapacity = newTable.length;
  // 遍历table数组的
  for (Entry<K,V> e : table) {
    // 遍历链表结构的节点
    while(null != e) {
      Entry<K,V> next = e.next;
      if (rehash) {
        e.hash = null == e.key ? 0 : hash(e.key);
      }
      int i = indexFor(e.hash, newCapacity);
      // 在这里链表的顺序发生了转换，也就是头部先插进去，然后尾部再把它顶出去(头插法)
      // 举个例子，比如当前链表是 0 -> 1 -> 2
      // 新的链表会变成 2 -> 1 -> 0
      e.next = newTable[i];
      newTable[i] = e;
      e = next;
    }
  }
}

那我们再看看 JDK8 的版本实现，Emm，orz：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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; // 同样的还是扩容两倍，采用位移的方式来计算
  }
  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;
  // 这上面是计算容量、threshold的，我们只要知道是2倍oldCap即可
  @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的连接
        oldTab[j] = null;
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          // 红黑树的尝试分割，通过跟以前相似的方法遍历红黑节点，分割高低位存放
          // 如果分割后的节点个数小于6个，则还原原来的Node链表结构
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          // 将原来的链表分割为两个链表分割
          // 一个高位，一个低位，
          // 分别声明两个值，head记录链表头部，tail记录尾部
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            next = e.next;
            // 使用旧的容量进行hash计算，能够保证插入的顺序
            // 这里有个技巧，扩容是2倍的扩容，所以在计算的时候
            // 之前碰撞的hash值要么在原位置，要么在(oldIndex+oldCap)
            // 所以loHead的链表可以看成是保存原来索引的链表而hiHead是保存新数组的链表
            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);
          // 直接赋值，loHead在低位索引的数组中，hiHead在高位的数组中
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}