问题引入
前些天在思考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: 我在查找这个问题的时候发现相关资料就比较少，思考之后也发现了为什么少，与其说答案，不如说这个问题本身站不住。发现问题的本质是理解后思考，解决问题是思考再理解，能发现问题就是好事，如果你看到这篇文章，说明你本身也是一个爱思考的人。
原文地址：https://wu55555.blog.csdn.net/article/details/118305731
