1
$\begingroup$

(I originally posted this on stackoverflow but thought it would be a better fit here)

I'm trying to understand the Ketama hash code used in consistent hashing.

link and snippet below:

public static Long md5HashingAlg(String key) {
    MessageDigest md5 = null;
    try {
        md5 = MessageDigest.getInstance("MD5");
    } catch (NoSuchAlgorithmException e) {
        log.error("++++ no md5 algorythm found");
        throw new IllegalStateException("++++ no md5 algorythm found");
    }
    md5.reset();
    md5.update(key.getBytes());
    byte[] bKey = md5.digest();
    long res = ((long) (bKey[3] & 0xFF) << 24)
        | ((long) (bKey[2] & 0xFF) << 16)
        | ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF);

    return res;
}

I think I understand what the code is doing, but I don't get why they're doing it. Particularly, I'm wondering why:

  1. the code discards the least significant 8 bytes of the 16-byte MD5 and uses only the first four (bKey[0] through bKey[3]).

  2. the code "flips" the significant bytes meaning that, of the 4 bytes from 1., the least significant now become the most significant (at least that's what I understand happens from the & 0xffs and left shifts).

I also came across another piece of code that uses the same logic as above, but in addition performs an & 0xffffffffL on the result to "truncate to 32-bits".

link and snippet:

case KETAMA_HASH:
    byte[] bKey = computeMd5(k);
    rv = ((long) (bKey[3] & 0xFF) << 24)
        | ((long) (bKey[2] & 0xFF) << 16)
        | ((long) (bKey[1] & 0xFF) << 8)
        | (bKey[0] & 0xFF);
    break;
    default:
    assert false;
}

return rv & 0xffffffffL; /* Truncate to 32-bits */

Could someone help me understand the rationale behind picking these particular bytes and re-arranging them in this particular fashion?

$\endgroup$
2
$\begingroup$

This is simply a way to generate 32-bit hash for the string. Assuming that MD5 is a good cryptographic hash function, it doesn't matter which bits you take from the hash and in which order you arrange them (as long as they are different bits). The behavior of the bits should be equally unpredictable.

There's no explanation, why exactly 32 bits are required, though my guess is that it enables the use of simple integer types in the code.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.