How to use HashSet to find common elements in two Comparable arrays?

Question

EDIT: The method signature

    public Comparable[][] findCommonElements(Comparable[][] collections)

is wrong. It should be

    public Comparable[] findCommonElements(Comparable[][] collections)

but changing it in my IDE messes everything up. I almost feel like I've gone beyond my knowledge because I don't fully understand Sets, and the 2D array is messing me up badly.

I am required to write an algorithm that takes two Comparable arrays, iterates through them with linear time efficiency, and displays the common elements. I have read that using a HashSet would give me the fastest time efficiency, but I have reached an impasse. Here's why:

We were given the instructions, and one single line of code, which is the method signature

public Comparable[][] findCommonElements(Comparable[][] collections)

which means I have to return the 2d array, "collections." I emailed my prof on using HashSets, and I was given the go-ahead, except I have this problem:

"You can use HashSets inside your findCommonElements method, but you will need to be able to count the number of comparisons performed. Although hashing is usually very efficient, some comparisons will be made in the event of collisions. To do this you would need to have access to the source code for the HashSet you use. You also need a "getComparisons()" method in your CommonElements class to return the number of comparisons."

In two semesters of programming, I did not learn HashSets, Maps, Tables, etc. I am trying to learn this myself, and I do not fully understand collisions.

My code does take the two arrays and return the common elements, but my return statement is screwy since I basically wrote it so it would compile (the 2d Comparable array is the parameter).

Am I on the right path with this? Here is the code:

public class CommonElements {

    static Comparable[] collection1 = {"A", "B", "C", "D", "E"}; //first array
    static Comparable[] collection2 = {"A", "B", "C", "D", "E", "F", "G"}; //second array
    static Comparable[][] collections = {collection1, collection2}; //array to store common elements. 
    static Set<Comparable> commonStuff = new HashSet<>(); //instance of Set containing common elements

    public static void main(String[] args) {

        CommonElements commonElements = new CommonElements(); //create instance of class CommonElements
        commonElements.findCommonElements(collections); //call the find method

    }
    public Comparable[][] findCommonElements(Comparable[][] collections) {

        Set<Comparable> addSet = new HashSet<>(); //instance of Set to add elements to

        for (Comparable x : collection1) { //adding elements from first array to my addSet
            addSet.add(x);
        }
        for (Comparable x : collection2) {
            if (addSet.contains(x)) {
            commonStuff.add(x); //checking for common elements, add to commonStuff Set
            }
        }
        System.out.println(toString(commonStuff)); //print the toString method

        return collections; //return statement, otherwise Java will whine at me
    }
    public String toString(Set<Comparable> commonStuff) { //this method gets rid of the brackets
        String elements = commonStuff.toString(); //make a String and assign it to the Set
        elements = elements.replaceAll("\\[", "").replaceAll("\\]", ""); //replace both brackets with empty space

        return "Common Elements: " + elements; //return the Set as a new String
    }
}

Answer 1

HashSet.add(E e) returns false if it fails to add e to the Set, so we can say:

if (addSet.add(x)){
    //the collection did not contain x already
} else {
    //the collection contained x
}

So what you can do is something like this:

public Comparable[] findCommonElements(){
    Set<Comparable> collectionSet1 = new HashSet<>(Arrays.asList(collection1));
    Set<Comparable> collectionSet2 = new HashSet<>(Arrays.asList(collection2));
    for (Comparable x : collectionSet1){
        if (!collectionSet2.add(x)){
            commonStuff.add(x);
        }
    }
    return commonStuff.toArray(); //convert HashSet to an array
}

Note that you'll need to import java.util.Arrays;

Answer 2

EDIT I forgot to mention that I imported the Apache Commons Array Utils. Very useful.

I figured it out. Thanks for all your help. I have a main method that calls an instance of the class 3 times, and 3 test methods, but those are irrelevant. Here is what was giving me trouble, and now it works. :-)

public int getComparisons() {
        return comparisons;
    } //method to return number of comparisons
    public static Comparable[] findCommonElements(Comparable[][] collections) {
        /*
        I LEARNED THAT WE HAD TO USE MORE THAN TWO ARRAYS, SO IT WAS BACK
        TO THE DRAWING BOARD FOR ME. I FIGURED IT OUT, THOUGH.
        */
        Comparable[] arr1 = collections[0]; //set initial values to 1 Dimensional arrays so the test methods can read their respective values
        Comparable[] arr2 = collections[1];
        Comparable[] arr3 = collections[2];

        /*
        THE FOLLOWING BLOCK OF CODE TAKES ALL THE PERMUTATIONS OF THE 3 ARRAYS (i.e. 1,2,3; 1,3,2; 2,1,3, etc),
        DETERMINES WHICH ARRAY IS THE SHORTEST, AND ADDS THE LONGER TWO ARRAYS TO A QUERY ARRAY.
         */
        if(arr1.length < arr2.length && arr1.length < arr3.length || arr2.length <= arr3.length) { //shortest array will become hash array. the other two will become a combined query array.
            hashArray = arr1;  //these will be utilized below to put into Sets
            queryArray = ArrayUtils.addAll(arr2, arr3);
        }
        else if(arr2.length < arr1.length && arr2.length < arr3.length || arr1.length <= arr3.length) {
            hashArray = arr2;
            queryArray = ArrayUtils.addAll(arr1, arr3);
        }
        else if(arr3.length < arr1.length && arr3.length < arr2.length || arr1.length <= arr2.length) {
            hashArray = arr3;
            queryArray = ArrayUtils.addAll(arr1, arr2);
        }
        HashSet<Comparable> intersectionSet = new HashSet<>(); //initialize Sets
        HashSet<Comparable> arrayToHash = new HashSet<>();
        for(Comparable element : hashArray) { //add shorter array to hashedArray Set
            arrayToHash.add(element);
        }
        //NOTE FROM THE JAVADOC ON THE IMPLEMENTATION OF .contains() USING HASHSET COMPARISONS
        /**
         * <p>This class offers constant time performance for the basic operations
         * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
         * assuming the hash function disperses the elements properly among the
         * buckets.
         */
        for(Comparable element : queryArray) {
            if(element != null) {
                comparisons++; // increment comparisons with each search
            }
            if(arrayToHash.contains(element)) { //search for matches and add to intersectionSet (.contains uses the equals method to determine if an object is within array)
                intersectionSet.add(element);
            }
        }
        return intersectionSet.toArray(new Comparable[0]); //return Set as Array defined in method signature
    }