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. Joerg
