30-Jul-2013 22:22, Walter Bright пишет:
On 7/30/2013 11:02 AM, Dmitry Olshansky wrote:
What bothers me is that while I've been hacking at this I couldn't
shake off the
feeling that AA code assumes NO FULL HASH COLLISIONS at all?
I don't know what you mean, as it has a collision resolution system. See
embedded code below.
Yes but it does so using full _hash_ alone.
Basically Key is size_t, if we store strings in this AA and they hash to
exactly the same size_t "key" then you'll never find one of them.
Value _aaGetRvalue(AA* aa, Key key)
//printf("_aaGetRvalue(key = %p)\n", key);
size_t len = aa->b_length;
if (len == 4)
i = (size_t)key & 3;
else if (len == 31)
i = (size_t)key % 31;
i = (size_t)key % len;
aaA* e = aa->b[i];
*** ^^^ obviously key is only a hash value ***
if (key == e->key)
e = e->next;
**** ^^^ collision resolution code ^^^ *****
Here key is 32 bits. Surely 2 strings can hash to the exact same 32 bit
value. This resolves only slot collision. It doesn't resolve full hash
return NULL; // not found