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.
