hashCodeとArrays.equalsを使用した場合の潜在的なハッシュの問題

Question

私のコードのコメントで説明しているように、お互いの順列である入力ファイルから文字列のペアの数を見つけることです。たとえば、 "ABCD"と "BCDA"は互いの順列であり、ペアが見つかったことを意味します。

私のプログラムの主なバルクは以下のようにある：

/** 
* Finds the number of pairs of strings that are permutations of each other. 
* 
* A hash map is created with a hash code generated from the array formed using the getFrequency 
* method as key and a pair containing a string array and the number of times a permutation of that 
* particular string array has been found as value. 
* 
* If a permutation is already in the hash table previously, increment the counter. 
*/ 
public static int findPairs(String fileName) { 
    try { 
     //Sets up the necessary file readers 
     FileReader dataFile = new FileReader(fileName); 
     BufferedReader bufferedDataFile = new BufferedReader(dataFile); 

     String line = bufferedDataFile.readLine(); 

     //Finds the number of entries in the file 
     int num = Integer.parseInt(line); 

     int counter = 0; 
     int accumulator = 0; 

     HashMap<Integer, Pair> store = new HashMap<>(); 

     for (int i = 0; i < num; i++) { 
      String current = bufferedDataFile.readLine(); 
      int[] currentArr = getFrequency(current); 
      int currHashCode = Arrays.hashCode(currentArr); 

      if (store.containsKey(currHashCode)) { 
       Pair pairToCheck = store.get(currHashCode); 
       int[] arrToCheck = pairToCheck.getArr(); 

       //Double checking, in case there is a collision and unequal arrays 
       //have the same hashCode 
       if (Arrays.equals(currentArr, arrToCheck)) { 
        counter = pairToCheck.getCount(); 
        pairToCheck.updateCount(); 
       } else { 
        //if the current bucket is not empty, and not a permutation of the input string, 
        //continue to conduct a linear probe 
        while (pairToCheck != null && !Arrays.equals(currentArr, arrToCheck)) { 
         currHashCode++; 
         pairToCheck = store.get(currHashCode); 
         arrToCheck = pairToCheck.getArr(); 
        } 

        //if the current bucket is empty, add the new pair into the position 
        if (pairToCheck == null) { 
         counter = 0; 
        //otherwise, a permutation has been found later in the linear probe! 
        } else { 
         counter = pairToCheck.getCount(); 
         pairToCheck.updateCount(); 
        } 
       } 
      //no such permutation in the hash table yet!  
      } else { 
       counter = 0; 
      } 

      //Updates the accumulator using the counter. If there were already other strings 
      //which are permutations of the current string, the current string will be able to 
      //form a pair with each of these strings. 
      accumulator += counter; 

      //Updates the hash map only if the permutation has not been stored previously 
      if (counter == 0) { 
       Pair newPair = new Pair(currentArr, 1); 
       store.put(currHashCode, newPair); 
      } 
     } 

     //Close the file reader 
     bufferedDataFile.close(); 

     return accumulator; 
    } catch (Exception e) { 
     System.out.println(e); 
    } 

    //In the event of an error, return -1 
    return -1; 
} 

JavaのhashCodeとArrays実装のような操作に起因することができますいくつかの潜在的な問題は何ですか？これは特に私が渡すべきいくつかの私的なテストケースが与えられていて、私がそれらのいくつかを渡すことができる間に、私は繰り返し失敗するものがあるからです。私はそれが私が衝突を扱っている方法と関係していると思う...しかし、私はこれを複数回検査したが、エラーがどこにあるのかはまだ不明である。どんな助けでも大歓迎です！

EDITは：

public static int[] getFrequency(String s) { 
    //There are 128 legal ascii characters 
    int[] charArr = new int[128]; 

    //Iterate through the given string, and increment the count for a character using its 
    //ascii value to locate its position in the array 
    for (int i = 0; i < s.length(); i++) { 

     char c = s.charAt(i); 
     int ascii = (int) c; 
     charArr[ascii] += 1;  
    } 

    return charArr; 
} 

EDIT 2：ペア：

public class Pair { 

    private int[] m_arr; 
    private int m_count; 

    public Pair(int[] arr, int count) { 
     this.m_arr = arr; 
     this.m_count = count; 
    } 

    public int[] getArr() { 
     return this.m_arr; 
    } 

    public int getCount() { 
     return this.m_count; 
    } 

    public void updateCount() { 
     this.m_count++; 
    } 

} 

Answer 1

アナグラムを見つけることが知られている問題である要求を1として、ここに私のgetFrequency方法です。通常の解決方法は、文字列をソートしソートされた文字列を比較することです。ソートすると、「ABCD」と「BCDA」の両方が「ABCD」になります。

ソートされた文字列をセットに格納すると、簡単に一致するものを見つけることができます。ソートされていないバージョンの文字列を簡単に取得できるように、ソートされたバージョンとソートされていないバージョンを別々に保持するクラスを作成します。

"BB"は "AC"と同じ値にハッシュされるため、ハッシュ関数は良くありません。ソートされたバージョンの文字列に対して、より良いハッシュ関数を使用します。