好散列码，等于一个具有多个整数值的键的实现

我有散列表，它有这样的键：'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

好散列码，等于一个具有多个整数值的键的实现

回答

相关问题