steve+comp.lang.python at pearwood.info
Mon Mar 10 04:24:08 CET 2014
On Sun, 09 Mar 2014 23:32:54 +0200, Marko Rauhamaa wrote:
> Dan Stromberg <drsalists at gmail.com>:
>> This is not just a detail: O(1) tends to be beat O(logn) pretty easily
>> for large n.
> There is no O(1) hash table.
Of course there are.
While it is true that hash tables *in general* are not *always* O(1), the
claim that hash tables are O(1) is *less wrong* than your claim that
there is "no O(1) hash table".
Proof: I create a hash table that accepts unsigned bytes as keys, where
the hash is the value of the byte. So byte 0x42 hashes to 0x42, or
decimal 66. I give the hash table 256 slots, numbered from 0 to 255.
Every hash takes constant time, there are no collisions at all, lookups,
insertions and deletions all take constant time regardless of how full
the table is. The best, worst and average cases are not just O(1) but
Since I have proven that there is *at least one* hash table that is O(1)
for best, worst and average case, your claim there are no such hash
tables is completely wrong, and certainly more wrong than the claim that
Python dicts are O(1) (which is only a little bit wrong, but typically
See also "The Relativity Of Wrong":
More information about the Python-list