整数区间内的Hashtable键
我不知道这是否可行，但我正在尝试制作一个Hashtable，其中Interval是一个具有2个整数/长值，开始和结束的类，我想做这样的事情：
Hashtable test = new Hashtable(); test.put(new Interval(100, 200), new WhateverObject()); test.get(new Interval(150, 150)) // returns the new WhateverObject i created above because 150 is betwwen 100 and 200 test.get(new Interval(250, 250)) // doesn't find the value because there is no key that contains 250 in it's interval 基本上我想要的是Interval对象中一系列值之间的键给出对应的WhateverObject。 我知道我必须在interval对象中重写equals（）和hashcode（），我认为主要问题是以某种方式将所有值介于100和200之间（在此特定示例中）以给出相同的散列。
任何想法，如果这是可能的？
谢谢
无需重新发明轮子，使用NavigableMap 。 示例代码：
final NavigableMap map = new TreeMap(); map.put(0, "Cry Baby"); map.put(6, "School Time"); map.put(16, "Got a car yet?"); map.put(21, "Tequila anyone?"); map.put(45, "Time to buy a corvette"); System.out.println(map.floorEntry(3).getValue()); System.out.println(map.floorEntry(10).getValue()); System.out.println(map.floorEntry(18).getValue());
输出：
哭泣的婴儿
上学时间
有车吗？
一个天真的HashTable是错误的解决方案。 覆盖equals（）方法对你没有任何好处，因为HashTable首先通过哈希码比较键条目，而不是equals（）方法。 只有匹配哈希码后才会检查equals（）方法。
在你的区间对象上创建一个哈希函数很容易，但要制作一个能够为另一个区间内的所有可能区间产生相同哈希码的方法要困难得多。 覆盖HashTable的get（）方法（例如https://stackoverflow.com/a/11189075/1261844 ）完全否定了HashTable的优势，这是非常快的查找时间。 在您扫描HashTable的每个成员的位置，您知道您正在错误地使用HashTable。
我会说使用java map进行范围搜索和https://stackoverflow.com/a/11189080/1261844是更好的解决方案，但HashTable根本不是解决这个问题的方法。
您可以使用IntervalTree 。 这是我之前制作的。
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 (); 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) { lefts.add(i); } else if (start > center) { 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); 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; } public long getStart() { return start; } public long getEnd() { return end; } @Override public String toString() { return "{" + start + "," + end + "}"; } } }
我认为实现一个专门的get方法会容易得多。
新方法可以是map-wrapper-class的一部分。
关键类:(间隔为[lower; upper [）
public class Interval { private int upper; private int lower; public Interval(int upper, int lower) { this.upper = upper; this.lower = lower; } public boolean contains(int i) { return i < upper && i >= lower; } @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final Interval other = (Interval) obj; if (this.upper != other.upper) { return false; } if (this.lower != other.lower) { return false; } return true; } @Override public int hashCode() { int hash = 5; hash = 61 * hash + this.upper; hash = 61 * hash + this.lower; return hash; } }
地图类：
public class IntervalMap extends HashMap { public T get(int key) { for (Interval iv : keySet()) { if (iv.contains(key)) { return super.get(iv); } } return null; } }
这只是一个例子，肯定可以优化，并且还有一些缺陷：
例如，如果间隔重叠，则无法保证知道哪个间隔将用于查找，并且间隔不保证不重叠！
OldCurmudgeon的解决方案对我来说非常有效，但初始化速度很慢（70k条目需要20分钟）。 如果您知道您的传入项目列表已经订购（升序）并且只有非重叠间隔，您可以通过添加和使用以下构造函数使其初始化为毫秒：
public IntervalTree(List intervals, boolean constructorFlagToIndicateOrderedNonOverlappingIntervals) { if (intervals == null) throw new NullPointerException(); int centerPoint = intervals.size() / 2; T centerInterval = intervals.get(centerPoint); this.intervals = new ArrayList (); this.intervals.add(centerInterval); this.uBound = centerInterval.getEnd(); this.lBound = centerInterval.getStart(); this.center = (this.uBound + this.lBound) / 2; List toTheLeft = centerPoint < 1 ? Collections. emptyList() : intervals.subList(0, centerPoint); this.left = toTheLeft.isEmpty() ? null : new IntervalTree (toTheLeft, true); List toTheRight = centerPoint >= intervals.size() ? Collections. emptyList() : intervals.subList(centerPoint+1, intervals.size()); this.right = toTheRight.isEmpty() ? null : new IntervalTree (toTheRight, true); }
这取决于您的hashCode实现。 您可能有两个具有相同hashCode值的对象。
请使用eclipse为您的类生成一个hashCode方法（没有必要重新发明轮子
为了使Hastable或HashMap按预期工作，它不仅是一个相等的哈希码，而且equals方法必须返回true。 你要求的是m，y内的m，n的Interval（x，y）.equals（Interval（m，n））。 因为对于Interval的任何重叠生活实例来说，这必须是真实的，所以该类必须记录所有这些实例，并且需要实现您正在尝试实现的内容。
所以简而言之，答案是否定的。
Google guava库计划提供RangeSet和Map： guava RangeSet
对于合理的小范围，一种简单的方法是通过放置和获取间隔的不同值来专门化HashMap。