4 ms·

Not sure why you're getting downvoted. It's plainly true that hash tables accesses are only O(1) amortized. The real worst case is ~O(n log n) (or whatever the

by 60654 8y ago

Not sure why you're getting downvoted. It's plainly true that hash tables accesses are only O(1) amortized. The real worst case is ~O(n log n) (or whatever the bucket data structure is) in the case of collisions and/or filling up. And we can always pre-allocate a huge array for the buckets, but the behavior of the hash function is always going to be a risk.

KirinDave 8y ago
I'm being downvoted because I deserve to be. I got involved in a computer science discussion on hacker news and now I don't have the self-control to extricate myself because I love this subject.
CodeMage 8y ago
I don't know about the rest, but I downvoted both of you because your vague claims just add noise to the discussion. There's absolutely no sense whatsoever in the claim that the worst case for hash table access is O(n log n), when just a linear search will be O(n).
- KirinDave 8y ago
  The task is not to find an object in a hash tables. It's to nub an array into a set. Which is why we're not handwaving away the construction cost or ignoring key comparisons or other such thinking. Saying, "A hash tables solves this" is the definition of noise, because if you have a perfect hash function for a data set to get the constants you want then you've already got the solution to the problem presented for discussion here. The hash tables itself just becomes cargo culting.
- 60654 8y ago
  Gah, I see the confusion, in one sentence I was talking about single element access, and in the next about full copy, and I was just assuming the jump was clear to the reader but clearly it wasn't. So just to be fully explicit: Single element access in a hash table is only ~O(1) when it's amortized over many accesses of a table that assumes few collisions (due to size and a good hash function). But the real worst-case performance, in case of incessent collisions, is going to be the performance of whatever data structure hides behind each bucket: O(n) if it's a naive list, O(log_x n) if it's a simple tree, etc. So copying a full list into a hash table is not O(n), it's O(n^2) if the buckets are backed by naive lists, O(n log_x n) if the buckets are backed by simple trees, or another superlinear bound for another backing data structure. How about it? And personally I would still prefer to de-dupe an array by dumping into a hashtable and back, but the OP is right, you have to be careful about implementation details of both the hashtable and the hashing function. The simple hashtable-and-back can produce much worse perf than sort-and-dedupe if stars don't align.

by 60654 8y ago

KirinDave 8y ago

I'm being downvoted because I deserve to be. I got involved in a computer science discussion on hacker news and now I don't have the self-control to extricate myself because I love this subject.

CodeMage 8y ago

I don't know about the rest, but I downvoted both of you because your vague claims just add noise to the discussion. There's absolutely no sense whatsoever in the claim that the worst case for hash table access is O(n log n), when just a linear search will be O(n).

KirinDave 8y ago
The task is not to find an object in a hash tables. It's to nub an array into a set. Which is why we're not handwaving away the construction cost or ignoring key comparisons or other such thinking. Saying, "A hash tables solves this" is the definition of noise, because if you have a perfect hash function for a data set to get the constants you want then you've already got the solution to the problem presented for discussion here. The hash tables itself just becomes cargo culting.
60654 8y ago
Gah, I see the confusion, in one sentence I was talking about single element access, and in the next about full copy, and I was just assuming the jump was clear to the reader but clearly it wasn't. So just to be fully explicit: Single element access in a hash table is only ~O(1) when it's amortized over many accesses of a table that assumes few collisions (due to size and a good hash function). But the real worst-case performance, in case of incessent collisions, is going to be the performance of whatever data structure hides behind each bucket: O(n) if it's a naive list, O(log_x n) if it's a simple tree, etc. So copying a full list into a hash table is not O(n), it's O(n^2) if the buckets are backed by naive lists, O(n log_x n) if the buckets are backed by simple trees, or another superlinear bound for another backing data structure. How about it? And personally I would still prefer to de-dupe an array by dumping into a hashtable and back, but the OP is right, you have to be careful about implementation details of both the hashtable and the hashing function. The simple hashtable-and-back can produce much worse perf than sort-and-dedupe if stars don't align.