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を与えることです。私はintervalオブジェクトの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());

出力：

泣く赤ちゃん
学校の時間
まだ車を手に入れましたか？

于 2012-06-25T13:15:15.527 に答える
3

ナイーブなHashTableは、ここでは間違った解決策です。equals（）メソッドをオーバーライドしても、HashTableはequals（）メソッドではなく、最初にハッシュコードによってキーエントリを比較するため、何の役にも立ちません。equals（）メソッドは、ハッシュコードが一致した後にのみチェックされます。

間隔オブジェクトでハッシュ関数を作成するのは簡単ですが、別の間隔内にある可能性のあるすべての間隔で同じハッシュコードを生成するハッシュ関数を作成するのははるかに困難です。HashTableのget（）メソッド（ここではhttps://stackoverflow.com/a/11189075/1261844など）をオーバーライドすると、ルックアップ時間が非常に速いHashTableの利点が完全に無効になります。HashTableの各メンバーをスキャンしている時点で、HashTableを誤って使用していることがわかります。

範囲検索にJavaマップを使用することと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-methodの実装ははるかに簡単だと思います。

新しいメソッドは、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

これは、hashCodeの実装によって異なります。同じhashCode値を持つ2つのオブジェクトがある場合があります。
Eclipseを使用して、クラスのhashCodeメソッドを生成してください（車輪の再発明をする意味はありません）

于 2012-06-25T12:01:33.840 に答える
0

HastableまたはHashMapが期待どおりに機能するには、等しいハッシュコードであるだけでなく、equalsメソッドもtrueを返す必要があります。あなたが要求しているのは、x、y内のm、nのInterval（x、y）.equals（Interval（m、n））です。これは、Intervalの重複する生きているインスタンスに当てはまる必要があるため、クラスはそれらすべてを記録する必要があり、実際に達成しようとしていることを実装する必要があります。

つまり、答えはノーです。

Google guavaライブラリは、RangeSetとMapを提供することを計画しています：guava RangeSet

妥当な小さな範囲の場合、簡単なアプローチは、間隔の個々の値を配置して取得することにより、HashMapを特殊化することです。

于 2012-06-25T13:51:22.877 に答える