Java教程

关于有序查找的随笔

本文主要是介绍关于有序查找的随笔,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

当初有一个业务需求,给每个业务数据评分,并获取排行及排行占比。

当时想着抽象来看,这就是有序查找,最高性能的有序查找只有二分查找法。想到二分查找立刻会想到二叉树。于是当初没多想,就用红黑树实现了这个功能。

如今看了redis的有序集合,有了新的感悟。写下此随笔。

redis的有序集合使用了哈希加跳表的方式实现。哈希主要是为了快速查询数据。跳表是为了实现数据有序。这才恍然大悟,原来除了二叉树还有其他的高效有序查找方法。

跳表和二叉树一样,有序查找的时间复杂度能够达到O(log(n)),空间损耗比二叉树略高,但是实现相对简单,并且由于修改操作需要锁住的结点比二叉树少,在并发方面有更高的性能。

由此可见上述业务更适合使用跳表实现。

这篇关于关于有序查找的随笔的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!