Re: How does a dictionary work exactly?

References	<A2CB3AFE-ACB3-4AD3-B35B-4BC6BA3D729D@gmail.com> <CANc-5UwGj5uT_ZBZETQz25O5NeEResUg=P0zL_oHEdK14VkThQ@mail.gmail.com> <948FE9D4-63CF-4730-B5F0-675F780A2481@gmail.com>
Date	2015-07-16 13:58 -0500
Subject	Re: How does a dictionary work exactly?
From	Skip Montanaro <skip.montanaro@gmail.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.603.1437073105.3674.python-list@python.org> (permalink)

Show all headers | View raw

On Thu, Jul 16, 2015 at 1:36 PM, yoursurrogategod@gmail.com
<yoursurrogategod@gmail.com> wrote:
> If I understand correctly, lookup would not be a constant, yes?

On the contrary, that's what you desire, nearly constant time
execution. To the greatest extent possible, you want the linked lists
to be of length zero or one. Part of the magic is in figuring out good
places to expand the size of the hash array. You don't want it to grow
too big, but you still want most linked lists to be very short. The
resize operation isn't done too often because it itself is expensive.
I believe Python dicts start out with an overly large initial hash
array (again, dredging up old memories of threads on python-dev) as an
optimization to avoid lots of early resize operations.

Skip

Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: How does a dictionary work exactly? Skip Montanaro <skip.montanaro@gmail.com> - 2015-07-16 13:58 -0500
  Re: How does a dictionary work exactly? Ned Batchelder <ned@nedbatchelder.com> - 2015-07-17 07:32 -0700
    Re: How does a dictionary work exactly? Skip Montanaro <skip.montanaro@gmail.com> - 2015-07-17 10:58 -0500

csiph-web