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

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

Ответ 1

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

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

Ответ 2

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

Ответ 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 не самая эффективная в BitSet памяти. Но есть более эффективные реализации памяти набора битов - хотя и не встроенные.

Ответ 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();
    }
}