Store and find if a certain array is already stored

Question

My program checks multiple boolean arrays (length 30 each) and I would like to know if I already checked that array. I thought the best way to handle this problem would be to store all the arrays and search for the new array in the set of all the arrays but I don't know what structure I should use. At first, I though hashtable would be the best but it looks like I can't use them with arrays. I looked for set and list but I have no clue what to use !

Edit/clarification: Hey it's my first question here and I'm surprised how many answers I received, thanks a lot ! Lot of people says they are unsure about what exactly I'm looking for so I'll try to clarify:

I have multiple boolean arrays of length 30 where the order is important ( order of elements in the array).

I receive one array at a time and I want to check if I already received the same array (same element, same order). I don't need to store them( I don't need any index, I don't want to know how many arrays I received), don't need anything except to know if I already received the array.

Answer 1

A boolean array is basically a list of bits. Since array size is 30, and an int is a 32-bit value, you can convert the array into an int. With a long you could support arrays up to 64 in size.

So, first convert your array to an int:

private static int toBits(boolean[] array) {
    if (array.length > 32)
        throw new IllegalArgumentException("Array too large: " + array.length);
    int bits = 0;
    for (int i = 0; i < array.length; i++)
        if (array[i])
            bits |= 1 << i;
    return bits;
}

Then keep track using a Set<Integer>:

private Set<Integer> alreadySeen = new HashSet<>();

private boolean firstTime(boolean[] array) {
    return ! this.alreadySeen.add(toBits(array));
}

This provides a very fast and low-memory implementation that can handle lots of boolean arrays.

Answer 2

You can try an adjacency list or perhaps an array/arraylist of an Object that you call 'Pair' for example where this object has two attributes , the first is an array(the array you checked or didn't check yet) and the second attribute is a boolean value that denotes whether this array has been visited or not.

Answer 3

You can create a Wrapper class that holds array (content) and a flag. And, instead of storing array of arrays, you can store array of objects of this class. Have a look at the example below:

public class ArrayWrapper {

        private boolean checked;
        private boolean[] content;

        /**
         * @return the checked
         */
        public boolean isChecked() {
            return checked;
        }
        /**
         * @param checked the checked to set
         */
        public void setChecked(boolean checked) {
            this.checked = checked;
        }
        /**
         * @return the content
         */
        public boolean[] getContent() {
            return content;
        }
        /**
         * @param content the content to set
         */
        public void setContent(boolean[] content) {
            this.content = content;
        }
    }

Now, you can create a List<ArrayWrapper> or ArrayWrapper[], iterate through it and set checked to true once the array (content) is checked.

Answer 4

Use Arrays.equals(array1, array2)

This method returns true if the two specified arrays of booleans are equal to one another. Two arrays are considered equal if both arrays contain the same number of elements, and all corresponding pairs of elements in the two arrays are equal.

I’m giving you a brute force solution.

List<boolean[]> arrs = new ArrayList<>();
while (true) {
    boolean[] receivedArr = receive();
    for (boolean[] existingArr : arrs) {
        if (Arrays.equals(existingArr, receivedArr)) {
            drop(receivedArr);
            break;
        }
        arrs.add(receivedArr);
    }
}

Answer 5

You can use an array :)

If you have n arrays, then create a boolean array of size n. Let's call it checked[].

So if checked[5] == true, you already checked the fifth array.

Another option would be to use the index 0 of each array as the 'checked flag'.

Answer 6

Thanks for your clarification!

HashMap is still a good answer using Arrays.hashCode() to create your key object. Like so:

HashMap<Integer, Boolean> checked = new HashMap<>();

/**
 * Returns true if already checked; false if it's new
 */
public boolean isChecked(Boolean [] array) {
    int hashCode = Arrays.hashCode(array);
    Boolean existing = checked(hashCode);
    if (existing == null) {
        checked.put(hashCode, true);
        return true;
    }
    return false;
}