Существует ли структура данных, которая хранит только хэш-коды, а не реальные объекты?

Question

Мой вариант использования заключается в том, что я ищу структуру данных в Java, которая позволила бы мне увидеть, находится ли внутри объект с таким же хеш-кодом (с помощью метода contains ()), но мне никогда не понадобится перебиратьэлементы или получить фактические объекты.HashSet близок, но, насколько я понимаю, он все еще содержит ссылки на реальные объекты, и это было бы пустой тратой памяти, поскольку мне никогда не понадобится содержимое реальных объектов.Лучший вариант, который я могу придумать, - это HashSet типа Integer, хранящий только хэш-коды, но мне интересно, есть ли встроенная структура данных, которая могла бы выполнять то же самое (и принимать только один тип в отличие от HashSetвведите Integer, который будет принимать хеш-код любого объекта).

Answer 1

A Фильтр Блума может определить, может ли объект быть членом или определенно не членом. Вы можете контролировать вероятность ложных срабатываний. Каждое хеш-значение отображается на один бит.

Библиотека Guava обеспечивает реализацию в Java .

Answer 2

Вы можете использовать реализацию примитивной коллекции, например IntSet , для хранения значений хеш-кодов.Очевидно, как уже упоминали другие, это предполагает, что столкновения не являются проблемой.

Answer 3

Если вы хотите отследить, если хеш-код уже существует, и сделать его эффективным для использования памяти, BitSet может удовлетворить ваши требования.

Посмотрите на следующий пример:

  public static void main(String[] args) {
    BitSet hashCodes = new BitSet();
    hashCodes.set("1".hashCode());

    System.out.println(hashCodes.get("1".hashCode())); // true
    System.out.println(hashCodes.get("2".hashCode())); // false
  }

BitSet "реализует вектор битов, который увеличивается по мере необходимости." .Это JDK " встроенная структура данных ", которая не содержит " ссылок на реальные объекты ".Он сохраняется только в том случае, если « тот же хеш-код находится внутри ».

РЕДАКТИРОВАТЬ:
Как упомянул @Steve в своем комментарии, реализация BitSet не самая большая памятьэффективный.Но есть более эффективные для использования в памяти реализации набора битов - хотя и не встроенные.

Answer 4

Нет такой встроенной структуры данных, потому что такая структура данных требуется редко.Однако его легко построить.

public class HashCodeSet<T> {

    private final HashSet<Integer> hashCodes;        

    public MyHashSet() {
        hashCodes = new HashSet<>();
    }         

    public MyHashSet(int initialCapacity) {
        hashCodes = new HashSet<>(initialCapacity);
    }         

    public HashCodeSet(HashCodeSet toCopy) {
        hashCodes = new HashSet<>(toCopy.hashCodes);
    } 

    public void add(T element) {
       hashCodes.add(element.hashCode());
    }

    public boolean containsHashCodeOf(T element) {
       return hashCodes.contains(element.hashCode());
    }        

    @Override
    public boolean equals(o: Object) {
        return o == this || o instanceof HashCodeSet && 
                ((HashCodeSet) o).hashCodes.equals(hashCodes);
    }        

    @Override
    public int hashCode() {
        return hashCodes.hashCode(); // hash-ception
    } 

    @Override
    public String toString() {
        return hashCodes.toString();
    }
}