Эквивалент TreeSet / TreeMap для HashSet / HashMap (пользовательский хеш)

Question

TreeSet имеет конструктор, который принимает компаратор, то есть даже если хранимые вами объекты не являются Comparable объектами сами по себе, вы можете предоставить собственный компаратор.

Есть ли аналогичная реализация неупорядоченного множества? (например, альтернатива HashSet<T>, которая принимает объект "хеш", который вычисляет equals() и hashCode() для объектов T, которые могут отличаться от собственных реализаций объектов?)

C ++ std::hash_set дает вам это, просто интересно, есть ли что-то для Java.

---

Edit: @Max поднимает хороший технический вопрос о equals() - достаточно справедливо; и это верно для клавиш TreeMap и HashMap через Map.containsKey(). Но существуют ли другие хорошо известные структуры данных, которые позволяют организовывать пользовательские хэши?

Answer 1

Нет, наличие объекта "hasher" не поддерживается спецификациями Collections. Вы, конечно, можете реализовать свою собственную коллекцию, которая поддерживает это, но другой способ сделать это - считать Hasher обертывающим объектом, который вместо этого хранится в вашем HashSet.

Set<HasherWrapper<Foo>> set = new HashSet<HasherWrapper<Foo>>();
set.add(new HasherWrapper(foo));
...

Класс-оболочка будет выглядеть примерно так:

private class HasherWrapper<T> {
    T wrappedObject;
    public HasherWrapper(T wrappedObject) {
        this.wrappedObject = wrappedObject;
    }
    @Override
    public int hashCode() {
        // special hash code calculations go here
    }
    @Override
    public boolean equals(Object obj) {
        // special equals code calculations go here
    }
}

Answer 2

В стандартной библиотеке нет такой реализации, но она не мешает вам развернуть свою собственную.Это то, что я часто хотел иметь сам.

См. http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4771660 по причине:

Мы хотели избежать сложности.Мы всерьез поддерживали это понятие во время разработки структуры коллекций, но отвергли его.Соотношение мощности к весу казалось низким.Мы чувствовали, что равных - это то, что вы хотели в 95% случаев;== 4%;и еще что-то 1%.Написание разумных контрактов для массовых операций, когда очень сложно, когда предикаты равенства различаются.

Answer 3

Нет, нет и не может быть по спецификации.Более того, вы неправильно поняли, как TreeSet использует его Comparator.

С TreeSet Javadoc :

Обратите внимание, что порядок, поддерживаемый набором (независимо от того, предоставляется ли явный компаратор), должен соответствовать равным, если онэто правильно реализовать интерфейс Set.(См. Comparable или Comparator для точного определения соответствия с equals.) Это так, потому что интерфейс Set определен в терминах операции equals, но экземпляр TreeSet выполняет все сравнения элементов, используя свой метод CompareTo (или сравнение), поэтому дваэлементы, которые считаются равными этим методом, с точки зрения множества равны.Поведение множества корректно определено, даже если его порядок не совпадает с равенством;он просто не соблюдает общий контракт интерфейса Set.

From Comparable javadoc :

Сказано естественное упорядочение для класса Cбыть согласованным с equals в том и только в том случае, если e1.compareTo (e2) == 0 имеет то же логическое значение, что и e1.equals (e2) для каждого e1 и e2 класса C. Обратите внимание, что null не является экземпляром какого-либо класса,и e.compareTo (null) должен генерировать исключение NullPointerException, даже если e.equals (null) возвращает false.

From Collection javadoc :

логическое значение содержит (Object o)

Возвращает значение true, если эта коллекция содержит указанный элемент.Более формально, возвращает true тогда и только тогда, когда эта коллекция содержит хотя бы один элемент e такой, что (o == null? E == null: o.equals (e)).

Следовательно,В спецификации не может быть какого-либо класса, который реализует интерфейс Collection<E>, а полностью зависит от некоторого внешнего объекта в стиле Comparator для вставки объектов.Все коллекции должны использовать equals метод класса Object, чтобы проверить, если объект уже вставлен.

Answer 4

Определенно ничего подобного нет, hashcode() и equals() определяют атрибуты объекта и не должны изменяться. Они определяют, что делает объект равным друг другу, и это не должно отличаться от одного набора к другому. Единственный способ сделать то, о чем вы говорите, это создать подкласс объекта и записать новые hashcode() и equals(), и это действительно имеет смысл, если подкласс имеет определяющую переменную, которая должна быть добавлена ​​в дополнение к супер класс 'hashcode() и equals(). Я знаю, что это не то, к чему вы стремитесь, но я надеюсь, что это поможет. Если вы объясните, почему вы хотите этого, то это может помочь найти лучшее решение, если оно существует.