Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 22 May 2014 08:09:59 -0500
From: Tim Chase <python.list@tim.thechases.com>
To: Adam Funk <a24061@ducksburg.com>
Subject: Re: hashing strings to integers for sqlite3 keys
In-Reply-To: <jn415bx6uf.ln2@news.ducksburg.com>
References: <jn415bx6uf.ln2@news.ducksburg.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.10220.1400764235.18130.python-list@python.org>
Lines: 45
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:71886

On 2014-05-22 12:47, Adam Funk wrote:
> I'm using Python 3.3 and the sqlite3 module in the standard library.
> I'm processing a lot of strings from input files (among other
> things, values of headers in e-mail & news messages) and suppressing
> duplicates using a table of seen strings in the database.
> 
> It seems to me --- from past experience with other things, where
> testing integers for equality is faster than testing strings, as
> well as from reading the SQLite3 documentation about INTEGER
> PRIMARY KEY --- that the SELECT tests should be faster if I am
> looking up an INTEGER PRIMARY KEY value rather than TEXT PRIMARY
> KEY.  Is that right?

If sqlite can handle the absurd length of a Python long, you *can* do
it as ints:

  >>> from hashlib import sha1
  >>> s = "Hello world"
  >>> h = sha1(s)
  >>> h.hexdigest()
  '7b502c3a1f48c8609ae212cdfb639dee39673f5e'
  >>> int(h.hexdigest(), 16)
  703993777145756967576188115661016000849227759454L

That's a pretty honkin' huge int for a DB key, but you can use it.
And it's pretty capped on length regardless of the underlying
string's length.

> If so, what sort of hashing function should I use?  The "maxint" for
> SQLite3 is a lot smaller than the size of even MD5 hashes.  The only
> thing I've thought of so far is to use MD5 or SHA-something modulo
> the maxint value.  (Security isn't an issue --- i.e., I'm not
> worried about someone trying to create a hash collision.)

You could truncate that to something like

  >>> int(h.hexdigest()[-8:], 16)

which should give you something that would result in a 32-bit number
that should fit in sqlite's int.

-tkc