Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!bcyclone03.am1.xlned.com!bcyclone03.am1.xlned.com!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!194.109.133.90.MISMATCH!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <skip.montanaro@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.005
X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; '16,': 0.03; 'array.': 0.07; 'extent': 0.07; 'cc:addr:python-list': 0.09; 'subject:How': 0.09; 'lookup': 0.09; 'python': 0.10; 'thu,': 0.15; 'big,': 0.16; 'cc:name:python': 0.16; 'correctly,': 0.16; 'magic': 0.16; 'resize': 0.16; 'threads': 0.16; 'wrote:': 0.16; 'skip': 0.18; '2015': 0.20; 'cc:2**0': 0.20; 'cc:addr:python.org': 0.20; 'constant': 0.22; 'nearly': 0.23; 'header:In-Reply-To:1': 0.24; 'message-id:@mail.gmail.com': 0.27; 'initial': 0.28; 'hash': 0.29; 'array': 0.29; 'operations.': 0.33; 'lists': 0.34; 'received:google.com': 0.35; 'done': 0.35; 'possible,': 0.35; "isn't": 0.35; 'but': 0.36; 'too': 0.36; 'subject:work': 0.36; 'subject:?': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'itself': 0.38; 'still': 0.40; 'avoid': 0.61; 'email addr:gmail.com': 0.62; 'linked': 0.63; 'places': 0.64; 'believe': 0.66; 'jul': 0.72; 'grow': 0.75; 'execution.': 0.84; 'memories': 0.84
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=xipH2VE2CVYCE0WpeOu2Nu8wFY6Z1k8SLyoIYa5XrfU=; b=D9hCKcG3gTIANzDy5pS2EFH5Zj9sGZLi76cUmvvraZFmVRv1KUBfwajoiwKnn+JAjM 7HPl8WhmFNI8Er4rf68YfAQeiIFBxD5uDn0oqOTaKYx7kULC3kPavDRsuWUjYly4H8zE Ge5ZtC1g+K/WtuUcsBeG1mwRw+wIsgwHluqFvLdPmHc/YvpnlNACMUOU1viogrNyaPmm M43tLE3gCZUPG+UEYdcfRar+e8fC8/tu196G5N3caJIyEsJZL4a5j/CAONFaVzwvlGf9 s+KPIRw828vqpnW2qgIMtglrZGMzMruXgdMcynq4GCp+pZ0Gi4RWBOkKEf+aGqCTlgt7 uM4Q==
MIME-Version: 1.0
X-Received: by 10.107.15.226 with SMTP id 95mr246059iop.44.1437073102399; Thu, 16 Jul 2015 11:58:22 -0700 (PDT)
In-Reply-To: <948FE9D4-63CF-4730-B5F0-675F780A2481@gmail.com>
References: <A2CB3AFE-ACB3-4AD3-B35B-4BC6BA3D729D@gmail.com> <CANc-5UwGj5uT_ZBZETQz25O5NeEResUg=P0zL_oHEdK14VkThQ@mail.gmail.com> <948FE9D4-63CF-4730-B5F0-675F780A2481@gmail.com>
Date: Thu, 16 Jul 2015 13:58:22 -0500
Subject: Re: How does a dictionary work exactly?
From: Skip Montanaro <skip.montanaro@gmail.com>
To: "yoursurrogategod@gmail.com" <yoursurrogategod@gmail.com>
Cc: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.20+
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.603.1437073105.3674.python-list@python.org>
Lines: 15
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1437073105 news.xs4all.nl 2845 [2001:888:2000:d::a6]:54709
X-Complaints-To: abuse@xs4all.nl
X-Received-Bytes: 4212
X-Received-Body-CRC: 4256662374
Xref: csiph.com comp.lang.python:93950

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