After reading more, it seems the novelty is in the two specific schemes that use these techniques to store data with high probability into tables of extremely high load factors with bounded pointer sizes, which are more complex than simple array indices due to having to resolve which fallback table is storing the key-value pair.
One scheme proves tiny pointer size bounds for fixed length tiny pointers. The other proves bounds for variable length pointers.
Comments
How is this novel?
This is like using a fixed sharding scheme plus delta-compression for indices relative to shard addresses plus varint encoding the deltas.
After reading more, it seems the novelty is in the two specific schemes that use these techniques to store data with high probability into tables of extremely high load factors with bounded pointer sizes, which are more complex than simple array indices due to having to resolve which fallback table is storing the key-value pair.
One scheme proves tiny pointer size bounds for fixed length tiny pointers. The other proves bounds for variable length pointers.