CODEWITHSUNDEEP
javahashsetunordered
Marmite Bomber
Marmite Bomber

Reputation: 21063

Order Independent Hash in Java

I'd like to calculate a hash of a set of strings in Java. Yes I can sort the strings and calculate the MD5 hash iterative using digest.update. But I'd prefer to omit the sort and use something like combineUnordered https://github.com/google/guava/wiki/HashingExplained There is a lot of similar question asking the same such as Order-independant Hash Algorithm but non of them provides a simple example showing how to calculate iterative an order independent hash in Java.

Upvotes: 8

Views: 3185

Answers (3)

DanyloStackylo
DanyloStackylo

Reputation: 420

Here's an example using Guava to calculate order-independent hash of a set of strings:

import java.util.Set;

import com.google.common.base.Charsets;
import com.google.common.hash.HashCode;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;

...

public String hash(final Set<String> strings) {
    final HashFunction function = Hashing.murmur3_128();

    // Hashing.combineUnordered will throw an exception if input is empty.
    if (strings.isEmpty()) {
        return function.newHasher()
            .hash()
            .toString();
    }

    final List<HashCode> stringsHashes = strings.stream()
            .map(string -> function.newHasher()
                    .putString(string, Charsets.UTF_8)
                    .hash())
            .toList();

    return Hashing.combineUnordered(stringsHashes).toString();
}

Upvotes: 0

Magnus
Magnus

Reputation: 8300

Just XOR each hash and the order wont matter, plus the hash size will be fixed rather than grow with the size of the collection.

Hashcode using built in java string hashcode:

int hashcode = strings.stream()
        .mapToInt(Object::hashCode)
        .reduce(0, (left, right) -> left ^ right);

Hashcode using guava and MD5 like the question asked:

Optional<byte[]> hash = strings.stream()
        .map(s -> Hashing.md5().hashString(s, Charset.defaultCharset()))
        .map(HashCode::asBytes)
        .reduce((left, right) -> xor(left, right));


static byte[] xor(byte[] left, byte[] right) {
    if(left.length != right.length) {
        throw new IllegalArgumentException();
    }
    byte[] result = new byte[left.length];
    for(int i=0; i < result.length; i++) {
        result[i] = (byte) (left[i] ^ right[i]);
    }
    return result;
}

Upvotes: 6

Elyor Murodov
Elyor Murodov

Reputation: 1028

You can calculate the MD5 hash of each string individually, and then, add them all to get a single hash. That will be order independent. Because addition operation is commutative.

Here is an example (assuming we have a method md5Hex(String str) that calculates md5 hash for a given string and returns the results in hexadecimal format):

String[] strings = {"str1", "str2", "str3", ...};

BigInteger hashSum = BigInteger.ZERO;
for(String s : strings) {
    String hexHash = md5Hex(s);
    hashSum = hashSum.add(new BigInteger(hexHash, 16));
}

String finalHash = hashSum.toString(16);

Upvotes: 1

Related Questions