Skip to main content

Return to Answer

Keep un-related thoughts to a minimum. :-) Also the blockquote implies you are quoting someone.
Source Link
ΩmegaMan
ΩmegaMan
  • 32.2k
  • 13
  • 110
  • 138

I love Stackoverflow! Reading this question made me look into hash functions a bit more and I foundHere is the Cuckoo Hash.

From the article:

Lookup requires inspection of just two locations in the hash table, which takes constant time in the worst case (see Big O notation). This is in contrast to many other hash table algorithms, which may not have a constant worst-case bound on the time to do a lookup.

I think that fits into your criteria of collisions and performance. It appears that the tradeoff is that this type of hash table can only get 49% full.

I love Stackoverflow! Reading this question made me look into hash functions a bit more and I found the Cuckoo Hash.

From the article:

Lookup requires inspection of just two locations in the hash table, which takes constant time in the worst case (see Big O notation). This is in contrast to many other hash table algorithms, which may not have a constant worst-case bound on the time to do a lookup.

I think that fits into your criteria of collisions and performance. It appears that the tradeoff is that this type of hash table can only get 49% full.

Here is the Cuckoo Hash.

Lookup requires inspection of just two locations in the hash table, which takes constant time in the worst case (see Big O notation). This is in contrast to many other hash table algorithms, which may not have a constant worst-case bound on the time to do a lookup.

I think that fits into your criteria of collisions and performance. It appears that the tradeoff is that this type of hash table can only get 49% full.

Source Link
Jason Z
Jason Z
  • 13.5k
  • 15
  • 52
  • 62

I love Stackoverflow! Reading this question made me look into hash functions a bit more and I found the Cuckoo Hash.

From the article:

Lookup requires inspection of just two locations in the hash table, which takes constant time in the worst case (see Big O notation). This is in contrast to many other hash table algorithms, which may not have a constant worst-case bound on the time to do a lookup.

I think that fits into your criteria of collisions and performance. It appears that the tradeoff is that this type of hash table can only get 49% full.