7 ms·

He says binary trees are better default search table than hash table... binary tree search is O(lg(n)) while hash table is O(1)... so hash table is better for s

He says binary trees are better default search table than hash table... binary tree search is O(lg(n)) while hash table is O(1)... so hash table is better for search, binary trees win in other ways (like ordered traversal if you need that), but no way you could say one is always better than the other. Also confused how he proposes to build his Radix Trie in less than linear time... just seems like he ditches his original premise and launches into routing. There are selection algorithms that will find things in an unsorted array in O(lg(n))... but pretty sure building a tree of any sort is not part of it. Radix Tries are sweet fun... so is just good old Radix Sort, but he starts with something that doesn't really make sense for the topic (the unsorted array he wants to pull three out of), then makes some weird claims, then jumps into routing with Radix Tries... not sure what is insightful here.

aston 19y ago
There aren't any algorithms to find things in an unsorted array in less than worst case linear time. I think you're confusing search (for some value) with select (a value with a given index in the sorted array).
- Xichekolas 19y ago
  Yeah, yeah I was... was just thinking about that over breakfast.
- eru 19y ago
  If you want to do several searches on the same data - that is initially unsorted - you can get better than O(n) per query. But like you said - not for the first one.
tptacek 19y ago
Hash tables are NOT O(1). You just failed the job interview. You're like the 4th person I've seen that read (some) of this article and pulled this tree vs. hash thing out of it. It's a throwaway point. Binary trees provide comparable performance to hash tables, but also provide efficient access to ranges of keys. Binary trees support more operations efficiently than hash tables. The article isn't about some war I've declared on hash tables.
- gojomo 19y ago
  "Hash tables are NOT O(1)." For average lookup time, which is a reasonable context to assume in the preceding comment, yes they are.
- marketer 19y ago
  What do you mean hash tables are not O(1)? With a good hash function (collision resistant), the amortized cost of lookup is O(1), even if you need to resize the table.
- Xichekolas 19y ago
  "tree vs. hash thing ... It's a throwaway point" If you had read more than (some) of my comment you might have gathered that was my entire point. The first page of your post was a throwaway point... nothing to do with your actual point, which seemed to be Radix Tries. It would've been nice to dispense with the distraction was all I was saying. I know that given a lot of collisions that hash tables degenerate into linear insertion and lookup... and I did point out that binary trees are better for several things, but I still maintain that you can't just outright claim one is better than the other for every situation. Oh, and as for failing the job interview... not really sure why that was necessary. You don't make a stronger point by being a dick about it.
  - tptacek 19y ago
    The hash table O(1)/O(n) question is a classic job interview gotcha. I didn't mean to be a dick.
    - Xichekolas 19y ago
      ... and I shoulda been nicer in my original comment. Applying radix tries to routing was pretty interesting. Sorry to pick nits.
- bayareaguy 19y ago
  Hash tables are NOT O(1). You just failed the job interview. tptacek, what do you think they are?
Tichy 19y ago
For hash tables you need to compute the hash function and execute an equals operation. Computing the hash function might take longer than traversing a tree. For example, if you key is "sdolkfhasodfgkokjhdfgfnaryksfdksfdgkjgf" the hash function will probably take every single letter into account (>20 operations, didn't count), whereas a binary tree might only need to look at the first letter at most nodes. So at least for relatively few entries, trees might perform better than hashtables, O(1) nonwithstanding.

aston 19y ago

There aren't any algorithms to find things in an unsorted array in less than worst case linear time. I think you're confusing search (for some value) with select (a value with a given index in the sorted array).

Xichekolas 19y ago
Yeah, yeah I was... was just thinking about that over breakfast.
eru 19y ago
If you want to do several searches on the same data - that is initially unsorted - you can get better than O(n) per query. But like you said - not for the first one.

tptacek 19y ago

Hash tables are NOT O(1). You just failed the job interview. You're like the 4th person I've seen that read (some) of this article and pulled this tree vs. hash thing out of it. It's a throwaway point. Binary trees provide comparable performance to hash tables, but also provide efficient access to ranges of keys. Binary trees support more operations efficiently than hash tables. The article isn't about some war I've declared on hash tables.

gojomo 19y ago
"Hash tables are NOT O(1)." For average lookup time, which is a reasonable context to assume in the preceding comment, yes they are.
marketer 19y ago
What do you mean hash tables are not O(1)? With a good hash function (collision resistant), the amortized cost of lookup is O(1), even if you need to resize the table.
Xichekolas 19y ago
"tree vs. hash thing ... It's a throwaway point" If you had read more than (some) of my comment you might have gathered that was my entire point. The first page of your post was a throwaway point... nothing to do with your actual point, which seemed to be Radix Tries. It would've been nice to dispense with the distraction was all I was saying. I know that given a lot of collisions that hash tables degenerate into linear insertion and lookup... and I did point out that binary trees are better for several things, but I still maintain that you can't just outright claim one is better than the other for every situation. Oh, and as for failing the job interview... not really sure why that was necessary. You don't make a stronger point by being a dick about it.
- tptacek 19y ago
  The hash table O(1)/O(n) question is a classic job interview gotcha. I didn't mean to be a dick.
  - Xichekolas 19y ago
    ... and I shoulda been nicer in my original comment. Applying radix tries to routing was pretty interesting. Sorry to pick nits.
bayareaguy 19y ago
Hash tables are NOT O(1). You just failed the job interview. tptacek, what do you think they are?

Tichy 19y ago

For hash tables you need to compute the hash function and execute an equals operation. Computing the hash function might take longer than traversing a tree. For example, if you key is "sdolkfhasodfgkokjhdfgfnaryksfdksfdgkjgf" the hash function will probably take every single letter into account (>20 operations, didn't count), whereas a binary tree might only need to look at the first letter at most nodes. So at least for relatively few entries, trees might perform better than hashtables, O(1) nonwithstanding.