How to use a HashSet to search for common elements in two comparable arrays?

Question

EDIT : method signature

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

wrong. It should be

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

but changing it in my IDE will ruin everything. I almost feel like I went beyond my knowledge, because I do not quite understand Sets, and the 2D array annoys me badly.

I need to write an algorithm that takes two Comparable arrays , iterates through linear time efficiency, and displays common elements. I read that using HashSet will give me the fastest time efficiency, but I am at a standstill. That's why:

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

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

which means that I have to return a 2d array, "collections". I emailed my professor to use HashSets, and they gave me the go-ahead, except for this problem:

"You can use HashSets inside the findCommonElements method, but you will need to count the number of comparisons completed. Although hashing is usually very effective, some comparisons will be made in case of collisions. You must have access to the source code of the HashSet you use. You also need the getComparisons () method in to your CommonElements class to return the number of comparisons. "

For two semesters of programming, I have not studied HashSets, Maps, Tables, etc. I am trying to learn this myself, and I do not quite understand the conflicts.

My code takes two arrays and returns common elements, but my return statement is disgusting since I basically wrote it to compile (2d Comparable array is a parameter).

Am I on the right track 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

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

I get it. Thank you for your help. I have a main method that calls an instance of the class 3 times and three testing methods, but that doesn't matter. Here is what gave me problems 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 (ie 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 } 

Answer 2

HashSet.add(E e) returns false if it fails to add e to 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 need import java.util.Arrays;