跳表与红黑树

 HashMap为什么用红黑树而不用跳表?

1、跳表需要维护额外的多层链表，是空间换时间的做法，红黑树不用占用多余的空间

2、同时HashMap的Entry并没有内在的排序关系，所以也无法使用跳表，因为跳表本身要求要存在排序关系（个人认为最重要）

总结

key的hashcode无法排序，所以无法实现跳表结构，那不用hashCode不就好了吗？其实如果有这个疑问就走进了一个死胡同。正因为用了hashCode才叫HashMap，不用hash的Map也有呀，有实现了排序关系的Map，比如TreeMap（使用TreeMap所有的key都必须直接或间接的实现Comparable接口，否则会报cannot be cast to java.lang.Comparable。当然，直接采用TreeMap(Comparator<? super K> comparator)构造器也是可以的。)再比如底层就是跳表的ConcurrentSkipListMap。

 

所以基于跳表实现的Map也有，基于红黑树实现的Map也有，只是看业务场景来选择哪一个来用。如果你在乎随机查询效率那就是HashMap,如果要求线程安全那就是ConcurrentHashMap；如果要求排序，范围查询那就是ConcurrentSkipListMap。

 

redis的zset为什么用跳表而不用红黑树?

1、跳表的实现更加简单，不用旋转节点，相对效率更高

2、跳表在范围查询的时候的效率是高于红黑树的，因为跳表是从上层往下层查找的，上层的区域范围更广，可以快速定位到查询的范围（我认为是最重要的）

3、平衡树的插入和删除操作可能引发子树的调整、逻辑复杂，而跳表只需要维护相邻节点即可

4、查找单个key，跳表和平衡树时间复杂度都是O(logN)

总结

从redis本身出发，redis是一个单线程的服务，它更加追求查询速度，redis本身是基于内存的，所以它的性能瓶颈在于内存和网络带宽，而不在于CPU。红黑树本身的实现比较复杂，每次新增、修改都要维护节点的旋转、变色，相对而言更加消耗内存，而跳表修改元素只需要维护前后两个节点即可。所以在保障查询速度的前提，内存消耗更小的更适合redis。 

 

一、红黑树

 

 

每个节点或者是红色，或者是黑色（定义）

根节点一定是黑色的（对应2-3树的2节点和3节点）

空节点是黑色的

如果一个节点是红色的，那么它的孩子节点都是黑色的

根节点到任意一个叶子节点所经过的黑节点个数是一样的，即红黑树是一颗保持黑平衡的二叉树，不是平衡二叉树，但左右子树的黑色节点保持绝对的平衡，增删改查复杂度 O(logN)，添加和删除操作比AVL树快

 

节点有两色，非红即黑

根色是黑

所有叶子是黑色空节点

红色节点的子节点都是黑色（不能有两个连续的红色节点相连）

从任何一个节点到其每个叶子的多有路径都包含相同数目的黑色节点

 

 

节点分两色，root是黑色，叶子成黑空，红色不相连，子节点黑色数目相同

 

变换有两种，变色和旋转

 

插入有5种情况：新节点默认颜色是红色

 

新点为树根：一下就变黑；

父点是黑色：新点直接方；

父节点和叔叔节点都是红色：父、爷、叔三节点都要变色；

父节点是红色，叔叔节点是黑色或者没有叔叔节点，且新节点是父节点的右孩子，父节点是祖父节点的左孩子：以父节点为轴，左旋转；（有镜像）

父节点是红色，叔叔节点是黑色或者没有叔叔节点，且新节点是父节点的左孩子，父节点是祖父节点的左孩子：以祖父节点为轴，右旋转；（有镜像）

 

二、跳表

之前我们知道，二分查找依赖数组的随机访问，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找了吗？而实际上，我们只需要对链表稍加改造，就可以实现类似“二分”的查找算法，这种改造之后的数据结构叫作跳表（Skip List）。

 

 

ConcurrentSkipListMap是在JDK 1.6中新增的，为了对高并发场景下的有序Map提供更好的支持，它有几个特点：

 

