mirror of
https://github.com/OpenHFT/Chronicle-Map.git
synced 2021-09-13 01:26:12 +00:00
65 lines
3.7 KiB
Markdown
65 lines
3.7 KiB
Markdown
# 4. The Chronicle Map Key Hashing and Checksum Algorithms
|
|
|
|
Keys in Chronicle Map are arbitrary sequences of bytes. [xxHash
|
|
](https://github.com/Cyan4973/xxHash/) algorithm (XXH64 version) is applied to the key, to obtain
|
|
the primary key hash code. Then the [`hashSplitting`](3_1-header-fields.md#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`](
|
|
> https://github.com/OpenHFT/Chronicle-Algorithms/blob/chronicle-algorithms-1.1.6/src/main/java/net/openhft/chronicle/algo/hashing/XxHash_r39.java).
|
|
> Although the Java implementation class has `_r39` suffix, the xxHash algorithm is stable since r3
|
|
> and [won't change in the future](
|
|
> https://github.com/Cyan4973/xxHash/issues/34#issuecomment-169176338). 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
|
|
](3-memory-layout.md#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](https://github.com/Cyan4973/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:
|
|
```java
|
|
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](https://docs.oracle.com/javase/specs/jls/se8/html/index.html).
|
|
|
|
> The above procedure is actually the [CityHash](https://github.com/google/cityhash) and [FarmHash](
|
|
> https://github.com/google/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](#primary-checksum). The entry checksum is stored in the 6th field of the [stored entry
|
|
structure](3-memory-layout.md#stored-entry-structure).
|
|
|
|
> The reference Java implementation: [`HashEntryChecksumStrategy`](
|
|
> ../src/main/java/net/openhft/chronicle/hash/impl/stage/entry/HashEntryChecksumStrategy.java). |