After reviewing the theory behind general cuckoo hashing, it turned
out that insert operation atomicity should better be achieved through
restore-when-fail than through commit-when-succeed. The latter
technique, that I have previously used, would require some graph
analysis to be totally correct.
Additionally, Cuckoo::_pHash function that handles cuckoo partial
hashing will now throw an exception when hash function (potentially
user-provided) does not work well for partial hashing. A hash function
that generates bucket_1 == alternative_bucket(bucket_2, f) for all f,
is now explicitly required.
Besides the above changes, I have also made few minor types modifications.
After reviewing the theory behind general cuckoo hashing, it turned out that insert operation atomicity should better be achieved through restore-when-fail than through commit-when-succeed. The latter technique, that I have previously used, would require some graph analysis to be totally correct.
Additionally, Cuckoo::_pHash function that handles cuckoo partial hashing will now throw an exception when hash function (potentially user-provided) does not work well for partial hashing. A hash function that generates
bucket_1 == alternative_bucket(bucket_2, f)for all f, is now explicitly required.Besides the above changes, I have also made few minor types modifications.