Come utilizzare HashSet per trovare elementi comuni in due matrici comparabili?

Question

EDIT: La firma del metodo

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

è sbagliato. Dovrebbe essere

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

ma cambiarlo nel mio IDE incasina tutto. Ho quasi la sensazione di essere andato oltre le mie conoscenze perché non capisco completamente gli Insiemi, e l'array 2D mi sta rovinando molto.

sono tenuto a scrivere un algoritmo che prende due paragonabili array, itera attraverso di loro con efficienza temporale lineare, e visualizza gli elementi comuni. Ho letto che l'utilizzo di un HashSet mi ha dato l'efficienza temporale più veloce, ma ho raggiunto un punto morto. Ecco perché:

Ci hanno dato le istruzioni, e una singola linea di codice, che è la firma del metodo

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

che significa che devo restituire l'array 2d, "collezioni". Ho mandato via email il mio prof utilizzando HashSets e mi è stato dato il via libera, tranne che ho questo problema:

"È possibile utilizzare HashSet all'interno del metodo findCommonElements, ma sarà necessario poter contare il numero di confronti Sebbene l'hashing sia in genere molto efficiente, alcuni confronti verranno effettuati in caso di collisioni, per cui è necessario avere accesso al codice sorgente per l'HashSet che si utilizza. È inoltre necessario un metodo "getComparisons()" in la classe CommonElements per restituire il numero di confronti. "

In due semestri di programmazione, non ho imparato HashSet, Maps, Tabelle, ecc. Sto cercando di impararlo da solo, e non capisco completamente le collisioni.

Il mio codice accetta i due array e restituisce gli elementi comuni, ma la mia dichiarazione di ritorno è fasulla poiché in pratica l'ho scritta in modo da compilare (la matrice 2d Comparable è il parametro).

Sono sulla buona strada con questo? Ecco il codice:

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 Ho dimenticato di dire che ho importato gli Apache Commons Array Utils. Molto utile.

L'ho capito. Grazie per tutto il vostro aiuto. Ho un metodo principale che chiama un'istanza della classe 3 volte e 3 metodi di test, ma quelli sono irrilevanti. Ecco cosa mi stava dando problemi, e ora funziona.:-)

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 
    } 

Answer 2

HashSet.add(E e) restituisce false se non riesce a aggiungere e al Set, in modo che possiamo dire:

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

Che cosa si può fare è qualcosa di simile:

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 
} 

Nota che è necessario import java.util.Arrays;