实现一个Map，其中键是非重叠范围的集合

我使用List和循环来解决当前实现的性能问题。 我正在考虑制作一些自定义Map但是可以正确覆盖getter以使用以下设置：

Map包含自定义对象，键可以如下：

 case A key: "10" calling get("10") would return matching object case B key: "10;12;14" calling get("10"),get("12"),get("14") would return same object case C key: "10;20-30" calling get("10"), get(value between 20 and 30) would return same object 

在这种场景中使用Map是最好的方法，可能有哪些替代方案？

谢谢。

Answer 1

更新：添加完整实施

更新2：如果需要，可以使用RangeMap作为注释中建议的内部地图。

如果键范围不重叠，则可以创建一个自定义容器，该容器在内部使用实现Comparable的自定义键在TreeMap存储数据：

 class MyStorage { private static final class Range implements Comparable { private int first; private int last; public Range(int first_, int last_) { first = first_; last = last_; } // This heavily relies on that the ranges don't overlap @Override public int compareTo(Range other) { if (last < other.first) return -1; if (first > other.last) return 1; return 0; } } private Map theMap = new TreeMap(); public void put(String key, T obj) { String[] ranges = key.split(";"); for (String range : ranges) { //System.out.println("Adding " + range); String[] bounds = range.split("-"); //System.out.println("Bounds " + bounds.length); int first = Integer.parseInt(bounds[0]); if (bounds.length == 1) theMap.put(new Range(first, first), obj); else theMap.put(new Range(first, Integer.parseInt(bounds[1])), obj); } } public T get(String key) { return get(Integer.parseInt(key)); } public T get(int key) { return theMap.get(new Range(key, key)); } } class Main { public static void main (String[] args) throws java.lang.Exception { MyStorage storage = new MyStorage(); storage.put("10;20-30", 123); storage.put("15;31-50", 456); System.out.println(storage.get("42")); } } 

Answer 2

有一种称为间隔树的结构可以满足您的需求。 这是它的实现。

它允许您将对象附加到间隔而不是通常的对象。

请注意，此实现不实现原始算法建议的排序索引，因为我需要它的用例不需要这种速度级别。

 /** * @author OldCurmudgeon * @param  - The type stored in the tree. Must implement IntervalTree.Interval but beyond that you can do what you like. Probably store that value in there too. */ public class IntervalTree { // My intervals. private final List intervals; // My center value. All my intervals contain this center. private final long center; // My interval range. private final long lBound; private final long uBound; // My left tree. All intervals that end below my center. private final IntervalTree left; // My right tree. All intervals that start above my center. private final IntervalTree right; public IntervalTree(List intervals) { if (intervals == null) { throw new NullPointerException(); } // Initially, my root contains all intervals. this.intervals = intervals; // Find my center. center = findCenter(); /* * Builds lefts out of all intervals that end below my center. * Builds rights out of all intervals that start above my center. * What remains contains all the intervals that contain my center. */ // Lefts contains all intervals that end below my center point. final List lefts = new ArrayList<>(); // Rights contains all intervals that start above my center point. final List rights = new ArrayList<>(); // Track my bounds while distributing. long uB = Long.MIN_VALUE; long lB = Long.MAX_VALUE; for (T i : intervals) { long start = i.getStart(); long end = i.getEnd(); if (end < center) { // It ends below me - move it to my left. lefts.add(i); } else if (start > center) { // It starts above me - move it to my right. rights.add(i); } else { // One of mine. lB = Math.min(lB, start); uB = Math.max(uB, end); } } // Remove all those not mine. intervals.removeAll(lefts); intervals.removeAll(rights); // Record my bounds. uBound = uB; lBound = lB; // Build the subtrees. left = lefts.size() > 0 ? new IntervalTree<>(lefts) : null; right = rights.size() > 0 ? new IntervalTree<>(rights) : null; // Build my ascending and descending arrays. /** * @todo Build my ascending and descending arrays. */ } /* * Returns a list of all intervals containing the point. */ List query(long point) { // Check my range. if (point >= lBound) { if (point <= uBound) { // In my range but remember, there may also be contributors from left or right. List found = new ArrayList<>(); // Gather all intersecting ones. // Could be made faster (perhaps) by holding two sorted lists by start and end. for (T i : intervals) { if (i.getStart() <= point && point <= i.getEnd()) { found.add(i); } } // Gather others. if (point < center && left != null) { found.addAll(left.query(point)); } if (point > center && right != null) { found.addAll(right.query(point)); } return found; } else { // To right. return right != null ? right.query(point) : Collections.emptyList(); } } else { // To left. return left != null ? left.query(point) : Collections.emptyList(); } } private long findCenter() { //return average(); return median(); } protected long median() { // Choose the median of all centers. Could choose just ends etc or anything. long[] points = new long[intervals.size()]; int x = 0; for (T i : intervals) { // Take the mid point. points[x++] = (i.getStart() + i.getEnd()) / 2; } Arrays.sort(points); return points[points.length / 2]; } /* * What an interval looks like. */ public interface Interval { public long getStart(); public long getEnd(); } /* * A simple implemementation of an interval. */ public static class SimpleInterval implements Interval { private final long start; private final long end; public SimpleInterval(long start, long end) { this.start = start; this.end = end; } @Override public long getStart() { return start; } @Override public long getEnd() { return end; } @Override public String toString() { return "{" + start + "," + end + "}"; } } public static void main(String[] args) { // Make some test data. final int testEntries = 1 * 100; ArrayList intervals = new ArrayList<>(); Random random = new Random(); for (int i = 0; i < testEntries; i++) { // Make a random interval. long start = random.nextLong(); intervals.add(new SimpleInterval(start, start + 1000)); } ProcessTimer timer = new ProcessTimer(); IntervalTree tree = new IntervalTree<>(intervals); System.out.println("Took " + timer); } }