🚀 go-pugleaf

zalman@macromedia.com (Zalman Stern) writes:

>In article <44smb1$3km@firma.tera.com>, preston@Tera.COM (Preston Briggs) wrote:
>> _I_ think you're exaggerating.  I don't think you can handle a single
>> successful lookup (or collision) in the amount of time it takes to do
>> a remainder.  If we're hashing strings, there's a string compare
>> implied in either case, not to mention the possibility of 2 or more
>> cache (tlb, ...) misses along the way.

>Yes, a single cache or TLB miss will outweigh a divide. To make Joe's
>claim closer to true, one has to cheat harder. In my case, key strings are
>mostly (but not always) from a well known set but appear in many different
>hash tables. The strings are kept in a single pool and a full 32 bit hash
>value is stored immediately before the string. On entry to the lookup
>routine, the code checks if the string points into this pool. If so, the
>hash value is immediately available and the string comparison is a pointer
>comparison. The hash value still must be reduced to the size of the hash
>table which is done with an and operation.

>Another advantage to 2^n sized tables is that one doesn't have to
>redistribute *all* the hash entries across the table when its size
>changes. I considered using a few prime number schemes, but they all
>became more difficult for dynamically sized hash tables. (Dynamic sizing
>seemed like more of a space and speed win than primes could make up for.)


I thought that dynamic hashing schemes (based on Litwin's linear
hashing) could start with any size of table.  It seems feasable to
start with a prime sized table and expand from there.

Eddie