跳表与红黑树

65 阅读 0 评论 43 点赞

我是靠谱客的博主生动超短裙，最近开发中收集的这篇文章主要介绍跳表与红黑树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

导读

前几天在可能Redis底层数据结构的实现时，看到了zset底层采用的时跳表，为什么不用红黑树呢，而HashMap为什么用的红黑树没有用跳表呢？因此查询了资料，进行了个人的总结。

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

1、跳表的实现更加简单，不用旋转节点，相对效率更高
2、跳表在范围查询的时候的效率是高于红黑树的，因为跳表是从上层往下层查找的，上层的区域范围更广，可以快速定位到查询的范围（我认为是最重要的）
3、平衡树的插入和删除操作可能引发子树的调整、逻辑复杂，而跳表只需要维护相邻节点即可
4、查找单个key，跳表和平衡树时间复杂度都是O(logN)

个人总结

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

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。