Check if an array exists in a HashSet

Question

How do I check if an array exists in a HashSet?

For example:

int[] a = new int[]{0, 0};

HashSet<int[]> set = new HashSet<>();
set.add(a);

Then:

int[] b = new int[]{0, 0};

set.contains(b); // ===> true

Answer 1

Using arrays

    int[] a = new int[] { 0, 0 };
    HashSet<int[]> set = new HashSet<>();
    set.add(a);

    int[] b = new int[] { 0, 0 };
    
    boolean contains = set.stream().anyMatch(c -> Arrays.equals(c, b));
    
    System.out.println("Contains? " + contains);

Output:

Contains? true

It doesn’t exploit the fast look up of a HashSet though. As noted in the comments, this is not possible because equals and hashCode for arrays doesn’t consider arrays containing the same numbers in the same order equal. An array is only considered equal to itself. We therefore need a linear search through the set to find the array containing the same numbers if there is one. I am using a stream pipeline for that. You may alternatively use a loop.

Faster: using lists

To exploit the fast lookup in a HashSet you may use lists instead of arrays:

    List<Integer> a = List.of(0, 0);
    HashSet<List<Integer>> set = new HashSet<>();
    set.add(a);

    List<Integer> b = List.of(0, 0);
    
    System.out.println("Contains? " + set.contains(b));

Contains? true

The List<Integer> approach has a space penalty, though, since it is storing Integer objects rather than int primitives, which generally takes up more space.

Both space and time efficient: develop a custom class

If the above still isn’t efficient enough — which it is for the vast majority of purposes — you may use your own class for the numbers:

public class IntArray {

    int[] elements;
    
    public IntArray(int... elements) {
        // Make a defensive copy to shield from subsequent modifications of the original array
        this.elements = Arrays.copyOf(elements, elements.length);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(elements);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        IntArray other = (IntArray) obj;
        return Arrays.equals(elements, other.elements);
    }

}

This will allow:

    IntArray a = new IntArray(0, 0);
    HashSet<IntArray> set = new HashSet<>();
    set.add(a);

    IntArray b = new IntArray(0, 0);
    
    System.out.println("Contains? " + set.contains(b));

Contains? true

Now we have the space efficiency of the original int array approach, nearly, and the time efficiency of the hashCode().

More options (thanks, fluffy)

As fluffy notes in the comments, there are still more options, and you may want to research some on your own. I am quoting the comments here:

Also, there can be two key-based solutions if I'm not wrong: something like

public final class IntArrayKey {
    private final int[];
    ...
}

(suffers from possible array mutation or defensive array cloning), or something like

public final class Key<T> {
    private final Predicate<T> equals;
    private final IntSupplier hashCode;
    public static Key<int[]> of(final int[] array) {
        return new Key<>(that -> Arrays.equals(array, that), () -> Arrays.hashCode(array));
    }

to keep it generic.

And probably one more solution I can think of is using fastutil or Trove instead of List<Integer> (e.g. IntList that overrides equals and hashCode properly). Not sure it worth adding all possible solutions (perhaps there are more?) now. :)

Answer 2

You can use TreeSet instead of HashSet with a comparator that compares the contents of two arrays instead of the hash codes of two array objects. Then you can use TreeSet.contains method as follows:

int[] a = {0, 0};
int[] b = {0, 0};
int[] c = {0, 0};

HashSet<int[]> hashSet = new HashSet<>();
TreeSet<int[]> treeSet = new TreeSet<>(Arrays::compare);

hashSet.addAll(List.of(a, b, c));
treeSet.addAll(List.of(a, b));

System.out.println(hashSet.size()); // 3
System.out.println(treeSet.size()); // 1

System.out.println(treeSet.contains(a)); // true
System.out.println(treeSet.contains(b)); // true
System.out.println(treeSet.contains(c)); // true