Hash Table vs Other data structures like AVLTrees
I was looking at the complexities of Hash Table and AVLTree. Theoretically, the complexity for inserting and deleting an element on Hash Tables is O(1) and for AVLTree O(log(n)) (studying the complexities with the workflow being the number of elements on the Data Structure), seeing this results Hash Tables seem to be better than AVLTrees but if we take into account the size of the structure itself and the time needed to compute the hashing function for a given key, aren´t AVLTrees better?
data-structures hashtable avl-tree
asked Nov 23 at 0:17
Angelixus
256
add a comment |
I was looking at the complexities of Hash Table and AVLTree. Theoretically, the complexity for inserting and deleting an element on Hash Tables is O(1) and for AVLTree O(log(n)) (studying the complexities with the workflow being the number of elements on the Data Structure), seeing this results Hash Tables seem to be better than AVLTrees but if we take into account the size of the structure itself and the time needed to compute the hashing function for a given key, aren´t AVLTrees better?
data-structures hashtable avl-tree
asked Nov 23 at 0:17
Angelixus
256
1
bigocheatsheet.com
– plasmacel
Nov 23 at 0:20
I can't imagine an O(log(n)) algorithm would ever be better than an O(1) algorithm for reasonably large data sets - but why don't you try it? SUGGESTION: Create a benchmark that compares the two, and post your results.
– FoggyDay
Nov 23 at 0:21
@FoggyDay Of course O(log(n)) is worst than O(1), but add operation of a Hash Table needs the result of the hashing function for what you want to add with the given key, if the hashing function has a comlexity O(n) even though when actually adding the element you add it directly to the position that the hashing function outputed, for huge keys (a string with 200 characters for example) wouldn´t it be slower than the adding operation of AVLTrees which is always O(log(n)) regardless of what you are actually adding? (I talk about overall execution time I may have used complexity notation wrong)
– Angelixus
Nov 23 at 0:28
SUGGESTION: Create a benchmark that compares the two, and post your results
– FoggyDay
Nov 23 at 5:03
add a comment |
I was looking at the complexities of Hash Table and AVLTree. Theoretically, the complexity for inserting and deleting an element on Hash Tables is O(1) and for AVLTree O(log(n)) (studying the complexities with the workflow being the number of elements on the Data Structure), seeing this results Hash Tables seem to be better than AVLTrees but if we take into account the size of the structure itself and the time needed to compute the hashing function for a given key, aren´t AVLTrees better?
data-structures hashtable avl-tree
asked Nov 23 at 0:17
Angelixus
256
I was looking at the complexities of Hash Table and AVLTree. Theoretically, the complexity for inserting and deleting an element on Hash Tables is O(1) and for AVLTree O(log(n)) (studying the complexities with the workflow being the number of elements on the Data Structure), seeing this results Hash Tables seem to be better than AVLTrees but if we take into account the size of the structure itself and the time needed to compute the hashing function for a given key, aren´t AVLTrees better?
data-structures hashtable avl-tree
data-structures hashtable avl-tree
asked Nov 23 at 0:17
Angelixus
256
asked Nov 23 at 0:17
Angelixus
256
asked Nov 23 at 0:17
Angelixus
256
asked Nov 23 at 0:17
Angelixus
256
asked Nov 23 at 0:17
Angelixus
256
256
1
bigocheatsheet.com
– plasmacel
Nov 23 at 0:20
I can't imagine an O(log(n)) algorithm would ever be better than an O(1) algorithm for reasonably large data sets - but why don't you try it? SUGGESTION: Create a benchmark that compares the two, and post your results.
– FoggyDay
Nov 23 at 0:21
@FoggyDay Of course O(log(n)) is worst than O(1), but add operation of a Hash Table needs the result of the hashing function for what you want to add with the given key, if the hashing function has a comlexity O(n) even though when actually adding the element you add it directly to the position that the hashing function outputed, for huge keys (a string with 200 characters for example) wouldn´t it be slower than the adding operation of AVLTrees which is always O(log(n)) regardless of what you are actually adding? (I talk about overall execution time I may have used complexity notation wrong)
– Angelixus
Nov 23 at 0:28
SUGGESTION: Create a benchmark that compares the two, and post your results
– FoggyDay
Nov 23 at 5:03
add a comment |
1
bigocheatsheet.com
– plasmacel
Nov 23 at 0:20
I can't imagine an O(log(n)) algorithm would ever be better than an O(1) algorithm for reasonably large data sets - but why don't you try it? SUGGESTION: Create a benchmark that compares the two, and post your results.
– FoggyDay
Nov 23 at 0:21
@FoggyDay Of course O(log(n)) is worst than O(1), but add operation of a Hash Table needs the result of the hashing function for what you want to add with the given key, if the hashing function has a comlexity O(n) even though when actually adding the element you add it directly to the position that the hashing function outputed, for huge keys (a string with 200 characters for example) wouldn´t it be slower than the adding operation of AVLTrees which is always O(log(n)) regardless of what you are actually adding? (I talk about overall execution time I may have used complexity notation wrong)
– Angelixus
Nov 23 at 0:28
SUGGESTION: Create a benchmark that compares the two, and post your results
– FoggyDay
Nov 23 at 5:03
1
1
bigocheatsheet.com
– plasmacel
Nov 23 at 0:20
bigocheatsheet.com
– plasmacel
Nov 23 at 0:20
I can't imagine an O(log(n)) algorithm would ever be better than an O(1) algorithm for reasonably large data sets - but why don't you try it? SUGGESTION: Create a benchmark that compares the two, and post your results.
– FoggyDay
Nov 23 at 0:21
I can't imagine an O(log(n)) algorithm would ever be better than an O(1) algorithm for reasonably large data sets - but why don't you try it? SUGGESTION: Create a benchmark that compares the two, and post your results.
– FoggyDay
Nov 23 at 0:21
@FoggyDay Of course O(log(n)) is worst than O(1), but add operation of a Hash Table needs the result of the hashing function for what you want to add with the given key, if the hashing function has a comlexity O(n) even though when actually adding the element you add it directly to the position that the hashing function outputed, for huge keys (a string with 200 characters for example) wouldn´t it be slower than the adding operation of AVLTrees which is always O(log(n)) regardless of what you are actually adding? (I talk about overall execution time I may have used complexity notation wrong)
– Angelixus
Nov 23 at 0:28
@FoggyDay Of course O(log(n)) is worst than O(1), but add operation of a Hash Table needs the result of the hashing function for what you want to add with the given key, if the hashing function has a comlexity O(n) even though when actually adding the element you add it directly to the position that the hashing function outputed, for huge keys (a string with 200 characters for example) wouldn´t it be slower than the adding operation of AVLTrees which is always O(log(n)) regardless of what you are actually adding? (I talk about overall execution time I may have used complexity notation wrong)
– Angelixus
Nov 23 at 0:28
SUGGESTION: Create a benchmark that compares the two, and post your results
– FoggyDay
Nov 23 at 5:03
SUGGESTION: Create a benchmark that compares the two, and post your results
– FoggyDay
Nov 23 at 5:03
add a comment |
1 Answer
1
active
oldest
votes
Hash tables and AVL trees serve fundamentally different functions. In short, a hash table is for lookup, whereas a tree structure is for search and traversal.
A hash table gives you very fast retrieval of values that are associated with individual keys. If you've inserted a value with key "xqj57", then you can quickly retrieve it. And if "xqj57" hasn't been inserted, the lookup will say that no such record exists. Both insertion and lookup are O(1) operations.
AVL trees and similar structures are good for storing things in sorted order. That lets you traverse the structure in sorted order, and also lets you do things like easily retrieve, in order, all records whose key starts with "A", or get the first record whose key is greater than or equal to "foo", etc. Insertion and search are O(log n) operations. Traversal, of course, is O(n).
If you want to traverse a hash table in sorted order, you would have to sort it first.
A hash table does have a little extra memory overhead when compared to a tree structure, but not that much.
Unless keys are exceptionally long, or your hashing function is really complicated, the cost of computing a hash value for a key is cheap compared to the cost of the log(n) key comparisons you'll have to do to find something in a tree structure.
If you just want fast insertion and lookup, then it's hard to beat a hash table. If you want to work with a sorted list, then a hash table is definitely not the way to go. An AVL tree, red-black tree, skip list, or other such sorted structure is going to perform better.
answered Nov 24 at 5:48
Jim Mischel
106k12128247
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f53439326%2fhash-table-vs-other-data-structures-like-avltrees%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Hash tables and AVL trees serve fundamentally different functions. In short, a hash table is for lookup, whereas a tree structure is for search and traversal.
A hash table gives you very fast retrieval of values that are associated with individual keys. If you've inserted a value with key "xqj57", then you can quickly retrieve it. And if "xqj57" hasn't been inserted, the lookup will say that no such record exists. Both insertion and lookup are O(1) operations.
AVL trees and similar structures are good for storing things in sorted order. That lets you traverse the structure in sorted order, and also lets you do things like easily retrieve, in order, all records whose key starts with "A", or get the first record whose key is greater than or equal to "foo", etc. Insertion and search are O(log n) operations. Traversal, of course, is O(n).
If you want to traverse a hash table in sorted order, you would have to sort it first.
A hash table does have a little extra memory overhead when compared to a tree structure, but not that much.
Unless keys are exceptionally long, or your hashing function is really complicated, the cost of computing a hash value for a key is cheap compared to the cost of the log(n) key comparisons you'll have to do to find something in a tree structure.
If you just want fast insertion and lookup, then it's hard to beat a hash table. If you want to work with a sorted list, then a hash table is definitely not the way to go. An AVL tree, red-black tree, skip list, or other such sorted structure is going to perform better.
answered Nov 24 at 5:48
Jim Mischel
106k12128247
add a comment |
Hash tables and AVL trees serve fundamentally different functions. In short, a hash table is for lookup, whereas a tree structure is for search and traversal.
A hash table gives you very fast retrieval of values that are associated with individual keys. If you've inserted a value with key "xqj57", then you can quickly retrieve it. And if "xqj57" hasn't been inserted, the lookup will say that no such record exists. Both insertion and lookup are O(1) operations.
AVL trees and similar structures are good for storing things in sorted order. That lets you traverse the structure in sorted order, and also lets you do things like easily retrieve, in order, all records whose key starts with "A", or get the first record whose key is greater than or equal to "foo", etc. Insertion and search are O(log n) operations. Traversal, of course, is O(n).
If you want to traverse a hash table in sorted order, you would have to sort it first.
A hash table does have a little extra memory overhead when compared to a tree structure, but not that much.
Unless keys are exceptionally long, or your hashing function is really complicated, the cost of computing a hash value for a key is cheap compared to the cost of the log(n) key comparisons you'll have to do to find something in a tree structure.
If you just want fast insertion and lookup, then it's hard to beat a hash table. If you want to work with a sorted list, then a hash table is definitely not the way to go. An AVL tree, red-black tree, skip list, or other such sorted structure is going to perform better.
answered Nov 24 at 5:48
Jim Mischel
106k12128247
add a comment |
Hash tables and AVL trees serve fundamentally different functions. In short, a hash table is for lookup, whereas a tree structure is for search and traversal.
A hash table gives you very fast retrieval of values that are associated with individual keys. If you've inserted a value with key "xqj57", then you can quickly retrieve it. And if "xqj57" hasn't been inserted, the lookup will say that no such record exists. Both insertion and lookup are O(1) operations.
AVL trees and similar structures are good for storing things in sorted order. That lets you traverse the structure in sorted order, and also lets you do things like easily retrieve, in order, all records whose key starts with "A", or get the first record whose key is greater than or equal to "foo", etc. Insertion and search are O(log n) operations. Traversal, of course, is O(n).
If you want to traverse a hash table in sorted order, you would have to sort it first.
A hash table does have a little extra memory overhead when compared to a tree structure, but not that much.
Unless keys are exceptionally long, or your hashing function is really complicated, the cost of computing a hash value for a key is cheap compared to the cost of the log(n) key comparisons you'll have to do to find something in a tree structure.
If you just want fast insertion and lookup, then it's hard to beat a hash table. If you want to work with a sorted list, then a hash table is definitely not the way to go. An AVL tree, red-black tree, skip list, or other such sorted structure is going to perform better.
answered Nov 24 at 5:48
Jim Mischel
106k12128247
Hash tables and AVL trees serve fundamentally different functions. In short, a hash table is for lookup, whereas a tree structure is for search and traversal.
A hash table gives you very fast retrieval of values that are associated with individual keys. If you've inserted a value with key "xqj57", then you can quickly retrieve it. And if "xqj57" hasn't been inserted, the lookup will say that no such record exists. Both insertion and lookup are O(1) operations.
AVL trees and similar structures are good for storing things in sorted order. That lets you traverse the structure in sorted order, and also lets you do things like easily retrieve, in order, all records whose key starts with "A", or get the first record whose key is greater than or equal to "foo", etc. Insertion and search are O(log n) operations. Traversal, of course, is O(n).
If you want to traverse a hash table in sorted order, you would have to sort it first.
A hash table does have a little extra memory overhead when compared to a tree structure, but not that much.
Unless keys are exceptionally long, or your hashing function is really complicated, the cost of computing a hash value for a key is cheap compared to the cost of the log(n) key comparisons you'll have to do to find something in a tree structure.
If you just want fast insertion and lookup, then it's hard to beat a hash table. If you want to work with a sorted list, then a hash table is definitely not the way to go. An AVL tree, red-black tree, skip list, or other such sorted structure is going to perform better.
answered Nov 24 at 5:48
Jim Mischel
106k12128247
answered Nov 24 at 5:48
Jim Mischel
106k12128247
answered Nov 24 at 5:48
Jim Mischel
106k12128247
answered Nov 24 at 5:48
Jim Mischel
106k12128247
106k12128247
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%2f53439326%2fhash-table-vs-other-data-structures-like-avltrees%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
1
bigocheatsheet.com
– plasmacel
Nov 23 at 0:20
I can't imagine an O(log(n)) algorithm would ever be better than an O(1) algorithm for reasonably large data sets - but why don't you try it? SUGGESTION: Create a benchmark that compares the two, and post your results.
– FoggyDay
Nov 23 at 0:21
@FoggyDay Of course O(log(n)) is worst than O(1), but add operation of a Hash Table needs the result of the hashing function for what you want to add with the given key, if the hashing function has a comlexity O(n) even though when actually adding the element you add it directly to the position that the hashing function outputed, for huge keys (a string with 200 characters for example) wouldn´t it be slower than the adding operation of AVLTrees which is always O(log(n)) regardless of what you are actually adding? (I talk about overall execution time I may have used complexity notation wrong)
– Angelixus
Nov 23 at 0:28
SUGGESTION: Create a benchmark that compares the two, and post your results
– FoggyDay
Nov 23 at 5:03