CODEWITHSUNDEEP
javaalgorithm
vjk
vjk

Reputation: 2283

good hashcode and equals implementation for a key having multiple integer values

I have hashmap that has keys like this:'2+4+5' , '653+65+1324+75'.(integer values delimited by a + sign)

What could be a good hashcode and equals method so that keys like '2+4+5', '5+4+2', '4+5+2' ... (all the permutation of 2,4,5) should return the same hashcode value and equals should return true.

I am planning to take the integer values in the key, sort them, put them in an ascending order into a string and call that strings hashcode and equals method. Suppose if I have '5+2+4' then I would change that to "245" and call the strings hashcode and equals method. But this is going to be an expensive operation since each time I have to do sorting. And all the methods in the hashmap like put,get... would again be expensive

Are there any other ways of doing this in a log or linear time...

Upvotes: 3

Views: 1340

Answers (3)

meriton
meriton

Reputation: 70564

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

Upvotes: 1

ratchet freak
ratchet freak

Reputation: 48196

simple yet effective:

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

    return hash;
}

Upvotes: 1

Eric J.
Eric J.

Reputation: 150108

A good hashcode algorithm should return very different hashes for slight differences in input. In your case, you also consider permutations of the values to be "equal".

It seems a good approach would be to parse the constituent integers and then sort them (one simple way to ensure a consistent order for comparison) then:

Consider two values equal if they have the same sorted constituent numbers.

Use a proven hash approach such as

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

Upvotes: 2

Related Questions