I was presuming that you'd want more nodes per bucket, but I suppose once you have a hash that can expand and contract efficiently that becomes less of an problem. The issue though with having an average of 1 node is that about 1/3 of the buckets will have no nodes (wasted space), and about 1/3 will have 2 or more (longer lookups).
Yes, for an efficient closed hash of a larger structure, you'd need to store both a pointer to structure and a means of disambiguation so that that you don't have to follow the pointer to (probabilistically) test if you have a matching entry. For a cuckoo, this might be the hash of the other slot, so it's not entirely wasted space, but it would add 8B or so to each entry. On the other hand, we're presuming a large struct anyway, this might not be too much extra burden.
The model that I'm mentally comparing to is an 2-way cuckoo hash with 8 slots per bucket, with a single SIMD compare to test for a match. It's an approach that makes a lot of sense to me. It's not quite what they describe, but if you haven't seen it, you might check out this paper: https://www.cs.princeton.edu/~mfreed/docs/cuckoo-eurosys14.p...
In any case, neat stuff to think about. Thanks for answering questions throughout the thread.
Yes, for an efficient closed hash of a larger structure, you'd need to store both a pointer to structure and a means of disambiguation so that that you don't have to follow the pointer to (probabilistically) test if you have a matching entry. For a cuckoo, this might be the hash of the other slot, so it's not entirely wasted space, but it would add 8B or so to each entry. On the other hand, we're presuming a large struct anyway, this might not be too much extra burden.
The model that I'm mentally comparing to is an 2-way cuckoo hash with 8 slots per bucket, with a single SIMD compare to test for a match. It's an approach that makes a lot of sense to me. It's not quite what they describe, but if you haven't seen it, you might check out this paper: https://www.cs.princeton.edu/~mfreed/docs/cuckoo-eurosys14.p...
In any case, neat stuff to think about. Thanks for answering questions throughout the thread.