AA rehash threshold

[Jerry Quinn via Digitalmars-d]

Steven Schveighoffer <schveiguy at yahoo.com> writes:

> On 11/20/14 5:30 PM, Jerry Quinn wrote:
>> This works nicely for small types, but has gotchas.  For example, if
>> you've got an AA of ints, what value indicates that this is a value
>> folded into the bucket entry vs actually being a pointer?  You'll need
>> extra space to make sure it's safe.  Alignment is another concern.
>> Let's say you have bool for the entry/element flag.  With ints you've
>> doubled the size of the bucket array.
>
> Hm.. the bucket entry will simply be what a node is now. You are actually
> saving space, because you don't need to store that extra pointer to the first
> node.

Almost. You do need a way to indicate that the bucket is empty.  So you
need another flag though it can be smaller than a pointer (for 64 bit).  But
the overhead is low except for things like ints.

> Where it gets dicey is when you rehash. Some of the nodes will be moved into
> the bucket space, some will move out of it. But I don't think it's a big deal,
> as a rehash doesn't happen very often.

True.  Umm, that does raise a question - are addresses of AA contents
required to be stable?  C++11 requires that of its hashtables.  But it
ties your hands when trying to write customized hash tables.