java_xiaoo的博客

一、前言 为啥要学红黑树吖？ 因为笔者最近在赶项目的时候，不忘抽出时间来复习Java基础知识，现在准备看集合的源码啦啦。听闻，HashMap在jdk 1.8的时候，底层的数据结构发生了变化，变成了数组+链表+红黑树。很好，没了解过红黑树，所以就趁今天闲暇学习一下啦 二、什么是红黑树？ 2.1 有啥用处？ 红黑树从本质上来说就是一颗二叉查找树，但是在二叉树的基础上增加了着色相关的性质，使得红黑树可以保证相对平衡，从而保证红黑树的增删改查的时间复杂度最坏也能达到O(log N)。 2...

前言 本文，我将通过两种方式手写跳表，并结合画图，彻底搞定跳表实现的细节。 第一种方式为跳表的通用实现，第二种方式为彤哥自己发明的实现，并运用到HashMap的改写中。 好了，开始今天的学习吧，Let’s Go！ 文末有跳表和红黑树实现的HashMap的对比，不想看代码的同学也可以直达底部。 通用实现 通用实现主要参考JDK中的ConcurrentSkipListMap，在其基础上，简化，并优化一些东西，学好通用实现也有助于理解JDK中的ConcurrentSkipListMa...

强连通分量分解的Kosaraju算法 今天是算法数据结构专题的第35篇文章，我们来聊聊图论当中的强连通分量分解的Tarjan算法。 Kosaraju算法一看这个名字很奇怪就可以猜到它也是一个根据人名起的算法，它的发明人是S. Rao Kosaraju，这是一个在图论当中非常著名的算法，可以用来拆分有向图当中的强连通分量。 背景知识 这里有两个关键词，一个是有向图，另外一个是强连通分量。有向图是它的使用范围，我们只能使用在有向图当中。对于无向图其实也存在强连通分量这个概念，但由于无向图的连通性非常强，

强连通分量分解的Kosaraju算法 今天是算法数据结构专题的第35篇文章，我们来聊聊图论当中的强连通分量分解的Tarjan算法。 Kosaraju算法一看这个名字很奇怪就可以猜到它也是一个根据人名起的算法，它的发明人是S. Rao Kosaraju，这是一个在图论当中非常著名的算法，可以用来拆分有向图当中的强连通分量。 背景知识 这里有两个关键词，一个是有向图，另外一个是强连通分量。有向图是它的使用范围，我们只能使用在有向图当中。对于无向图其实也存在强连通分量这个概念，但由于无向图的连通性非常强，