等值查找，有数组、列表、HashMap等，已经足够了，范围查找，该用什么数据结构呢？下面介绍java中非常好用的两个类TreeMap和ConcurrentSkipListMap。
TreeMap的实现基于红黑树
每一棵红黑树都是一颗二叉排序树，又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
ConcurrentSkipListMap的实现基于跳表
跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到。
它采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。跳表结构的头节点需有足够的指针域，以满足可能构造最大级数的需要，而尾节点不需要指针域。
采用这种随机技术，跳表中的搜索、插入、删除操作的时间均为O(logn)，然而，最坏情况下时间复杂性却变成O(n)。相比之下，在一个有序数组或链表中进行插入/删除操作的时间为O(n)，最坏情况下为O(n)。
范围查找代码
Original: https://www.cnblogs.com/hdwang/p/16412551.html
Author: 追极
Title: java基于TreeMap或ConcurrentSkipListMap实现数据的范围查找
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587765/
转载文章受原作者版权保护。转载请注明原作者出处！