4 ms·
I'm not following your logic here: "The implications are interesting, in that if the hash computation did grow as O(log2(N)), then it would (theoretically) out
by bogomipz 10y ago
I'm not following your logic here:
"The implications are interesting, in that if the hash computation did grow as O(log2(N)), then it would (theoretically) outperform the current typical O(1) hash table implementation, and they would meet only when the table is full."
How would O(log n) ever out perform constant time, O(1)?
Could you elaborate?
- dahart 10y agoThis is and always has been an important part of understanding what big-O notation actually means. O(1) means constant time, it does not tell you what the constant is. The constant can be large. In this case, if your hash always takes 64 bit values and always produces 64 bit values, it is O(1). If your hash were O(log2(N)), then your hash function with an empty table would do 1 bit worth of work, and would do only one operation. But when the table grew to contain 1,000 elements, it would do 10 bits worth of work. The O(log2(N)) algorithm with N < 2^64 is always faster (in theory) than the O(1) algorithm that does a constant 64 bits of work. The O(1) algorithm pays off in spades for N >> 2^64, it will become much faster than the logarithmic one, but for small N, log(N) is smaller than 64.
- bogomipz 10y agoRight, a constant i.e unchanging amount of work. I usually think of hashtables though as being O(1) in referring to the look up(amortized) and not the hash code itself.
- dahart 10y agoYep, and a hash table's get is O(1) amortized even when you include the hash function itself, simply because the hash function doesn't change as the hash table grows. @rand_r is right that the hash function is doing C * log2(MAX_N) operations, but that doesn't actually affect the big-O metric, it only affects the run time. :P
- bogomipz 10y agoIndeed, thanks for the clarification.