java基於TreeMap或ConcurrentSkipListMap實現數據的範圍查找

背景

等值查找，有數組、列表、HashMap等，已經足夠了，範圍查找，該用什麼數據結構呢？下麵介紹java中非常好用的兩個類TreeMap和ConcurrentSkipListMap。

TreeMap的實現基於紅黑樹

    每一棵紅黑樹都是一顆二叉排序樹，又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。是數據結構中的一類。在一般情況下，查詢效率比鏈表結構要高。

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());
        }
    }
}