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

　　本篇文章为你整理了java基于TreeMap或ConcurrentSkipListMap实现数据的范围查找（）的详细内容，包含有 java基于TreeMap或ConcurrentSkipListMap实现数据的范围查找，希望能帮助你了解 java基于TreeMap或ConcurrentSkipListMap实现数据的范围查找。

　　背景

　　等值查找，有数组、列表、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)。

　　范围查找代码

　　
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

　　以上就是java基于TreeMap或ConcurrentSkipListMap实现数据的范围查找（）的详细内容，想要了解更多 java基于TreeMap或ConcurrentSkipListMap实现数据的范围查找的内容，请持续关注盛行IT软件开发工作室。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

相关文章阅读