java-良好的哈希码,并且等于具有多个整数值的键的实现

由 发布于 Javaalgorithm
 收藏

提问

我有具有这样的键的哈希图：’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”并调用字符串哈希码和equals方法.但这将是一项昂贵的操作,因为每次都要进行排序.哈希图中的所有方法(如put,get …)将再次变得昂贵

还有其他方法可以在对数时间或线性时间内执行此操作吗？

最佳答案

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