Chronicle-Map/spec/4-hashing-algorithms.md

4. The Chronicle Map Key Hashing and Checksum Algorithms

Keys in Chronicle Map are arbitrary sequences of bytes. xxHash algorithm (XXH64 version) is applied to the key, to obtain the primary key hash code. Then the hashSplitting algorithm is applied, to determine the segment in which the key should be stored, and the part of the key hash code to be stored in a segment tier's hash lookup.

The reference Java implementation: XxHash_r39. Although the Java implementation class has _r39 suffix, the xxHash algorithm is stable since r3 and won't change in the future. A different version of the algorithm could have a different name.

Checksum algorithm

Primary checksum

The primary checksum is a 64-bit value.

If the 2nd field of the stored entry structure ends at the same address, as the 6th field of the same structure starts, i. e. the value size is 0, and the size itself is stored using 0 bytes, and there is no value alignment, the key hash code is the primary checksum.

Otherwise, the xxHash algorithm (XXH64 version) is applied to the memory range between the end of the 2nd field of the stored entry structure and the end of the 5th field, i. e. between the end of the stored key and the end of the stored value. The resulting hash value is called payload checksum.

xxHash is used to compute the payload checksum instead of CRC32, because the Java implementation of CRC32 appears to be slower than xxHash while having the same (if not worse) quality, and the native CRC32 implementation, using specialized processor instructions, is available from Java only via JNI, having significant per-call costs, that eliminates any benefits.

Then the following procedure is used to compute the primary checksum:

long K2 = 0x9ae16a3b2f90404fL;
long mul = K2 + (keySize << 1);
long a = keyHashCode + K2;
long c = ((payloadChecksum >>> 37) | (payloadChecksum << 27)) * mul + a;
long d = (((a >>> 25) | (a << 39)) + payloadChecksum) * mul;
long a1 = (c ^ d) * mul ^ ((c ^ d) * mul >>> 47);
long primaryChecksum = ((d ^ a1) * mul ^ ((d ^ a1) * mul >>> 47)) * mul;

where the keySize is the key sequence length in bytes, keyHashCode is the key hash code, and the payloadChecksum is the payload checksum, computed on the previous step. The given procedure code is in Java language.

The above procedure is actually the CityHash and FarmHash algorithm for bytes sequences of lengths between 8 and 16 ( CityHash and FarmHash are equivalent for such input lengths), where keySize is the length of the input sequence, keyHashCode value is the starting 8 bytes of the sequence, payloadChecksum is the ending 8 bytes of the sequence. This procedure presumably has good hashing properties, however it was not checked for the changed semantics of the three parameters.

Entry checksum

Entry checksum is 4 bytes long, it is obtained by XOR-ing lowest and highest 32 bits of the primary checksum. The entry checksum is stored in the 6th field of the stored entry structure.

The reference Java implementation: HashEntryChecksumStrategy.