HashMap与红黑树学习总结

2021-06-11

HashMap与红黑树学习总结

HashMap解读(JDK1.8)

带着问题去看代码:

  • 里面是怎么存储数据的(使用到的数据结构)?
  • 怎么计算哈希值,怎么解决哈希冲突?
  • 初始化容量是多少?不断加入数据时,如何进行扩容? 扩容后数据的存储位置是怎么样的
  • 查找数据的时间复杂度
  • 为什么要用红黑树?这里的红黑树实现有什么特点

HashMap特性

  • hash算法效率好,高低位异或
  • 数组⻓度是2的n次幂,采用&运算来代替模运算
  • 采用modCount来实现failFast
  • 为LinkHashMap预留方法实现
  • 效率高,用链接来解决哈希冲突。插入数据时链接过长转为红黑树,删除数据时红黑树高度变低了转化为链表。
  • 数组扩容时链表会一分为二,红黑树也一样,红黑树甚至会转化为链表
  • 线程不安全。
  • 源代码里语句很简洁,经常一行代码包括N多赋值与判断,变量命名过 于简单

Hashtable是线程安全的,它是经典的哈希表实现(数组+ 链表),没有红黑树。同样是哈希表,HashMap跟Hashtable的实现天差地别,可以看出HashMap追求极致的性能,而Hashtable是线程安全的,有加锁操作,性能不会好,所以就采用了最简单的实现

红黑树

红黑树的由来

要完全理解红黑树,必须把下面这些概念都完全搞清楚。

树》二叉树》二叉排序树》自平衡二叉树》2-3树和2-3-4树 (B树)》红黑树

  • 树,只有一个父节点,有若干个子节点
  • 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),又称 二叉搜索树。任意一个节点,它的值比它左孩子的值要大,比它右孩子的值要小
  • 平衡二叉树, 又叫AVL树(它的名字是它的发明者们的缩写),是一个二叉搜索树,它的任意一个节点的左右孩子高度差不超过1

B树

  • B树是一种平衡的多路搜索树
  • 1 个节点可以存储超过 2 个元素(多个元素从小到大排 列)、可以拥有超过 2 个子节点。一个节点存储的元素个 数是它的儿子个数减1
  • 拥有二叉搜索树的一些性质
  • 绝对平衡:每个节点的所有子树高度一致
  • 2-3树和2-3-4树是B树的特例,2-3树是最简单的B树

2-3树、2-3-4树与红黑树

  • 2-3树、2-3-4树虽然能保持平衡,但是计算机不好实现
  • 红黑树(Red Black Tree) 是一种自平衡二叉查找树。红黑树是近似平衡 的二叉树,左右子树高差有可能大于 1,但是他的平均性能要好于AVL树
  • 红黑树对应的理论模型可以是2-3树,也可以是2-3-4树。普遍红黑树的实 现是采用2-3-4树模型

因为2-3(2-3-4)树不好实现,所有把它当做一种模型,采用二叉树的方式(代码较好实现)来实现这个模型。这个就是红黑树。这就是红黑树的由来(当然这是我的猜测)。

红黑树怎么实现这个模型的呢?2-3树一个节点能存两个值,二叉树只能存一个值,所以要把2-3树拆分成两个节点:一个红色,一个黑色。红色代码它可以向上跟它的父节点合并成一个节点,对应的就是2-3树里有两个值元素的节点。这是就是基础。剩下就的就是定各种规则来让红黑树符合2-3树的特征。也就有了红黑树的5个规则。

一张重要的图:2-3-4树与红黑树

2-3-4树与红黑树

红黑树5个特性

  • 1) 节点是红色或黑色
  • 2) 根节点是黑色
  • 3) 空节点(NIL节点,有些文章也叫叶子节点)是黑色的
  • 4) 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所 有路径上不能有两个连续的红色节点)
  • 5 )从任一节点到其每个叶子的路径上包含的黑色节点数量都相同
  • 附加特性:插入的节点设为红色

红黑树5个特性(Why)

  • 1)红色在2-3-4树模型中代表要跟父节点合并成一个节点
  • 2)根节点没有父节点,没有办法合并,所以根节点不能是红色的
  • 3)由于根据特性1任何节点都有颜色,空节点也应该有颜色,被定义为 黑色在代码实现上比较方便(看TreeMap的实现就很明显)。
  • 第4和第5特性要结合一起来看,第5点规定从根到叶子节点的路径上只 算黑色节点数,而第4点规定红色节点不能连续,这两点保证了红黑树 的左右两个子树的高度差不会太大。这也是它性能不错的原因。
  • 附加特性:在代码实现红黑树的时候,插入的代码设为红色,红色的节 点不影响平衡(第5点特性),这样可以减少对树的旋转操作

如果你理解了上面的why,就不会再怕记不住它的5条规则了。

节点插入与删除涉及操作

为了保持红黑树的平衡(即符合红黑树的5个特性),节点 插入或删除需要做一些操作: 1. 变色 2. 左旋转或右旋转,或者将两种旋转组合 3. 涉及到的节点:当前插入的节点,兄弟节点,当前节点的父节点,爷爷节点,叔叔节点

插入总结

先看父,再看叔叔,然后看爷爷。若爷孙三代不在直线, 先父转,再变色, 再爷转。 这一句话概括了几乎所有情况。

删除总结

要想理解红黑树的删除,必须先理解二叉排序树的删除操作。

二叉查找树的结点无非是有两个子结点,有一个子结点和叶子结 点三种,其中有两个子结点的 M 结点的删除逻辑是: 首先寻找 M 结点左子树最大或右子树最小的结点 X 然后把 X 结点的值复制到 M 结点 * 最后删除 X 结点,而这个结点要么是叶子结点,要么就只有一个 孩子

所以,删除任一结点的问题就简化成了: 删除一个最多只有一个孩 子的结点的情况(要么没有孩子,要么只有一个孩子)

红黑树删除节点要领

  • 删除红色叶子节点不影响平衡
  • 删除黑色节点会影响树的平衡,所以想办法从孩子节点, 或者兄弟节点,或者父节点借一个红色节点过来,并把它 变黑,这样树就恢复平衡了。
  • 如果没办法借到红色节点,只能将平衡交给父节点处理,递归向上调整。

红黑树的实现

  • HashMap中的红黑树特性:代码复杂,成员变量多,包含 双向链表结构,空间冗余
  • TreeMap: 按照2-3-4树模型实现,代码可读性强
  • 重复造轮子:手动实现一个红黑树

TreeMap是学习红黑树的最佳源码,没有之一。HashMap里的红黑树相当复杂,在删除一个具有两个孩子节点的地方不太一样,它是直接交换两个节点的,这点开始看得我头疼。

对网上红黑树参考资料吐槽

  • 没有把红黑树规则3说清楚(说叶子节点是黑色的很容易让 人误解)
  • 大部分没有讲红黑树怎么来的,有什么用
  • 没有讲解红黑树的删除操作(删除比插入更复杂)
  • 对代码的解读只是简单的代码注释,估计作者也是半懂不 懂的

我写了个《HashMap、红黑树与B树》的PPT给我们团队做技术分享。该PPT已转为PDF传到了GitHub,感兴趣的可以看看。地址在这

终极疑问

  • 红黑树最差情况是怎样的?
  • 基于2-3树和基于2-3-4树模型实现的红黑树有什么区别?
  • HashMap里的红黑树数据结构什么搞那么复杂?(包含双向链表, 空间冗余)

如果你觉得这篇文章有用,请打赏小钱喝杯咖啡^_^ 打赏

Category: 技术 Tagged: HashMap 红黑树

Comments