Hash table element existence check

[Steven Schveighoffer via Digitalmars-d-learn]

On 9/3/16 8:30 AM, Illuminati wrote:

> Yes, one must have a way to mark empty "buckets"(I hate that term! Seems
> so banal for some reason ;/)
>
> If using pointers, which is what I use, then null means empty, but one
> can't use inline structs and which then can create data fragmentation.
> If the structs are inline, there is no way to know if the element is a
> valid struct or empty. One could test against the .init, say, but I
> don't think any of that is safe.
>
> Hence a bitmap could be used in that case, but wastes a lot of space. I
> don't see any other way though. Pointers, also, waste memory rather than
> structs inline and effectively is a bitmap but does save space for
> sparse maps.

In general, there may not be a way to do this. Are you storing hash 
values to optimize equality check and rehashing? If so, then you may be 
able to flag some hash value as "empty". Other than that, you'd need 
some mechanism to flag a value as a "sentinel" empty value, or store the 
flag inline with the elements.

Note that there are always tradeoffs, which is why hash table has so 
many solutions :)

Using pointers to elements can lead to fragmentation, but what if your 
pointers and elements are stored in the same memory segment, or at least 
2 memory segments (one array for pointers, one for elements)? And when 
you rehash, having inline storage is going to be more costly due to all 
the copying, and storing external references to elements is dangerous.

If there was one best solution, everyone would use it...

-Steve