31-Jul-2013 13:17, Walter Bright пишет:
On 7/31/2013 1:49 AM, Dmitry Olshansky wrote:
Here key is 32 bits. Surely 2 strings can hash to the exact same 32
bit value.
No, they cannot. The "hash value" is a pointer to the string. The
strings are already inserted into another hash table,
The StringTable ? Then I have to look somewhere else entirely.
so all strings
that are the same are combined. Therefore, all unique strings "hash" to
unique values.
Now that sets things straight ... if they ain't hashes then it isn't a
hash table in the general sense :)
At least that means that contrary to my naive guess calcHash has no
effect whatsoever on the distribution of keys in this AA. The "real hash
function" could be rather biased. I've got to dig a bit deeper into the
code then.
This resolves only slot collision. It doesn't resolve full hash
collision.
If it was broken the compiler wouldn't work at all :-)
I had a feeling that it can't be that bad :)
--
Dmitry Olshansky
