Is there a data structure that only stores hash codes and not the actual objects?

Question

My use-case is that I'm looking for a data structure in Java that will let me see if an object with the same hash code is inside (by calling contains()), but I will never need to iterate through the elements or retrieve the actual objects. A HashSet is close, but from my understanding, it still contains references to the actual objects, and that would be a waste of memory since I won't ever need the contents of the actual objects. The best option I can think of is a HashSet of type Integer storing only the hash codes, but I'm wondering if there is a built-in data structure that would accomplish the same thing (and only accept one type as opposed to HashSet of type Integer which will accept the hash code of any object).

Answer 1

A Bloom filter can tell whether an object might be a member, or is definitely not a member. You can control the likelihood of false positives. Each hash value maps to a single bit.

The Guava library provides an implementation in Java.

Answer 2

You could use a primitive collection implementation like IntSet to store values of hash codes. Obviously as others have mentioned this assumes collisions aren't a problem.

Answer 3

If you want to track if a hash code is already present and to do it memory efficient a BitSet may suite your requirements.

Look at the following example:

  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
  }

The BitSet "implements a vector of bits that grows as needed.". It's a JDK "built-in data structure" which doesn't contain "references to the actual objects". It stores only if "the same hash code is inside".

EDIT:
As @Steve mentioned in his comment the implementation of the BitSet isn't the most memory efficient one. But there are more memory efficient implementations of a bit set - though not built-in.

Answer 4

There is no such built-in data structure, because such a data structure is rarely needed. It's easy to build one, though.

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();
    }
}