Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!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.016
X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; 'say,': 0.05; 'column': 0.07; 'memory.': 0.07; 'string': 0.09; '128': 0.09; '22,': 0.09; '32-bit': 0.09; 'assuming': 0.09; 'subject:keys': 0.09; 'cc:addr :python-list': 0.11; 'python': 0.11; 'adam': 0.16; 'arbitrarily': 0.16; 'check.': 0.16; 'directly?': 0.16; 'dump': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'hashes': 0.16; 'subject:sqlite3': 0.16; 'truncate': 0.16; 'wrote:': 0.18; 'obviously': 0.18; 'thu,': 0.19; 'cc:addr:python.org': 0.22; 'load': 0.23; '(such': 0.24; 'bytes': 0.24; 'integer': 0.24; '---': 0.24; 'cc:2**0': 0.24; 'header:In- Reply-To:1': 0.27; 'function': 0.29; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'asked': 0.31; 'gives': 0.31; 'that.': 0.31; '(maybe': 0.31; 'becomes': 0.33; 'table': 0.34; 'maybe': 0.34; 'operations': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'disk': 0.36; 'ram': 0.36; 'set.': 0.36; 'pm,': 0.38; 'that,': 0.38; 'anything': 0.39; 'enough': 0.39; 'space': 0.40; 'days': 0.60; 'then,': 0.60; 'simple': 0.61; 'further': 0.61; 'save': 0.62; 'chance': 0.65; 'occur': 0.65; 'close': 0.67; 'fact,': 0.69; 'million': 0.74; '50%': 0.78; 'birthday': 0.84; 'characters,': 0.84; 'collision': 0.84; 'fast,': 0.84; 'paradox': 0.84; '32gb': 0.91; 'divided': 0.91; 'to:none': 0.92; 'average': 0.93; 'hundred': 0.95
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:cc :content-type; bh=AGz0fhRc7rhPWobkXtIA6ODyzKp2oSgwdBwRLXo52hE=; b=mR3dCTs8wSnDXqrc0S/u1kZyLywN0dmo0+XI1rkDXjNcrb2KW7ftNz+JMCZ4mgSXGQ vRAZhsgeQ0K0kapiJz7Ba1QMqEedx4J+Wwxc+lX3oOydXqhpZWmp+IF7KWlIqUMP7yx7 Mdk+mPwZMh5Bk6XI4hxRuKFRx4PIb2S7IR17CkuLHQZD8MQY67dnr5sTzLJCKRDTGwKE O3TU9Dp3tb2dO5iKu1wdeV6IEEzZ+8WW6tVmUq0B084+TkeTjG3hg4HU6sVXhvT9NypN gHIz4GkrJY/44321J/zWKyABiaw4P5U/Bp5erSsSE4psV5oS4LvFNouwGx8GxL9JVHMd /TGQ==
MIME-Version: 1.0
X-Received: by 10.58.89.242 with SMTP id br18mr395542veb.66.1400767723237; Thu, 22 May 2014 07:08:43 -0700 (PDT)
In-Reply-To: <tcb15bx6oj.ln2@news.ducksburg.com>
References: <jn415bx6uf.ln2@news.ducksburg.com> <mailman.10218.1400763549.18130.python-list@python.org> <tcb15bx6oj.ln2@news.ducksburg.com>
Date: Fri, 23 May 2014 00:08:43 +1000
Subject: Re: hashing strings to integers for sqlite3 keys
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
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: <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.10222.1400767725.18130.python-list@python.org>
Lines: 23
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1400767725 news.xs4all.nl 2841 [2001:888:2000:d::a6]:48544
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:71892

On Thu, May 22, 2014 at 11:41 PM, Adam Funk <a24061@ducksburg.com> wrote:
> On further reflection, I think I asked for that.  In fact, the table
> I'm using only has one column for the hashes --- I wasn't going to
> store the strings at all in order to save disk space (maybe my mind is
> stuck in the 1980s).

That's a problem, then, because you will see hash collisions. Maybe
not often, but they definitely will occur if you have enough strings
(look up the birthday paradox - with a 32-bit arbitrarily selected
integer (such as a good crypto hash that you then truncate to 32
bits), you have a 50% chance of a collision at just 77,000 strings).

Do you have enough RAM to hold all the strings directly? Just load 'em
all up into a Python set. Set operations are fast, clean, and easy.
Your already_seen function becomes a simple 'in' check. These days you
can get 16GB or 32GB of RAM in a PC inexpensively enough; with an
average string size of 80 characters, and assuming Python 3.3+, that's
about 128 bytes each - close enough, and a nice figure. 16GB divided
by 128 gives 128M strings - obviously you won't get all of that, but
that's your ball-park. Anything less than, say, a hundred million
strings, and you can dump the lot into memory. Easy!

ChrisA