drsalists at gmail.com
Sun Mar 9 23:08:20 CET 2014
On Sun, Mar 9, 2014 at 2:43 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Dan Stromberg <drsalists at gmail.com>:
>> On Sun, Mar 9, 2014 at 2:32 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
>>> There is no O(1) hash table.
> 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
More information about the Python-list