On Sun, Mar 9, 2014 at 4:08 PM, Dan Stromberg <drsali...@gmail.com> wrote: > On Sun, Mar 9, 2014 at 2:43 PM, Marko Rauhamaa <ma...@pacujo.net> wrote: >> Dan Stromberg <drsali...@gmail.com>: >> >>> On Sun, Mar 9, 2014 at 2:32 PM, Marko Rauhamaa <ma...@pacujo.net> wrote: >>>> There is no O(1) hash table. >>> >>> http://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1 >> >> Please elaborate. > > A hash table of fixed size is O(1) until you fill it so full that you > start getting enough collisions to make it O(n), as one bucket becomes > a linked list. This is because the hash function is O(1), and looking > up a value in a C array is O(1). > > A more flexible hash table will not have a fixed size; instead it will > grow itself as needed. This growth operation tends to be O(n), but > happens vanishingly infrequently as the table grows, so it's still > amortized O(1).
A hash table can also only ever be O(1) in the average case. Worst case, everything you put into the hash table has the same hash value, and so the time to fetch an item is entirely dependent on the collision resolution scheme -- e.g. O(n) if a linked list or linear probe is used, or perhaps O(log n) if each bucket is a balanced binary tree. There are schemes such as cuckoo hashing that allow true O(1) worst case access, but they have other drawbacks -- inserts with cuckoo hashing are amortized O(1), and it is even possible for an insert to fail entirely after spending exponential time trying to find a way to arrange things. -- https://mail.python.org/mailman/listinfo/python-list
