Michael Rynn wrote:
I do not think this is true of current builtin AA,
Correct, it is not.
and therefore not true
of this enhanced implementation. I note the current builtin _aaGet will
locate a new node by pointer, maybe do a rehash, and then return the node
it previously relocated. Relax, this AA has no fear of nodes moving
around on rehash. They are just relinked. All done with pointers.
I was looking at:
http://www.dsource.org/projects/aa/browser/trunk/randAA/RandAA.d
which contains the data structures:
K* _keys;
V* vals;
ubyte* flags;
i.e. 3 parallel arrays. I apologize since you are apparently not referring to
that, but this:
http://www.dsource.org/projects/aa/browser/trunk/druntime/aaA.d
but that uses the data structure:
aaNode *left_;
aaNode *right_;
static if (keyBig)
hash_t hash_;
so I don't see where the linear congruent random probe thingy is <g>. You
*could* get rid of the left and right pointers and use linear congruent probing,
and that might be worth a try.
