11

我不知道这是否可能，但我正在尝试制作一个哈希表，其中 Interval 是一个具有 2 个整数/长值、一个开始和一个结束的类，我想做这样的事情：

Hashtable<Interval, WhateverObject> test = new Hashtable<Interval, WhateverObject>();
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。我知道我必须在间隔对象中覆盖 equals() 和 hashcode()，我认为的主要问题是以某种方式让所有值在 100 到 200 之间（在这个特定示例中）以给出相同的哈希。

任何想法，如果这是可能的？

谢谢

4

7 回答 7

15

无需重新发明轮子，使用NavigableMap. 示例代码：

final NavigableMap<Integer, String> map = new TreeMap<Integer, String>();
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());

输出：

Cry Baby
School Time
有车了吗？

于 2012-06-25T13:15:15.527 回答
3

天真的 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 根本不是解决这个问题的方法。

于 2012-06-25T13:02:33.897 回答
2

您可以使用IntervalTree。这是我之前做的一个。

public class IntervalTree<T extends IntervalTree.Interval> {
  // My intervals.

  private final List<T> 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<T> left;
  // My right tree. All intervals that start above my center.
  private final IntervalTree<T> right;

  public IntervalTree(List<T> 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<T> lefts = new ArrayList<T>();
    // Rights contains all intervals that start above my center point.
    final List<T> rights = new ArrayList<T>();

    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<T>(lefts) : null;
    right = rights.size() > 0 ? new IntervalTree<T>(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<T> 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<T> found = new ArrayList<T>();
        // 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.<T>emptyList();
      }
    } else {
      // To left.
      return left != null ? left.query(point) : Collections.<T>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 + "}";
    }
  }

}
于 2012-06-25T12:07:52.497 回答
1

我认为实现一个专门的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<T> extends HashMap<Interval, T> {

    public T get(int key) {
        for (Interval iv : keySet()) {
            if (iv.contains(key)) {
                return super.get(iv);
            }
        }
        return null;
    }
}

这只是一个例子，当然可以优化，也有一些缺陷：

例如，如果间隔重叠，则无法保证知道哪个间隔将用于查找，并且不保证间隔不重叠！

于 2012-06-25T12:07:31.613 回答
1

OldCurmudgeon 的解决方案非常适合我，但初始化速度很慢（70k 条目需要 20 分钟）。如果您知道传入的项目列表已经排序（升序）并且只有非重叠间隔，您可以通过添加和使用以下构造函数使其以毫秒为单位进行初始化：

public IntervalTree(List<T> intervals, boolean constructorFlagToIndicateOrderedNonOverlappingIntervals) {
    if (intervals == null) throw new NullPointerException();

    int centerPoint = intervals.size() / 2;
    T centerInterval = intervals.get(centerPoint);
    this.intervals = new ArrayList<T>();
    this.intervals.add(centerInterval);
    this.uBound = centerInterval.getEnd();
    this.lBound = centerInterval.getStart();
    this.center = (this.uBound + this.lBound) / 2;
    List<T> toTheLeft = centerPoint < 1 ? Collections.<T>emptyList() : intervals.subList(0, centerPoint);
    this.left = toTheLeft.isEmpty() ? null : new IntervalTree<T>(toTheLeft, true);
    List<T> toTheRight = centerPoint >= intervals.size() ? Collections.<T>emptyList() : intervals.subList(centerPoint+1, intervals.size());
    this.right = toTheRight.isEmpty() ? null : new IntervalTree<T>(toTheRight, true);
}
于 2013-04-16T14:08:09.660 回答
0

要让 Hastable 或 HashMap 按预期工作，它不仅是相等的哈希码，而且 equals 方法必须返回 true。您要求的是 Interval(x, y).equals(Interval(m, n)) for m, n 在 x,y 内。由于对于 Interval 的任何重叠的活实例都必须如此，因此该类必须记录所有这些实例，并且确实需要实现您想要实现的目标。

所以简而言之，答案是否定的。

Google guava 库计划提供 RangeSet 和 Map：guava RangeSet

对于合理的小范围，一种简单的方法是通过放置和获取间隔的各个值来专门化 HashMap。

于 2012-06-25T13:51:22.877 回答
0

这取决于您的 hashCode 实现。您可能有两个具有相同 hashCode 值的对象。
请使用eclipse为你的类生成一个hashCode方法（没必要重新发明轮子

于 2012-06-25T12:01:33.840 回答