好散列碼，等於一個具有多個整數值的鍵的實現

我有散列表，它有這樣的鍵：'2 + 4 + 5'，'653 + 65 + 1324 + 75'（用+符號分隔的整數值）好散列碼，等於一個具有多個整數值的鍵的實現

什麼可能是一個好的hashcode和equals方法，以便像'2 + 4 + 5'，'5 + 4 + 2'，'4 + 5 + 2'...這樣的鍵（所有2的排列，4,5）應該返回相同的哈希碼值，等於應該返回true。

我打算在鍵中取整數值，對它們進行排序，將它們按照升序放入一個字符串中，並調用該字符串hashcode和equals方法。假設如果我有'5 + 2 + 4'，那麼我會將它改爲「245」並調用字符串hashcode和equals方法。但是這將是一個昂貴的操作，因爲每次我必須進行分類。而在像放HashMap的所有方法，得到...將再次昂貴

是否有一個日誌或線性時間這樣做的任何其他方式...

來源

2012-04-23 vjk

有一個關鍵的「2 + 4 + 5 「看起來有點腥 - 這真的是一個僞裝的對象嗎？如果是這樣，編寫散列碼可能更自然。 – 2012-04-23 22:57:41

class Combination { 
    final int[] parts; 

    Combination(String str) { 
     String[] strings = str.split("\\+"); 
     parts = new int[strings.length]; 
     for (int i = 0; i < parts.length; i++) { 
      parts[i] = Integer.parseInt(strings[i]); 
     } 
     Arrays.sort(parts); 
    } 

    @Override public int hashCode() { 
     return Arrays.hashCode(parts); 
    } 

    @Override public boolean equals(Object o) { 
     return o instanceof Combination && Arrays.equals(parts, ((Combination) o).parts); 
    } 
}

測試代碼：

public static void main(String[] args) { 
    Set<Combination> set = new HashSet<>(); 
    set.add(new Combination("1+2+3")); 
    set.add(new Combination("1+2+4")); 
    System.out.println(set.contains(new Combination("3+2+1"))); // prints "true" 
    System.out.println(set.contains(new Combination("4+2+1"))); // prints "true" 
    System.out.println(set.contains(new Combination("4+3+1"))); // prints "false" 
}

來源

2012-04-23 23:07:01 meriton

一個好的哈希碼算法應該很返回對於輸入的細微差異，不同的哈希值。在你的情況下，你也會考慮這些值的排列是「相等的」。

這似乎是一個不錯的方法是分析組成的整數，然後對其進行排序（一個簡單的方法，以確保比較一致的順序），則：

考慮兩個值相等，如果它們具有相同的排序組成的數字。

使用經過驗證的哈希方法如

hash = value1 + 31 * value2 + 31 * 31 * value3 + 31 * 31 * 31 * value4 + etc.

來源

2012-04-23 22:49:49

簡單而有效：

public int hashcode(){ 
    int hash=5; 
    for(int i:array) 
     hash=hash*17+i; 

    return hash; 
}

來源

2012-04-23 22:55:50

好散列碼，等於一個具有多個整數值的鍵的實現

回答

相關問題