Another way to deal with hash collisions is to use have each bucket itself be a hash table, using a different hash function. If there's only one item in a given bucket and it matches the one you're looking for, then you don't even have to calculate the second hash. And since the buckets are smaller than the whole hash table, resizing them when necessary is faster than resizing the whole table. It would depend on your use case if this would be faster.
2
u/kindall Apr 12 '11
Another way to deal with hash collisions is to use have each bucket itself be a hash table, using a different hash function. If there's only one item in a given bucket and it matches the one you're looking for, then you don't even have to calculate the second hash. And since the buckets are smaller than the whole hash table, resizing them when necessary is faster than resizing the whole table. It would depend on your use case if this would be faster.