Hashtable key within integer interval

Question

I don't know if this is possible but i'm trying to make an Hashtable of where Interval is a class with 2 integer / long values, a start and an end and i wanted to make something like this:

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

So basically what i want is that a key between a range of values in an Interval object give the correspondent WhateverObject. I know i have to override equals() and hashcode() in the interval object, the main problem i think is to somehow have all the values between 100 and 200 (in this specific example) to give the same hash.

Any ideias if this is possible?

Thanks

Answer 1

No need to reinvent the wheel, use a NavigableMap. Example Code:

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

Output:

Cry Baby
School Time
Got a car yet?

Answer 2

You could use an IntervalTree. Here's one I made earlier.

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 + "}";
    }
  }

}

Answer 3

A naive HashTable is the wrong solution here. Overriding the equals() method doesn't do you any good because the HashTable compares a key entry by the hash code first, NOT the equals() method. The equals() method is only checked AFTER the hash code is matched.

It's easy to make a hash function on your interval object, but it's much more difficult to make one that would yield the same hashcode for all possible intervals that would be within another interval. Overriding the get() method (such as here https://stackoverflow.com/a/11189075/1261844) for a HashTable completely negates the advantages of a HashTable, which is very fast lookup times. At the point where you are scanning through each member of a HashTable, then you know you are using the HashTable incorrectly.

I'd say that Using java map for range searches and https://stackoverflow.com/a/11189080/1261844 are better solutions, but a HashTable is simply not the way to go about this.

Answer 4

I think implementing a specialized get-method would be much easier.

The new method can be part of a map-wrapper-class.

The key-class: (interval is [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;
    }
}

The Map-class:

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

This is just an example and can surely be optimized, and there are a few flaws as well:

For Example if Intervals overlap, there's no garantee to know which Interval will be used for lookup and Intervals are not garanteed to not overlap!

Answer 5

OldCurmudgeon's solution works perfectly for me, but is very slow to initialise (took 20 mins for 70k entries). If you know your incoming list of items is already ordered (ascending) and has only non overlapping intervals, you can make it initialise in milliseconds by adding and using the following constructor:

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

Answer 6

This depends on your hashCode implementation. You may have two Objects with the same hashCode value.
Please use eclipse to generate a hashCode method for your class (no point to re-invent the wheel

Answer 7

For Hastable or HashMap to work as expected it's not only a equal hashcode, but also the equals method must return true. What you are requesting is that Interval(x, y).equals(Interval(m, n)) for m, n within x,y. As this must be true for any overlapping living instance of Interval, the class has to record all of them and needs to implement what you are trying to achieve, indeed.

So in short the answer is no.

The Google guava library is planning to offer a RangeSet and Map: guava RangeSet

For reasonable small ranges an easy approach would be to specialize HashMap by putting and getting the indivual values of the intervals.