3

我的哈希图具有这样的键：'2+4+5'、'653+65+1324+75'。（由 + 号分隔的整数值）

什么可能是一个好的哈希码和 equals 方法，以便像“2+4+5”、“5+4+2”、“4+5+2”这样的键......（2、4、5的所有排列）应该返回相同的哈希码值，equals 应该返回 true。

我打算取键中的整数值，对它们进行排序，将它们按升序放入一个字符串中，然后调用该字符串的 hashcode 和 equals 方法。假设如果我有“5+2+4”，那么我会将其更改为“245”并调用字符串 hashcode 和 equals 方法。但这将是一项昂贵的操作，因为每次我都必须进行排序。哈希图中的所有方法，如 put,get... 将再次变得昂贵

有没有其他方法可以在对数或线性时间内做到这一点......

4

3 回答 3

2

一个好的哈希码算法应该为输入的细微差异返回非常不同的哈希值。在您的情况下，您还认为值的排列是“相等的”。

似乎一个好方法是解析组成整数然后对它们进行排序（一种简单的方法来确保比较顺序一致）然后：

如果两个值具有相同的排序成分数，则认为它们相等。

使用经过验证的哈希方法，例如

hash = value1 + 31 * value2 + 31 * 31 * value3 + 31 * 31 * 31 * value4 + etc.
于 2012-04-23T22:49:49.657 回答
1

简单而有效：

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

    return hash;
}
于 2012-04-23T22:55:50.333 回答
1 
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-23T23:07:01.193 回答