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). -- https://mail.python.org/mailman/listinfo/python-list
