4 ms·

Very few hash tables actually run in O(1) time and they tend to be bounded. You cannot have any collisions at all, and you need to use a lookup with fast, const

Very few hash tables actually run in O(1) time and they tend to be bounded. You cannot have any collisions at all, and you need to use a lookup with fast, constant cost. Many hash tables in use today are actually either O(n^2) (for the homework kind), or O(n log n) for some large log factor like 32 (in the spirit of Bagwell's work).

avian 8y ago
> Many hash tables in use today are actually either O(n^2) or O(n log n) Do you have any citation for such an extraordinary claim? Or are you not talking about lookup complexity where n is the size of the table? I would think that a hash table with an O(n^2) or O(n log n) lookup is not a hash table at all. I mean, a simple linear search is O(n).
- KirinDave 8y ago
  O(n) == O(n^2) when n = 1.
  - kevinwang 8y ago
    ...
    - KirinDave 8y ago
      It is a jokey way to restate the absurd essence of the parent's argument.
  - 15rthughes 8y ago
    The whole point of this notation is to describe limiting behavior, the true value of N isn’t important in the slightest.
    - KirinDave 8y ago
      That is actually my point. Remember the goal is to nub an array into a set. Perfect hash tables where there are no collisions are O(1) but they're not suitable for casual use, you need to guarantee your data set never collides hash buckets. That is why most implementations of "maps" in programming languages map to very wide trees after a certain size. A common example is HAMTs (Bagwell is famois for these). They're flexible and perform well on modern hardware for arbitrary key lookiup. If your constant time hash tables is taken to the worst case (as we do in O analysis) then that operation would collide with the same bucket and require a potentially full linear search of the data every time to see if it places into your oversubscribed bucket. That's O(n^2). You could make it better by sorting on insert. That's O(n log n) because it's comparison based. I've provided a much better solution and links to code that does it. Maps and hash tables don't solve this problem any better than just sorting the array. It's worth noting that if we're ignoring preprocessing and the domain is well-constrained, we could probably make O(1) to do a bunch of these ops in bulk if we really wanna go off the deep end. But that's cheating because we'd be ignoring construction costs, as you are here.
aflag 8y ago
What are you calling n?
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.
KirinDave 8y ago
It's worth noting for clarification I'm talking about inserting to construct a set and reading out the keyspace. Not specifically reads, which is I think what folks below are objecting to. The read side barely matters for the use case we're discussing.

avian 8y ago

> Many hash tables in use today are actually either O(n^2) or O(n log n) Do you have any citation for such an extraordinary claim? Or are you not talking about lookup complexity where n is the size of the table? I would think that a hash table with an O(n^2) or O(n log n) lookup is not a hash table at all. I mean, a simple linear search is O(n).

KirinDave 8y ago
O(n) == O(n^2) when n = 1.
- kevinwang 8y ago
  ...
  - KirinDave 8y ago
    It is a jokey way to restate the absurd essence of the parent's argument.
- 15rthughes 8y ago
  The whole point of this notation is to describe limiting behavior, the true value of N isn’t important in the slightest.
  - KirinDave 8y ago
    That is actually my point. Remember the goal is to nub an array into a set. Perfect hash tables where there are no collisions are O(1) but they're not suitable for casual use, you need to guarantee your data set never collides hash buckets. That is why most implementations of "maps" in programming languages map to very wide trees after a certain size. A common example is HAMTs (Bagwell is famois for these). They're flexible and perform well on modern hardware for arbitrary key lookiup. If your constant time hash tables is taken to the worst case (as we do in O analysis) then that operation would collide with the same bucket and require a potentially full linear search of the data every time to see if it places into your oversubscribed bucket. That's O(n^2). You could make it better by sorting on insert. That's O(n log n) because it's comparison based. I've provided a much better solution and links to code that does it. Maps and hash tables don't solve this problem any better than just sorting the array. It's worth noting that if we're ignoring preprocessing and the domain is well-constrained, we could probably make O(1) to do a bunch of these ops in bulk if we really wanna go off the deep end. But that's cheating because we'd be ignoring construction costs, as you are here.

aflag 8y ago

What are you calling n?

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.

KirinDave 8y ago

It's worth noting for clarification I'm talking about inserting to construct a set and reading out the keyspace. Not specifically reads, which is I think what folks below are objecting to. The read side barely matters for the use case we're discussing.