Looking at the actual code (https://github.com/fastserial/lite3/blob/main/src/lite3.c#L2...), it seems like it performs up to 128 probes to find a target before failing, rather than bailing immediately if a collision is detected. It seems like maybe the documentation needs to be updated?
It's a bit unfortunate that the wire format is tied to a specific hash function. It also means that the spec will ossify around a specific hash function, which may not end up being the optimal choice. Neither JSON nor Protobuf have this limitation. One way around this would be to ditch the hashing and use the keys for the b-tree directly. It might be worth benchmarking - I don't think it's necessarily any slower, and an inline cache of key prefixes (basically a cheapo hash using the first N chars) should help preserve performance for common cases.
> It seems like maybe the documentation needs to be updated
Looks like it, yes:
/**
Enable hash probing to tolerate 32-bit hash collisions.
Hash probing configuration (quadratic open addressing for 32-bit hashes:
h_i = h_0 + i^2)
Limit attempts with `LITE3_HASH_PROBE_MAX` (defaults to 128).
Probing cannot be disabled.
*/
#ifndef LITE3_HASH_PROBE_MAX
#define LITE3_HASH_PROBE_MAX 128U
#endif
#if LITE3_HASH_PROBE_MAX < 2
#error "LITE3_HASH_PROBE_MAX must be >= 2"
#endif
> It also means that the spec will ossify around a specific hash function
It is a bit ugly, and will break backwards compatibility, but supporting a second hash function isn’t too hard.
You can, on load, hash a few keys, compare them to the hashes, and, from that, if the input has many keys with high probability, infer which hash function was used.
There also might be spare bit somewhere to indicate ‘use the alternative hash function’.
> The JSON standard requires that the root-level type always be an ‘object'
> or 'array'. This also applies to Lite³.
I don’t think that is true, and https://www.json.org/json-en.html agrees with that. Single values (numbers, strings, booleans, null) also are valid json.
It's a bit unfortunate that the wire format is tied to a specific hash function. It also means that the spec will ossify around a specific hash function, which may not end up being the optimal choice. Neither JSON nor Protobuf have this limitation. One way around this would be to ditch the hashing and use the keys for the b-tree directly. It might be worth benchmarking - I don't think it's necessarily any slower, and an inline cache of key prefixes (basically a cheapo hash using the first N chars) should help preserve performance for common cases.