Hash table element existence check

[Illuminati via Digitalmars-d-learn]

On Friday, 2 September 2016 at 19:48:30 UTC, Steven Schveighoffer 
wrote:
> On 9/2/16 3:38 PM, Illuminati wrote:
>> I am trying to create a hash table and would like an efficient 
>> way to be
>> able to know if an element exists to test for collisions.
>
> You mean you are writing your own hash table, or you want to 
> use a D hash table (associative array)?
>

First.

>> I could keep a bitarray, but wasting around 12% space. I could 
>> use
>> pointers(null check) to elements but this creates 
>> fragmentation. It is
>> not terrible, just curious if anyone has a better way?
>
> I'm not sure I understand the question. Hash tables have many 
> many many different ways to implement. Obviously, marking empty 
> buckets somehow is necessary.
>
> -Steve

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.