CODEWITHSUNDEEP
javaalgorithmmathhash
yehyaawad
yehyaawad

Reputation: 126

Good hash for a set of numbers and a special number?

I have arrays of integers such as

[1, 3, 5], 
[7, 2, 10],
[50, 12, 10],
[20, 1, 34],

I'm trying to make a hashing algorithm that given one of these arrays will return a unique hash for each so that I can quickly look if they exist in the HashMap.

The hash should be the same if both arrays contain the same set of numbers and the last number in the array is the same.

For example

// these are the same because they contain the same numbers and have same last number (5)
Hash([3, 1, 5]) -> 5678326 
Hash([1, 3, 5]) -> 5678326

// different hash because the last number in the array is different
Hash([5, 1, 3]) -> 9877124

// different hash because different set of values
Hash([7, 1, 5]) -> 2123466

The values in the arrays are in the rage 0 - 100 and they are all unique (so there can be no duplicates in the array) and the maximum size of the array is 100.

What would be a really good hashing algorithm for this?

Upvotes: 1

Views: 2100

Answers (4)

Alvin Thompson
Alvin Thompson

Reputation: 5448

If you just need to produce a hash for the purpose of storing the arrays in the buckets of a Map or Set, you don't need to create your own hashing function. The one in java.util.Arrays will do. They were designed specifically for this purpose.

Additionally, hash codes don't have to be guaranteed unique--just unlikely to produce a collision. In fact, guaranteeing they're unique would slow down the Map much more than the occasional collision would.

No need to reinvent the wheel--just use java,util.Arrays.hashCode to compute the hash code for your arrays.

Upvotes: -2

shmosel
shmosel

Reputation: 50716

Not the most optimized solution, but it should do what you want:

int hash(int[] array) {
    array = array.clone();
    Arrays.sort(array, 0, array.length - 1);
    return Arrays.hashCode(array);
}

Another option is to add elements to a set and call Objects.hash(set, array[array.length - 1]).

Upvotes: 0

Sean Patrick Floyd
Sean Patrick Floyd

Reputation: 298928

What you describe is a weird setup, but one way to implement it is with a custom Object:

public class YourCustomObject {
    private final int[] allButLast;
    private final int last;

    public YourCustomObject(int[] value){
        this.value = value;
        this.allButLast = Arrays.copyOfRange(value, 0, value.length-1);
        Arrays.sort(allButLast);
        this.last = value[value.length-1];
    }
    private final int[] value;

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }else if (( o instanceof YourCustomObject)) {
            YourCustomObject that = (YourCustomObject) o;
            return last == that.last && Arrays.equals(allButLast, that.allButLast);
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return Objects.hash(allButLast, last);
    }

    public int[] getValue() {
        return value;
    }
}

This object's equals/hashCode properties rely on the same array elements in any order, excluding the last element, which must be the same. You can use this object as a key in a HashMap, and it will work as specified.

Also, since arrays are mutable, I'd probably make a defensive copy in both the constructor and the getter.

Upvotes: 1

Jiri Tousek
Jiri Tousek

Reputation: 12440

Compute hash code for the input as if it was a set, multiply by a prime, and add hash code of last element.

Along the lines of

new HashSet<Integer>(Arrays.asList(input)).hashCode() * 31 + input[input.length - 1]

but for performance you'd probably want to do it manually by adding the input items up in a loop instead of creating a HashSet.

Note that this won't "return a unique hash for each [input]" as you request - you'd need perfect hash function for that which would probably be quite overkill.

Upvotes: 3

Related Questions