Ключ Hashtable в целочисленном интервале

Ответ 1

Не нужно изобретать колесо, используйте 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
Школьное время
Есть еще автомобиль?

Ответ 2

Наивный HashTable - неправильное решение здесь. Переопределение метода equals() не делает вам ничего хорошего, потому что HashTable сначала сравнивает ключевую запись с помощью хеш-кода, а не методом equals(). Метод equals() проверяется только после того, как будет согласован хэш-код.

Легко сделать хэш-функцию на вашем объекте интервала, но гораздо сложнее сделать тот, который даст тот же хэш-код для всех возможных интервалов, которые будут в пределах другого интервала. Переопределение метода get() (например, здесь fooobar.com/questions/413479/...) для HashTable полностью отрицает преимущества HashTable, что очень быстрое время поиска. В тот момент, когда вы просматриваете каждый элемент HashTable, вы знаете, что неправильно используете HashTable.

Я бы сказал, что Использование java-карты для поиска диапазона и fooobar.com/questions/413479/... - лучшие решения, но HashTable просто не подходит для этого.

Ответ 3

Вы можете использовать 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 + "}";
    }
  }

}

Ответ 4

Я думаю, что реализация специализированного метода get будет намного проще.

Новый метод может быть частью класса-оболочки-оболочки.

Ключевой класс: (интервал [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;
    }
}

Это просто пример и, безусловно, может быть оптимизирован, и есть несколько недостатков:

Для примера, если Intervals перекрываются, нет никакой гарантии, чтобы узнать, какой интервал будет использоваться для поиска, а интервалы не гарантируются, чтобы не перекрываться!

Ответ 5

Решение OldCurmudgeon отлично работает для меня, но очень медленно инициализирует (потребовалось 20 минут для записи 70 тыс.). Если вы знаете, что ваш входящий список элементов уже упорядочен (по возрастанию) и имеет только неперекрывающиеся интервалы, вы можете инициализировать его в миллисекундах, добавив и используя следующий конструктор:

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

Ответ 6

Это зависит от вашей реализации hashCode. У вас могут быть два объекта с одинаковым значением hashCode.
Используйте eclipse для генерации метода hashCode для вашего класса (нет смысла повторно изобретать колесо

Ответ 7

Чтобы Hastable или HashMap работали, как ожидалось, это не только равный хэш-код, но и метод equals должен возвращать true. То, что вы запрашиваете, это интервал (x, y).equals(интервал (m, n)) для m, n в пределах x, y. Поскольку это должно быть верно для любого перекрывающегося живого экземпляра Interval, класс должен записать все из них и должен реализовать то, что вы пытаетесь достичь, действительно.

Короче говоря, нет.

Google guava-библиотека планирует предлагать RangeSet и Map: guava RangeSet

Для разумных небольших диапазонов простой подход состоял бы в том, чтобы специализировать HashMap, помещая и получая отдельные значения интервалов.