高并发场景

key是有序的

添加、删除、查找操作都是基于跳表结构（Skip List）实现的

key和value都不能为null

 

跳表（Skip List）是一种类似于链表的数据结构，其查询、插入、删除的时间复杂度都是 O(logn)。

在传统的单链表结构中，查找某个元素需要从链表的头部按顺序遍历，直到找到目标元素为止，查找的时间复杂度为O(n)。

 

而跳表结合了树和链表的特点，其特性如下： 

跳表由很多层组成；

每一层都是一个有序的链表；

最底层的链表包含所有元素；

对于每一层的任意一个节点，不仅有指向其下一个节点的指针，也有指向其下一层的指针；

如果一个元素出现在Level n层的链表中，则它在Level n层以下的链表也都会出现。

 

Skip List例子： 

下图是一种可能的跳表结构：

 

如图，[1]和[40]节点有3层，[8]和[18]节点有2层。每一层都是有序的链表。 

如果要查找目标节点[15]，大致过程如下： 

首先查看[1]节点的第1层，发现[1]节点的下一个节点为[40]，大于15，那么查找[1]节点的下一层；

查找[1]节点的第2层，发现[1]节点的下一个节点为[8]，小于15，接着查看下一个节点，发现下一个节点是[18]，大于15，因此查找[8]节点的下一层；

查找[8]节点的第2层，发现[8]节点的下一个节点是[10]，小于15，接着查看下一个节点[13]，小于15，接着查看下一个节点[15]，发现其值等于15，因此找到了目标节点，结束查询。

 

跳表实际上是一种 空间换时间 的数据结构。

ConcurrentSkipListMap用到了两种结构的节点。

 

ConcurrentSkipListMap 的节点主要由 Node, Index, HeadIndex 构成;下面是一个典型的ConcurrentSkipListMap 的实例的结构图：

 

Redis 为何选用跳表

有序的单链表 O(N)

提高查找效率 --》 对链表建立索引

建立了多级索引，每层索引中，每个节点指向有两个指向，向右和向下

每一层索引节点个数是下层节点个数的一半

查询效率O(logN), 插入，删除也是

通过随机函数维持平衡性，当往跳表中插入数据时，可以通过随机函数选择选择向哪些索引中添加节点，

Redis中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。如果你去查看Redis的开发手册，就会发现，Redis中的有序集合支持的核心操作主要有下面这几个：

插入一个数据；

删除一个数据；

查找一个数据；

 

按照区间查找数据（比如查找值在[100, 356]之间的数据）；

迭代输出有序序列。

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

对于按照区间查找数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。

 

 

当然，Redis之所以用跳表来实现有序集合，还有其他原因，比如，跳表更容易代码实现。虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

 

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表是一样的。

但是，按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表可以在 O(logn)

时间复杂度定位区间的起点，然后在原始链表中顺序向后查询就可以了，这样非常高效。

此外，相比于红黑树，跳表还具有代码更容易实现、可读性好、不容易出错、更加灵活等优点，因此 Redis 用跳表来实现有序集合

 

跳表高效的动态插入和删除？

在链表中，如果我们知道要插入数据的位置，那么插入的时间复杂度就为 O(1)。在跳表中，查找的时间复杂度为 O(logn)，因此，动态插入数据的时间复杂度也就是 O(logn)

了。

 

从链表中删除结点的时候，如果结点在索引中也有出现，那么我们除了要删除原始链表中的结点，还要删除索引中的。

当我们不停地往跳表中插入数据的时候，如果我们不更新索引，就有可能出现某两个结点之间数据非常多的情况。极端情况下，跳表还会退化为单链表。

 

因此，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表结点变多了，索引值就相应地增加一些。

 

当我们往跳表中插入数据的时候，我们可以选择同时也将这个数据插入到部分索引层中。而插入到哪些索引层中，则由一个随机函数生成一个随机数字来决定。如果这个数字为 K，那我们就将数据插入到第一级到第 K 级索引中。