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?
