Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <d@davea.name>
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; 'algorithm': 0.03; 'true,': 0.04; 'cpython': 0.05; 'seemed': 0.07; 'subject:file': 0.07; 'dict': 0.09; 'lookup': 0.09; 'cc:addr:python-list': 0.10; 'aug': 0.13; '3.3,': 0.16; 'datasets.': 0.16; 'dictionaries': 0.16; 'efficiency.': 0.16; 'entry.': 0.16; 'foolishly': 0.16; 'generator.': 0.16; 'hashes': 0.16; 'randomize': 0.16; 'wrote:': 0.17; '>>>': 0.18; 'versions': 0.20; 'default,': 0.22; 'cc:2**0': 0.23; 'cc:no real name:2**0': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'header:User-Agent:1': 0.26; 'common': 0.26; 'am,': 0.27; 'older': 0.27; 'andrew': 0.27; 'dos': 0.27; 'entries': 0.27; 'possible,': 0.27; 'chris': 0.28; '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; 'function.': 0.33; 'version': 0.34; 'wrong': 0.34; 'pm,': 0.35; 'table': 0.35; 'too.': 0.35; 'there': 0.35; 'but': 0.36; 'anything': 0.36; 'thank': 0.36; 'too': 0.36; 'possible': 0.37; 'option': 0.37; 'subject:: ': 0.38; 'received:192': 0.39; 'where': 0.40; 'received:192.168': 0.40; 'end': 0.40; 'claim': 0.60; 'replying': 0.64; 'response.': 0.67; 'header:Reply-To:1': 0.68; 'received:74.208': 0.71; 'reply-to:no real name:2**0': 0.72; 'collision': 0.84; 'intending': 0.84; 'ridiculously': 0.84; 'glad': 0.86; 'increases': 0.91; 'sensibly': 0.91; 'suffer': 0.91; 'angel': 0.93; 'poorly': 0.93
Date: Thu, 09 Aug 2012 19:42:48 -0400
From: Dave Angel <d@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120714 Thunderbird/14.0
MIME-Version: 1.0
To: Chris Angelico <rosuav@gmail.com>
Subject: Re: save dictionary to a file without brackets.
References: <930ab3d8-4ab9-446d-9970-ee811eb70a44@googlegroups.com> <F1B463BB-19A6-4DB1-99B3-929CCBFB5920@gmail.com> <50241F14.2060209@tim.thechases.com> <36EA3847-6713-4C12-B47B-9B5E10325F00@gmail.com> <502429C3.5000600@tim.thechases.com> <mailman.3120.1344548050.4697.python-list@python.org> <MsWUr.1183213$%k.489563@fx20.am4> <5024392D.3010306@davea.name> <CAPTjJmpvLCAi21HuKFFK0qud5d=y1CEDbgL+pKGsXcYjD2hCGg@mail.gmail.com>
In-Reply-To: <CAPTjJmpvLCAi21HuKFFK0qud5d=y1CEDbgL+pKGsXcYjD2hCGg@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Provags-ID: V02:K0:tA5jYUHsVT27bzCn52/qSWWjo0uRdS0zlpruypBWYLN O7rrg8V6QuFtphocaydqdsHXQdPQZfelZCJeGUL+B8I0AdNGux hILdfld/2ncNGTpoalmCSpA5ueDlP980UUyc1T5ECG0RE36HlN qvhxK0WdmuQWxja9yBM7eSc/3ZaSYw9aA0RDzHyBiCzONuss/t p+531KLmdNvYLIoKWzrplimHkgPKXrnfrPwTJmn/6LCXJ4zkf9 mdTf8C5AKwrBY1knvPxVq6JUH1+woNvzn4BYV2G2RUov3NLcoO w1fP27oTANLxgtxe47dZS1vjC4TdJRZU7bnt5W8S4jtVnbifw= =
Cc: python-list@python.org
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.12
Precedence: list
Reply-To: d@davea.name
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://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: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.3138.1344555793.4697.python-list@python.org>
Lines: 36
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1344555793 news.xs4all.nl 6863 [2001:888:2000:d::a6]:57619
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:26836

On 08/09/2012 06:53 PM, Chris Angelico wrote:
> On Fri, Aug 10, 2012 at 8:26 AM, Dave Angel <d@davea.name> 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

Thank you to you and others, who have corrected my over-general
response.  I was not intending to claim anything about either a
deliberate DOS, nor a foolishly chosen hash function.  But the message I
was replying to seemed to me to claim that for large datasets, even a
good hash algorithm would end up giving O(n) performance.



-- 

DaveA