On Sun, 09 Mar 2014 23:32:54 +0200, Marko Rauhamaa wrote: > Dan Stromberg <drsali...@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 also Ω(1). 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 right). See also "The Relativity Of Wrong": http://chem.tufts.edu/answersinscience/relativityofwrong.htm -- Steven D'Aprano http://import-that.dreamwidth.org/ -- https://mail.python.org/mailman/listinfo/python-list