Mryntu

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 

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