Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <python-python-list@m.gmane.org>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=python.org; s=200901; t=1352855168; bh=rkVzH/LvD2ickONXF9rzMNmWu1PVktZqkZg5xKJJVas=; h=To:From:Subject:Date:Message-ID:References:Mime-Version: Content-Type:Content-Transfer-Encoding:In-Reply-To; b=OKj5ISjPVwgkdQRrWnSAGpKa2QJUeJ8gwJ4FGi5HpG+1EE/+dqupmmQlUlsGcD9wO oLVwQC9EA5Ppe9PsRkR0GkVXF6IN0lYgWv9AyQIH1s0TzVFe58KY7TM7wsXKj588wG zV7xUDDnXMxfi+vuTVXI0SNk36L1e7wcsPSftCc0=
X-Spam-Status: OK 0.001
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'ideally': 0.04; 'column': 0.07; 'internally': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'index': 0.13; 'from:name:christian heimes': 0.16; 'hashes': 0.16; 'lookups': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'storing': 0.16; 'subject:Generate': 0.16; 'subject:URL': 0.16; 'worst': 0.16; 'from:addr:python.org': 0.17; 'header:In-Reply- To:1': 0.25; 'header:User-Agent:1': 0.26; 'header:X-Complaints- To:1': 0.28; 'cpu': 0.29; 'exposed': 0.29; 'publicly': 0.29; 'to:addr:python-list': 0.33; 'table': 0.35; 'received:org': 0.36; 'but': 0.36; 'data': 0.37; 'subject:: ': 0.38; 'to:addr:python.org': 0.39; 'header:Received:5': 0.40; 'kind': 0.61; 'million': 0.72; 'collision': 0.84; 'complexity': 0.84
X-Injected-Via-Gmane: http://gmane.org/
To: python-list@python.org
From: Christian Heimes <christian@python.org>
Subject: Re: Generate unique ID for URL
Date: Wed, 14 Nov 2012 02:05:57 +0100
References: <0692e6a2-343c-4eb0-be57-fe5c815efb99@googlegroups.com> <k7ulda$geh$1@reader1.panix.com> <133e0be5-63af-4f72-9d0a-c59b04aa4ce4@googlegroups.com> <CALvWhxsMx34QdNNi0dpMCZ_VL055gSY8v_kNvfsEW7CSMK-N_w@mail.gmail.com> <mailman.3656.1352853781.27098.python-list@python.org> <9feb1237-b495-4367-8108-4d6291a5a05a@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Gmane-NNTP-Posting-Host: f049228186.adsl.alicedsl.de
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121028 Thunderbird/16.0.2
In-Reply-To: <9feb1237-b495-4367-8108-4d6291a5a05a@googlegroups.com>
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.3658.1352855170.27098.python-list@python.org>
Lines: 11
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1352855170 news.xs4all.nl 6985 [2001:888:2000:d::a6]:43297
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:33282

Am 14.11.2012 01:50, schrieb Richard:
> These URL ID's would just be used internally for quick lookups, not exposed publicly in a web application.
> 
> Ideally I would want to avoid collisions altogether. But if that means significant extra CPU time then 1 collision in 10 million hashes would be tolerable.

Are you storing the URLs in any kind of database like a SQL database? A
proper index on the data column will avoid full table scans. It will
give you almost O(1) complexity on lookups and O(n) worst case
complexity for collisions.