Java: структура данных для сортировки объектов / поддержания ключа в таком порядке?

Question

Я хочу сохранить коллекцию объектов типа Odp. Odp реализует Comparable. Мне нужно иметь возможность ссылаться на объект в коллекции с его целочисленным именем. Это целое число должно соответствовать порядку сортировки (а не порядку вставки). Каждое целое число относится только к одному Odp, и наоборот.

У меня есть функция compareOdp(Odp o1, Odp o2), которая возвращает числовое значение, представляющее сходство двух аргументов. Я собираю коллекцию Odp таким образом, чтобы можно было легко задавать вопросы типа «Какой ближайший Odp к foo в коллекции?» или «Из этих нескольких коллекций объектов Odp, насколько они близки друг к другу?»

Каков наилучший способ сделать это? TreeMap? HashBiMap?

Вопрос по теме:

Допустим, у меня есть следующий набор объектов: o1, o2, o3, содержащиеся в коллекции col. Их порядок сортировки

o2
o3
o1

Я хочу спросить col: «Что такое n-й объект в списке?» Из того, что я вижу, SortedSet и TreeMap не имеют возможности сделать это. Я думаю, я мог бы повторить, но кажется, что должен быть более легкий путь.

Answer 1

Если вы используете Java 6, может помочь API NavigableSet (реализованный TreeSet).

public static Odp nearest(Odp o, NavigableSet<? extends Odp> set) {
  Odp f = set.floor(o), c = set.ceiling(o);
  if (f == null)
    return c;
  if (c == null)
    return f;
  int df = compareOdp(o, f), dc = compareOdp(c, o);
  return (df <= dc) ? f : c;
}

Answer 2

TreeMap - это встроенное решение, насколько я его использовал. Я думаю, что это очень хорошо.

Answer 3

Любая реализация SortedSet будет поддерживать элементы в порядке, в соответствии с интерфейсом Comparable. TreeSet является реализацией SortedSet.

Answer 4

// What is the nth object in the list...

Object oneObject = TreeMap.get(nthKey);

Хорошо, пока / так хорошо. Если вас не волнует, как они содержатся в структуре данных, вы можете использовать (возможно, придется искать его, но он будет называться a) HashMap ==, в этом случае вам будет предоставлен ключ, который может легко быть:

Object placement= HashMap.put(new Integer(++index),new Object(data));// see docs for exact

если размещение равно нулю, карта ранее не содержала объект, используемый в сочетании с containsKey (), можно получить точное управление набором данных

Что будет работать для поиска и сдачи по заказанному ключу, но только если вы выполните toArray(), вы получите странный порядок, который понятен только тому, кто написал реализацию HashMap.

Answer 5

Я бы использовал непритязательный LinkedList . Затем используйте Collections.binarySearch для поиска в списке. Функция бинарного поиска вернет вам точку вставки в вашем связанном списке. Чтобы найти, какой из них ближе всего, просто используйте функцию compareOdp с элементом ниже и элементом выше в связанном списке.