Hash table element existence check

[Cauterite via Digitalmars-d-learn]

On Saturday, 3 September 2016 at 12:33:26 UTC, Illuminati wrote:
> On Saturday, 3 September 2016 at 07:44:28 UTC, Cauterite wrote:
>> On Friday, 2 September 2016 at 19:38:34 UTC, 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.
>>
>> Just do a regular lookup on the hash? It's an O(1) operation, 
>> like 4 instructions.
>
> Huh? One can look up fine, but how does one know if the result 
> is valid or not?

Okay I think I misinterpreted the question. I believe when I did 
this my solution was to have an additional template parameter 
specifying null key values, so the template was like this:

struct HashTbl(
	K, /* key type */
	V, /* value type */
	K NullKey, /* key placeholder value */
	alias hash_key, /* hash function */
	alias keys_eq /* equality function */
) {...

I guess this doesn't really solve the problem, but makes it the 
user's problem.

> I could keep a bitarray, but wasting around 12% space.

That assumes your (K,V) tuples are 1 byte total, right?