Order Independent Hash in Java

Question

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.

Answer 1

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);

Answer 2

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