Mrthfx

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).

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. A single bit is stored per hash value.

The Guava library provides an implementation in Java.

There is no data structure like that, but you can create a wrapper around HashSet to suit your needs. Something like this:

public class MyHashSet{



    private HashSet<Integer> set;        



    public MyHashSet(){

        set = new HashSet<>();

    } 



    public void add(int hash) {

       set.add(hash);

    }



    public boolean contains(int hash) {

       return set.contains(hash);

    }

}

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

    }

}

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.

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.