Re: Fast dictionary with integer keys?
Re: Fast dictionary with integer keys?
- Subject: Re: Fast dictionary with integer keys?
- From: Graham Cox <email@hidden>
- Date: Mon, 16 Mar 2009 21:28:02 +1100
On 16/03/2009, at 7:37 PM, Jean-Daniel Dupas wrote:
That's why a good hash table uses primary numbers as table size
This only helps if the hash function distributes more or less
randomly. If your hash function turned out to hit multiples of the
hash table size, prime or not, you'd end up colliding every time.
Trivial and contrived example - hash table size = 13 (prime), hash
function of a string = first char of string % 26 (for a..z, say).
OK, so that's a seriously dysfunctional hash function, but it's not
unheard of for hash functions to have a periodicity, and if that
periodicity is non-prime in itself, then it will have prime factors
that *could* equal the table size. With integer indexes as the "hash",
this could be fairly likely.
--Graham
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden