Geek asks and answers

Good hashcode and is equal to an implementation for a key that has multiple integer values

I have a hashmap that has these keys: '2 + 4 + 5', '653 + 65 + 1324 + 75'. (integer values ​​indicated by +)

Which can be a good hashcode and equals method, so keys like "2 + 4 + 5", "5 + 4 + 2", "4 + 5 + 2" ... (all permutation 2,4, 5) should return the same hashcode value, and equals should return true.

I plan to take the integer values ​​in the key, sort them, put them in ascending order in the string and call this hashcode and equals method. Suppose if I have "5 + 2 + 4", then I would change it to "245" and call the hashcode and equals method. But it will be an expensive operation, because every time I have to do sorting. And all methods in hashmap like put, get ... will again be expensive

Are there other ways to do this in logarithmic or linear time ...

+3
source share
3 answers
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);
    }
}

Test code:

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"
}
+1
source

A good hashcode algorithm should return very different hashes for minor differences in input. In your case, you also think that the permutations of the values ​​are equal.

, , , ( ):

, , .

-,

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

simple but effective:

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

    return hash;
}
+1
source

More articles:


All Articles