Why we don't use Cuckoo Hashing
up vote
0
down vote
favorite
My question is from what i understand Cuckoo Hashing takes usually 0(1) time for insert delete and find. The worst case scenario is O(1) (amortized). My question is why isn't this algorithm used more often. Why would we use a different algorithm to look things up inserting or deleting rather then something like Cuckoo Hashing?
algorithm hash
asked Nov 8 at 0:23
shiv shah
133
add a comment |
up vote
0
down vote
favorite
My question is from what i understand Cuckoo Hashing takes usually 0(1) time for insert delete and find. The worst case scenario is O(1) (amortized). My question is why isn't this algorithm used more often. Why would we use a different algorithm to look things up inserting or deleting rather then something like Cuckoo Hashing?
algorithm hash
asked Nov 8 at 0:23
shiv shah
133
Possible duplicate of Advantages of Binary Search Trees over Hash Tables
– James K Polk
Nov 8 at 0:29
Are you asking why tree maps are more common than hash maps? If so, I'd say that's a false premise - hash maps are easily more commonly used in most languages / library ecosystems. Or are you asking why other resolution strategies are more common for hash maps than Cuckoo Hashing? If so, the "Practice" section of the Wikipedia article on Cuckoo Hashing might give one reason.
– sepp2k
Nov 8 at 0:32
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
My question is from what i understand Cuckoo Hashing takes usually 0(1) time for insert delete and find. The worst case scenario is O(1) (amortized). My question is why isn't this algorithm used more often. Why would we use a different algorithm to look things up inserting or deleting rather then something like Cuckoo Hashing?
algorithm hash
asked Nov 8 at 0:23
shiv shah
133
My question is from what i understand Cuckoo Hashing takes usually 0(1) time for insert delete and find. The worst case scenario is O(1) (amortized). My question is why isn't this algorithm used more often. Why would we use a different algorithm to look things up inserting or deleting rather then something like Cuckoo Hashing?
algorithm hash
algorithm hash
asked Nov 8 at 0:23
shiv shah
133
asked Nov 8 at 0:23
shiv shah
133
edited Nov 8 at 0:33
asked Nov 8 at 0:23
shiv shah
133
asked Nov 8 at 0:23
shiv shah
133
asked Nov 8 at 0:23
shiv shah
133
133
Possible duplicate of Advantages of Binary Search Trees over Hash Tables
– James K Polk
Nov 8 at 0:29
Are you asking why tree maps are more common than hash maps? If so, I'd say that's a false premise - hash maps are easily more commonly used in most languages / library ecosystems. Or are you asking why other resolution strategies are more common for hash maps than Cuckoo Hashing? If so, the "Practice" section of the Wikipedia article on Cuckoo Hashing might give one reason.
– sepp2k
Nov 8 at 0:32
add a comment |
Possible duplicate of Advantages of Binary Search Trees over Hash Tables
– James K Polk
Nov 8 at 0:29
Are you asking why tree maps are more common than hash maps? If so, I'd say that's a false premise - hash maps are easily more commonly used in most languages / library ecosystems. Or are you asking why other resolution strategies are more common for hash maps than Cuckoo Hashing? If so, the "Practice" section of the Wikipedia article on Cuckoo Hashing might give one reason.
– sepp2k
Nov 8 at 0:32
Possible duplicate of Advantages of Binary Search Trees over Hash Tables
– James K Polk
Nov 8 at 0:29
Possible duplicate of Advantages of Binary Search Trees over Hash Tables
– James K Polk
Nov 8 at 0:29
Are you asking why tree maps are more common than hash maps? If so, I'd say that's a false premise - hash maps are easily more commonly used in most languages / library ecosystems. Or are you asking why other resolution strategies are more common for hash maps than Cuckoo Hashing? If so, the "Practice" section of the Wikipedia article on Cuckoo Hashing might give one reason.
– sepp2k
Nov 8 at 0:32
Are you asking why tree maps are more common than hash maps? If so, I'd say that's a false premise - hash maps are easily more commonly used in most languages / library ecosystems. Or are you asking why other resolution strategies are more common for hash maps than Cuckoo Hashing? If so, the "Practice" section of the Wikipedia article on Cuckoo Hashing might give one reason.
– sepp2k
Nov 8 at 0:32
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
Cuckoo hashing requires an unbounded number of different independent hash functions, which is not compatible with the way we usually implement a generic hash table, since that only requires one hash function to be specified.
If you are writing a hash table implementation for a specific data type, then the hash function(s) can be built into the table implementation and cuckoo hashing may be reasonable.
Even in that case, however, you probably won't be able to prove that you can support any set of elements, since your hash functions won't really be random and independent, so a cuckoo hashing implementation has O(1) expected time for insert, but in a real implementation there may be a case or two in which it will go into an infinite loop or fail.
You could engineer a fallback for cases like that, but then is cuckoo hashing worth the extra complexity?
Cuckoo hashing may be a good alternative to perfect hashing, when the hash table is computed in advance... but if you're doing it in advance then insertions don't usually have to be that fast so you can use perfect hashing instead.
answered Nov 8 at 1:48
Matt Timmermans
18k11532
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Cuckoo hashing requires an unbounded number of different independent hash functions, which is not compatible with the way we usually implement a generic hash table, since that only requires one hash function to be specified.
If you are writing a hash table implementation for a specific data type, then the hash function(s) can be built into the table implementation and cuckoo hashing may be reasonable.
Even in that case, however, you probably won't be able to prove that you can support any set of elements, since your hash functions won't really be random and independent, so a cuckoo hashing implementation has O(1) expected time for insert, but in a real implementation there may be a case or two in which it will go into an infinite loop or fail.
You could engineer a fallback for cases like that, but then is cuckoo hashing worth the extra complexity?
Cuckoo hashing may be a good alternative to perfect hashing, when the hash table is computed in advance... but if you're doing it in advance then insertions don't usually have to be that fast so you can use perfect hashing instead.
answered Nov 8 at 1:48
Matt Timmermans
18k11532
add a comment |
up vote
1
down vote
Cuckoo hashing requires an unbounded number of different independent hash functions, which is not compatible with the way we usually implement a generic hash table, since that only requires one hash function to be specified.
If you are writing a hash table implementation for a specific data type, then the hash function(s) can be built into the table implementation and cuckoo hashing may be reasonable.
Even in that case, however, you probably won't be able to prove that you can support any set of elements, since your hash functions won't really be random and independent, so a cuckoo hashing implementation has O(1) expected time for insert, but in a real implementation there may be a case or two in which it will go into an infinite loop or fail.
You could engineer a fallback for cases like that, but then is cuckoo hashing worth the extra complexity?
Cuckoo hashing may be a good alternative to perfect hashing, when the hash table is computed in advance... but if you're doing it in advance then insertions don't usually have to be that fast so you can use perfect hashing instead.
answered Nov 8 at 1:48
Matt Timmermans
18k11532
add a comment |
up vote
1
down vote
up vote
1
down vote
Cuckoo hashing requires an unbounded number of different independent hash functions, which is not compatible with the way we usually implement a generic hash table, since that only requires one hash function to be specified.
If you are writing a hash table implementation for a specific data type, then the hash function(s) can be built into the table implementation and cuckoo hashing may be reasonable.
Even in that case, however, you probably won't be able to prove that you can support any set of elements, since your hash functions won't really be random and independent, so a cuckoo hashing implementation has O(1) expected time for insert, but in a real implementation there may be a case or two in which it will go into an infinite loop or fail.
You could engineer a fallback for cases like that, but then is cuckoo hashing worth the extra complexity?
Cuckoo hashing may be a good alternative to perfect hashing, when the hash table is computed in advance... but if you're doing it in advance then insertions don't usually have to be that fast so you can use perfect hashing instead.
answered Nov 8 at 1:48
Matt Timmermans
18k11532
Cuckoo hashing requires an unbounded number of different independent hash functions, which is not compatible with the way we usually implement a generic hash table, since that only requires one hash function to be specified.
If you are writing a hash table implementation for a specific data type, then the hash function(s) can be built into the table implementation and cuckoo hashing may be reasonable.
Even in that case, however, you probably won't be able to prove that you can support any set of elements, since your hash functions won't really be random and independent, so a cuckoo hashing implementation has O(1) expected time for insert, but in a real implementation there may be a case or two in which it will go into an infinite loop or fail.
You could engineer a fallback for cases like that, but then is cuckoo hashing worth the extra complexity?
Cuckoo hashing may be a good alternative to perfect hashing, when the hash table is computed in advance... but if you're doing it in advance then insertions don't usually have to be that fast so you can use perfect hashing instead.
answered Nov 8 at 1:48
Matt Timmermans
18k11532
answered Nov 8 at 1:48
Matt Timmermans
18k11532
answered Nov 8 at 1:48
Matt Timmermans
18k11532
answered Nov 8 at 1:48
Matt Timmermans
18k11532
18k11532
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53199889%2fwhy-we-dont-use-cuckoo-hashing%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Possible duplicate of Advantages of Binary Search Trees over Hash Tables
– James K Polk
Nov 8 at 0:29
Are you asking why tree maps are more common than hash maps? If so, I'd say that's a false premise - hash maps are easily more commonly used in most languages / library ecosystems. Or are you asking why other resolution strategies are more common for hash maps than Cuckoo Hashing? If so, the "Practice" section of the Wikipedia article on Cuckoo Hashing might give one reason.
– sepp2k
Nov 8 at 0:32