Path: csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <rosuav@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.002
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'exception': 0.03; 'case.': 0.05; 'say,': 0.05; 'python': 0.09; 'check.': 0.09; 'lookup': 0.09; 'bug': 0.10; 'dec': 0.15; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'hashes': 0.16; 'retrieving': 0.16; 'subject:compare': 0.16; 'useless.': 0.16; 'wrote:': 0.17; 'element': 0.17; 'exists': 0.17; 'saying': 0.18; 'header:In-Reply- To:1': 0.25; 'checking': 0.27; 'tree': 0.27; 'message- id:@mail.gmail.com': 0.27; 'dictionary': 0.29; 'hash': 0.29; 'case,': 0.29; 'becomes': 0.30; 'received:209.85.160.46': 0.32; 'to:addr:python-list': 0.33; 'received:google.com': 0.34; 'text': 0.34; 'doing': 0.35; 'pm,': 0.35; 'received:209.85': 0.35; 'but': 0.36; 'does': 0.37; 'being': 0.37; 'quite': 0.37; 'received:209': 0.37; 'subject:: ': 0.38; 'some': 0.38; 'to:addr:python.org': 0.39; 'header:Received:5': 0.40; 'back': 0.62; 'potentially': 0.66; 'collision': 0.84; 'tree,': 0.84; 'walking': 0.91
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=arr8BbJqP1tx2Ev8UtR5702+5iw0bLWc6sSa15QFieo=; b=BMlQufBYT9L2OodkPlBeLRN8ZCTsGo6K7Xc7/8iK9VSOgY/Tp8wYfE/t2EHMNO+eUq jfda+pyXEL9L6Z3274ulwauB7/t5fidUg7V/SgVnHfzpaa3qttJNBb3S/noibuWgoNuW yURW1yqIP7Q0P88jrCRe2KmRuzkoLAayqE/MZpRGFai3o/st/4g96UpK79GHPVZUZMge 5xRI4BT/SIzONxGXE7FzI4z5im8wF8gyeWdvChp3BRoHoEW95A9wLq7lwMpt6J9TdRwz 5tPPnnYdosZ32Ze+2gZVZSQL0ymiFZxZykSe9FHgvMnSK+wjWtyGIlwHNjnXdSBktrjE dHQQ==
MIME-Version: 1.0
In-Reply-To: <b32a0bad-4772-4cb8-b371-869f706a2ac8@googlegroups.com>
References: <CAKhY55PXaMkdnW7qMb-5ConHMcz05Gnkqw4wvyoprBFBd5UFFw@mail.gmail.com> <mailman.538.1354753193.29569.python-list@python.org> <k9p32p$nek$1@dont-email.me> <50c01fe2$0$21853$c3e8da3$76491128@news.astraweb.com> <mailman.549.1354783761.29569.python-list@python.org> <50c085e5$0$29994$c3e8da3$5496439d@news.astraweb.com> <mailman.555.1354796060.29569.python-list@python.org> <b32a0bad-4772-4cb8-b371-869f706a2ac8@googlegroups.com>
Date: Sun, 9 Dec 2012 14:22:21 +1100
Subject: Re: Confused compare function :)
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
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.643.1355023344.29569.python-list@python.org>
Lines: 14
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1355023344 news.xs4all.nl 6879 [2001:888:2000:d::a6]:41704
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:34517

On Sun, Dec 9, 2012 at 2:07 PM, Ramchandra Apte <maniandram01@gmail.com> wrote:
> Not really. I remember a bug saying that only 256 hashes were required of known texts and then the randomization becomes useless.

That requires that someone be able to get you to hash some text and
give back the hash. In any case, even if you _are_ dealing with the
worst-case hash collision attack, all it does is stop a Python
dictionary from being an exception to the general principle. If you're
doing a lookup in, say, a tree, then checking if the element exists
and then retrieving it means walking the tree twice - O(log n) if the
tree's perfectly balanced, though a splay tree would be potentially
quite efficient at that particular case. But there's still extra cost
to the check.

ChrisA