问题引入

前些天在思考zset为什么用跳表而不用红黑树时,自然想到了HashMap为什么用红黑树而不用跳表,做了一些查询和考虑,以此记录结果

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

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

个人思考

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

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

1、跳表需要维护额外的多层链表,是空间换时间的做法,红黑树不用占用多余的空间
2、同时HashMap的Entry并没有内在的排序关系,所以也无法使用跳表,因为跳表本身要求要存在排序关系

个人思考

hashcode无法排序,所以无法实现跳表结构,那不用hashCode不就好了吗?其实如果有这个疑问就走进了一个死胡同。正因为用了hashCode才叫HashMap,不用hash的Map也有呀,
有实现了排序关系的Map,比如TreeMap,再比如底层就是跳表的ConcurrentSkipListMap

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

ps: 我在查找这个问题的时候发现相关资料就比较少,思考之后也发现了为什么少,与其说答案,不如说这个问题本身站不住。发现问题的本质是理解后思考,解决问题是思考再理解,能发现问题就是好事,如果你看到这篇文章,说明你本身也是一个爱思考的人。

QQ + 微信

原文地址:https://wu55555.blog.csdn.net/article/details/118305731