JDK1.8HashMap源码学习-数据结构

木左

修改于 2020-10-20 16:54:46

3590

修改于 2020-10-20 16:54:46

文章被收录于专栏：木左侃技术人生木左侃技术人生

都说现在面试必问HashMap，所以自己也学习下。不过有些东西看过不记录下来估计很快就忘记了。所以记录下来，以便自己将来查看回顾学习。

先看下HashMap的数据结构，只有了解了底层的数据结构，才会对之后如何操作数据有一个更加形象深刻的了解。下图是JDK1.8的HashMap数据结构：

如图所示，JDK1.8HashMap采用的是数组+链表+红黑树。每一个数组下标中(或者称为桶中)存储的应该就是三种类型，一种是空，即没有存储数据。一种是Node<K,V>，另一种就是TreeNode<K,V>，通过查看TreeNode<K,V>的继承关系，如下

//Class TreeNode
static final class TreeNode<K,V> 
extends LinkedHashMap.Entry<K,V> {...}
//Class LinkedHashMap.Entry<K,V>
static class Entry<K,V> extends HashMap.Node<K,V> {...}

我们可以知道，原来TreeNode<K,V>间接继承了Node<K,V>，所以说桶中存储TreeNode<K,V>并没有任何问题。

了解了桶中存储的对象，我们接下看下一个桶中是如何存储多个对象的。有两种方式，一种是采用的单向链表，一种是采用的双向链表+红黑树。在整体的数据结构图中有明确的标识，可放大查看。

单向链表比较简单，我们看下它的每个节点Node<K,V>代码

//Class Node<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    ...
}

每一个节点都保存了通过key计算的hash值以及map中的key和value以及下一节点的引用。也就是说一个节点是知道它下一个节点的，但是并不知道它的前一个节点。所以单向链表就是从桶的根节点一直向下存储，每次查找数据、添加数据、删除数据都是这样。所以如果一个桶中的数据非常多，那么相应的数据操作就是这样从根节点开始，一直向下，直到找到对应的位置进行操作，相对来说比较耗时。

于是引入了红黑树这种结构，方便快速查找。个人理解这是一种空间换时间的做法，因为转换成红黑树后每个节点存储的属性会多，占用空间应该也会大，但是速度会比之前快。

那么我们看下双向链表+红黑树每个节点TreeNode<K,V>代码

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

我们看到增加了属性父节点parent，左孩子left，右孩子right，前节点prev以及颜色是否是红色red，增加的这些节点都是引用，为了方便描述统一省略，之后也直接说。其中的父节点parent，左孩子left，右孩子right和是否是红色red主要是用于描述红黑树，而前节点prev主要是用于和从Node<K,V>中继承的next节点去对应描述双向链表。

如果一个桶中是红黑树的结构，那它应该也是一个双向链表的结构。不仅如此，红黑树的根节点就是双向链表的头节点。这个大家一定要记住，因为之后的源码阅读中，如果有这个作为基础，很多代码就能很容易的去理解。这个在上图中也有标识，可以去查看。

然后我们看下对其中的数据进行操作，红黑树也是从根节点开始，但是每次查找通过比较hash值就可以过滤掉另一部分的节点，相比链表肯定快。我们放一个动态的图，给大家直观的感受下。