Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!feed.xsnews.nl!border-2.ams.xsnews.nl!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.007 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'true,': 0.04; 'cpython': 0.05; 'subject:file': 0.07; 'dict': 0.09; 'lookup': 0.09; 'aug': 0.13; '3.3,': 0.16; 'datasets.': 0.16; 'dictionaries': 0.16; 'efficiency.': 0.16; 'entry.': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'generator.': 0.16; 'hashes': 0.16; 'randomize': 0.16; 'wrote:': 0.17; 'versions': 0.20; 'received:209.85.214.174': 0.21; 'default,': 0.22; 'header:In- Reply-To:1': 0.25; 'common': 0.26; 'am,': 0.27; 'older': 0.27; 'andrew': 0.27; 'dos': 0.27; 'entries': 0.27; 'possible,': 0.27; 'message-id:@mail.gmail.com': 0.27; 'hash': 0.29; 'sensible': 0.29; 'unlikely': 0.29; "i'm": 0.29; 'becomes': 0.30; 'fri,': 0.30; 'function': 0.30; '(and': 0.32; 'cases,': 0.33; 'to:addr :python-list': 0.33; 'version': 0.34; 'received:google.com': 0.34; 'wrong': 0.34; 'pm,': 0.35; 'table': 0.35; 'too.': 0.35; 'received:209.85': 0.35; 'there': 0.35; 'but': 0.36; 'too': 0.36; 'possible': 0.37; 'option': 0.37; 'received:209': 0.37; 'subject:: ': 0.38; 'to:addr:python.org': 0.39; 'received:209.85.214': 0.39; 'where': 0.40; 'header:Received:5': 0.40; 'collision': 0.84; 'ridiculously': 0.84; 'glad': 0.86; 'increases': 0.91; 'sensibly': 0.91; 'suffer': 0.91; 'angel': 0.93; 'poorly': 0.93 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 :content-type; bh=anmzU8xAodXmy3nYBfakvFk+DGAzXMzjMpnabOtD25w=; b=Kh062biVTHgPUTkZioQuT3NvZMIy0nEWS2EtRkBPbCzOlkGe/wFtaokQVz2ZBYyB0A BIOvZNRqNDKyrrw4NSQ4cHMtWRdOZEC2H6H3zi6BfJpWQWpc0sKiWgPhZ6E72bwrIXuY HAlCNYfCVS0NfGUMOkYs9Lw7Dmcm4ScqdXLBec27SKo3nYn33fkFbMNvJVFJsGiR709y zvUFUGMt/5dT01QFJmqlZR2JuvhT8IStyogmoc6G7DaiD9GUC5PsSSOUwVmX0n61misw nS0zNA2F58BHRNH515zu0RDLyrNp8hapFhzLm2UmfSVBpp/m6bnScMBj8oe0vJtLLIBT Hjag== MIME-Version: 1.0 In-Reply-To: <5024392D.3010306@davea.name> References: <930ab3d8-4ab9-446d-9970-ee811eb70a44@googlegroups.com> <50241F14.2060209@tim.thechases.com> <36EA3847-6713-4C12-B47B-9B5E10325F00@gmail.com> <502429C3.5000600@tim.thechases.com> <5024392D.3010306@davea.name> Date: Fri, 10 Aug 2012 08:53:43 +1000 Subject: Re: save dictionary to a file without brackets. From: Chris Angelico To: python-list@python.org Content-Type: text/plain; charset=ISO-8859-1 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 24 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1344552827 news.xs4all.nl 6960 [2001:888:2000:d::a6]:59622 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:26828 On Fri, Aug 10, 2012 at 8:26 AM, Dave Angel wrote: > On 08/09/2012 06:03 PM, Andrew Cooper wrote: >> O(n) for all other entries in the dict which suffer a hash collision >> with the searched entry. >> >> True, a sensible choice of hash function will reduce n to 1 in common >> cases, but it becomes an important consideration for larger datasets. > > I'm glad you're wrong for CPython's dictionaries. The only time the > lookup would degenerate to O[n] would be if the hash table had only one > slot. CPython sensibly increases the hash table size when it becomes > too small for efficiency. > > Where have you seen dictionaries so poorly implemented? In vanilla CPython up to version (I think) 3.3, where it's possible to DoS the hash generator. Hash collisions are always possible, just ridiculously unlikely unless deliberately exploited. (And yes, I know an option was added to older versions to randomize the hashes there too. It's not active by default, so "vanilla CPython" is still vulnerable.) ChrisA