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);
     if (aa)
         size_t i;
         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 ***

         while (e)
             if (key == e->key)
                 return e->value;
             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 collision.

     return NULL;    // not found

Dmitry Olshansky

Reply via email to