tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: radix tree implementation for quota ?

On Tue, Nov 30, 2010 at 03:37:28PM +0000, Sad Clouds wrote:
> Well, if hash table is heavily used for looking up keys, you can reduce
> the number of collisions even further. The trick is to use different
> hash functions, which are very fast to compute:

This is just one (bad) version of implementing collision handling.
This does *not* reduce the number of collissions, it just may help to
spread them better over the table.

If you want to have a proper algorithm for collision avoidance, look at
Cuckoo Hashing. It ensures that every look up has to check at most two
different keys. That requires the availability of universal hash
functions again, so we are back at the original topic.


Home | Main Index | Thread Index | Old Index