3 ms·
Hm? Hashing is O(N) unless it's oblivious to some bits. Though the prefix tree part is optional, yes. :-) Better luck next time. (For some reason programmers r
by abecedarius 14y ago
Hm? Hashing is O(N) unless it's oblivious to some bits. Though the prefix tree part is optional, yes. :-) Better luck next time.
(For some reason programmers really love tries / prefix trees when answering on stackoverflow and such. I'd like to understand why -- tries are neat, but you don't see them nearly as much in actual use.)
- JoshTriplett 14y ago> Hashing is O(N) unless it's oblivious to some bits. O(N) only makes sense when you agree on what N means. When using big-O notation, always make sure you agree on the base N values you want to work with. In this case, it sounds like you interpreted N as the number of bits to hash, in which case yes, any sensible hash algorithm has to look at all the bits so it'll use an O(N) algorithm. However, the post you replied to talked about hash tables, a structure used to implement (among other things) maps from keys to values. For such a structure, N refers to the number of items stored in the table; hash tables have the rather unique property of supporting O(1) insertion, removal, and lookups (modulo amortization arguments about the size of the table).
- pjscott 14y agoWell put. I'd like to add that, while hashing time is proportional to the key length, in practice it's very, very fast for all non-enormous keys, at least on modern processors. Compare with the cost of pointer-chasing in a tree, and hashing time starts to look pretty constant-ish. (Yes I'm handwaving around the details. So is everyone who talks about big-O notation in connection with real software.)
- abecedarius 14y agoThe post I replied to said N is the length of the key.