Возврат элемента из TreeSet с использованием бинарного поиска

Question

В TreeSet есть метод с именем contains, который возвращает true, если элемент находится в наборе.Я предполагаю, что этот метод использует бинарный поиск и не перебирает все элементы в порядке возрастания.Я прав?

У меня есть TreeSet, который содержит объекты класса, который использует две переменные экземпляра String, чтобы отличать его от других объектов того же класса.Я хочу иметь возможность создать метод, который ищет TreeSet, сравнивая две переменные экземпляра объектов (конечно, используя методы get) с двумя другими переменными String и, если они равны, возвращает элемент.Если переменные экземпляра меньше, чем переход к первому элементу в правом поддереве, или если они больше, ищите в левом поддереве и т. Д. Есть ли способ сделать это?

Я знаю, что могу просто сохранить объектыв ArrayList и использовать бинарный поиск, чтобы найти объект, но это не так быстро, как просто поиск TreeSet.

Answer 1

set.tailSet(obj).first();

делает то, что вы хотите.

Answer 2

Вместо использования TreeSet вы можете хранить свои объекты в TreeMap<Foo, Foo> или TreeMap<FooKey, Foo> (если вы не можете легко создать новый фактический Foo каждый раз, когда хотите выполнить поиск). Set s на самом деле не предназначены для поиска.

Для примера FooKey, FooKey будет простым неизменным классом, который просто содержит два String s и равен Comparable. Найти значение Foo для двух String с было бы простым делом treeMap.get(new FooKey(firstString, secondString)). Это, конечно, использует обход дерева, значение которого вы хотите найти.

Answer 3

Вы должны либо реализовать Comparable на своем объекте, либо создать отдельный класс Comparator, который вы передаете во время создания TreeSet. Это позволяет вам внедрить вашу собственную логику сравнения записей и позволить TreeSet оптимизировать процесс хранения / поиска.

Answer 4

Мне было интересно узнать, почему вы хотите искать в отсортированном наборе?Если вы хотите иметь возможность выполнять итерацию по порядку, а также быстро выполнять поиск, вы можете извлечь выгоду из хранения ваших объектов в двух отдельных структурах данных.Такой как ваш SortedSet<Foo>, а затем HashMap<FooKey,Foo> похож на тот, что упоминал ColinD.Затем вы получаете постоянный поиск вместо log (n) в TreeMap.У вас есть штраф за запись в обе структуры и ресурс памяти из-за наличия двух структур данных, но вы полностью оптимизировали свой доступ к данным.

Также, если ресурсы памяти ограничены, и ваши строки действительно различают объекты, тогда вы можете просто реализовать hashcode() и equals() на вашем объекте Foo, а затем просто использовать их как ключи значение (например, HashMap<Foo,Foo>. Предостережение заключается в том, что вам нужно создать Foo для вызова метода получения.

Answer 5

Вы получили ответ об использовании сопоставимого / компаратора, но я подумал, что добавлю, что вы правы, так как метод содержит () двоичный поиск, хотя вам не нужно знать эти подробности