良好的哈希码，等于具有多个整数值的键的实现

Question

我有这样的标签：'2+4+5' ， '653+65+1324+75'。由 + 号分隔的整数值）

什么是好的哈希码和等于方法，以便像"2+4+5"、"5+4+2"、"4+5+2"这样的键......（2,4,5 的所有排列）应返回相同的哈希码值，等于应返回 true。

我打算获取键中的整数值，对它们进行排序，将它们按升序放入字符串中，并调用该字符串哈希码和等于方法。假设如果我有"5+2+4"，那么我会将其更改为"245"并调用字符串哈希码和等于方法。但这将是一个昂贵的操作，因为每次我都必须进行排序。以及哈希图中的所有方法，例如放置，获取...会再次昂贵

在日志或线性时间内还有其他方法可以做到这一点吗？

Answer 1

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

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

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

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

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

Answer 2

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"
}

Answer 3

简单而有效：

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