jjzjj

java基于TreeMap或ConcurrentSkipListMap实现数据的范围查找

追极 2023-03-28 原文

背景

等值查找，有数组、列表、HashMap等，已经足够了，范围查找，该用什么数据结构呢？下面介绍java中非常好用的两个类TreeMap和ConcurrentSkipListMap。

 

TreeMap的实现基于红黑树

    每一棵红黑树都是一颗二叉排序树，又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 [2] 
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
 
ConcurrentSkipListMap的实现基于跳表
    跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到。
    它采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。跳表结构的头节点需有足够的指针域，以满足可能构造最大级数的需要，而尾节点不需要指针域。
    采用这种随机技术，跳表中的搜索、插入、删除操作的时间均为O(logn)，然而，最坏情况下时间复杂性却变成O(n)。相比之下，在一个有序数组或链表中进行插入/删除操作的时间为O(n)，最坏情况下为O(n)。
 
范围查找代码
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;


public class TreeMapAndSkipListMapTest {

    public static void main(String[] args) {
        Map<Long, String> map = new HashMap<>();
        map.put(2L, "aaa2");
        map.put(1L, "aaa1");
        map.put(5L, "aaa5");
        map.put(3L, "aaa3");
        map.put(4L, "aaa4");
        treeMapTest(map);
        skipListMapTest(map);
    }

    private static void treeMapTest(Map<Long, String> map) {
        TreeMap<Long, String> treeMap = new TreeMap<>();
        treeMap.putAll(map);

        //自然序输出
        System.out.println("TreeMap自然序输出");
        for (Map.Entry<Long, String> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }

        //寻找范围
        System.out.println("TreeMap输出2-3的值");
        SortedMap<Long, String> sortedMap = treeMap.subMap(2L, 4L);
        for (Map.Entry<Long, String> entry : sortedMap.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
    }

    private static void skipListMapTest(Map<Long, String> map) {
        ConcurrentSkipListMap<Long, String> skipListMap = new ConcurrentSkipListMap();
        skipListMap.putAll(map);

        //自然序输出
        System.out.println("ConcurrentSkipListMap自然序输出");
        for (Map.Entry<Long, String> entry : skipListMap.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }

        //寻找范围
        System.out.println("ConcurrentSkipListMap输出2-3的值");
        SortedMap<Long, String> sortedMap = skipListMap.subMap(2L, 4L);
        for (Map.Entry<Long, String> entry : sortedMap.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
    }
}

 

 
 跳表原理：https://blog.csdn.net/belalds/article/details/113175003
 
ConcurrentSkipListMapTreeMapspancolorstyleJava

有关java基于TreeMap或ConcurrentSkipListMap实现数据的范围查找的更多相关文章

  1. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  2. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  3. ruby - 触发器 ruby​​ 中 3 点范围运算符和 2 点范围运算符的区别 - 2

    请帮助我理解范围运算符...和..之间的区别，作为Ruby中使用的“触发器”。这是PragmaticProgrammersguidetoRuby中的一个示例:a=(11..20).collect{|i|(i%4==0)..(i%3==0)?i:nil}返回:[nil,12,nil,nil,nil,16,17,18,nil,20]还有:a=(11..20).collect{|i|(i%4==0)...(i%3==0)?i:nil}返回:[nil,12,13,14,15,16,17,18,nil,20] 最佳答案 触发器(又名f/f)是

  4. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  5. ruby-on-rails - 相关表上的范围为 "WHERE ... LIKE" - 2

    我正在尝试从Postgresql表(table1)中获取数据，该表由另一个相关表(property)的字段(table2)过滤。在纯SQL中，我会这样编写查询:SELECT*FROMtable1JOINtable2USING(table2_id)WHEREtable2.propertyLIKE'query%'这工作正常:scope:my_scope,->(query){includes(:table2).where("table2.property":query)}但我真正需要的是使用LIKE运算符进行过滤，而不是严格相等。然而，这是行不通的:scope:my_scope,->(que

  6. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  7. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  8. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  9. Ruby 从大范围中获取第 n 个项目 - 2

    假设我有这个范围:("aaaaa".."zzzzz")如何在不事先/每次生成整个项目的情况下从范围中获取第N个项目？ 最佳答案 一种快速简便的方法:("aaaaa".."zzzzz").first(42).last#==>"aaabp"如果出于某种原因你不得不一遍又一遍地这样做，或者如果你需要避免为前N个元素构建中间数组，你可以这样写:moduleEnumerabledefskip(n)returnto_enum:skip,nunlessblock_given?each_with_indexdo|item,index|yieldit

  10. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

随机推荐