General Hash Functions In Python

[Arash Partow]

Hi all,

I've ported various hash functions to python if anyone is interested:

def RSHash(key):
a = 378551
b = 63689
hash = 0
for i in range(len(key)) :
hash = hash * a + ord(key[i])
a = a * b
return (hash & 0x7FFFFFFF)
def JSHash(key):
hash = 1315423911
for i in range(len(key)) :
hash ^= ((hash << 5) + ord(key[i]) + (hash >2))
return (hash & 0x7FFFFFFF)
def PJWHash(key):
BitsInUnsignedI nt = 4 * 8
ThreeQuarters = long((BitsInUns ignedInt * 3) / 4)
OneEighth = long(BitsInUnsi gnedInt / 8)
HighBits = (0xFFFFFFFF) << (BitsInUnsigned Int - OneEighth)
hash = 0
test = 0

for i in range(len(key)) :
hash = (hash << OneEighth) + ord(key[i])
test = hash & HighBits
if test != 0:
hash = (( hash ^ (test >ThreeQuarters) ) & (~HighBits));
return (hash & 0x7FFFFFFF)
def ELFHash(key):
hash = 0
x = 0
for i in range(len(key)) :
hash = (hash << 4) + ord(key[i])
x = hash & 0xF0000000
if x != 0:
hash ^= (x >24)
hash &= ~x
return (hash & 0x7FFFFFFF)
def BKDRHash(key):
seed = 131 # 31 131 1313 13131 131313 etc..
hash = 0
for i in range(len(key)) :
hash = (hash * seed) + ord(key[i])
return (hash & 0x7FFFFFFF)
def SDBMHash(key):
hash = 0
for i in range(len(key)) :
hash = ord(key[i]) + (hash << 6) + (hash << 16) - hash;
return (hash & 0x7FFFFFFF)
def DJBHash(key):
hash = 5381
for i in range(len(key)) :
hash = ((hash << 5) + hash) + ord(key[i])
return (hash & 0x7FFFFFFF)
def DEKHash(key):
hash = len(key);
for i in range(len(key)) :
hash = ((hash << 5) ^ (hash >27)) ^ ord(key[i])
return (hash & 0x7FFFFFFF)
def APHash(key):
hash = 0
for i in range(len(key)) :
if ((i & 1) == 0):
hash ^= ((hash << 7) ^ ord(key[i]) ^ (hash >3))
else:
hash ^= (~((hash << 11) ^ ord(key[i]) ^ (hash >5)))
return (hash & 0x7FFFFFFF)
print RSHash ('abcdefghijklm nopqrstuvwxyz12 34567890')
print JSHash ('abcdefghijklm nopqrstuvwxyz12 34567890')
print PJWHash ('abcdefghijklm nopqrstuvwxyz12 34567890')
print ELFHash ('abcdefghijklm nopqrstuvwxyz12 34567890')
print BKDRHash('abcde fghijklmnopqrst uvwxyz123456789 0')
print SDBMHash('abcde fghijklmnopqrst uvwxyz123456789 0')
print DJBHash ('abcdefghijklm nopqrstuvwxyz12 34567890')
print DEKHash ('abcdefghijklm nopqrstuvwxyz12 34567890')
print APHash ('abcdefghijklm nopqrstuvwxyz12 34567890')

Arash Partow
_______________ _______________ _______________ ___________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

[Paul Rubin]

"Arash Partow" <pa****@gmail.c omwrites:

I've ported various hash functions to python if anyone is interested:

Are these useful for any particular interoperabilit y purposes?
Otherwise I'd say just one such hash is plenty, or maybe don't even
bother, since Python's built-in dicts are sufficient for most
applications that call for hashing, and the cryptographic hashes are
available for when you really care about uniformity of the hash
output.

for i in range(len(key)) :
hash = hash * a + ord(key[i])
a = a * b

As a stylistic issue, I'd write this:

for c in key:
hash = hash * a + ord(c)
a *= b

and similarly for the other similar loops.

[Arash Partow]

Hi Paul,

For different data types different hash functions work
better/worse aka fewer or more collisions.

I believe the more choice people have and also the more
ways people see how a particular thing can be done, then
the easier it will be for them to come up with their own
specific efficient solutions.

That said, I believe at least one (most likely more) of
the hash functions in the group above will most always work
better (ala less collisions) than the standard default hash
available in the built-in dict for any random set of strings.

Please feel free to prove me wrong :)


Arash Partow
_______________ _______________ _______________ ___________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net
Paul Rubin wrote:

"Arash Partow" <pa****@gmail.c omwrites:

I've ported various hash functions to python if anyone is interested:

Are these useful for any particular interoperabilit y purposes?
Otherwise I'd say just one such hash is plenty, or maybe don't even
bother, since Python's built-in dicts are sufficient for most
applications that call for hashing, and the cryptographic hashes are
available for when you really care about uniformity of the hash
output.

for i in range(len(key)) :
hash = hash * a + ord(key[i])
a = a * b

As a stylistic issue, I'd write this:

for c in key:
hash = hash * a + ord(c)
a *= b

and similarly for the other similar loops.

[Paul Rubin]

"Arash Partow" <pa****@gmail.c omwrites:

For different data types different hash functions work
better/worse aka fewer or more collisions.

But you give no indication of which of those hashes works best for
what kind of data. How is the user supposed to figure out which one
to choose?

[Robert Kern]

Arash Partow wrote:

That said, I believe at least one (most likely more) of
the hash functions in the group above will most always work
better (ala less collisions) than the standard default hash
available in the built-in dict for any random set of strings.

Please feel free to prove me wrong :)

You have it backwards. You are the one making the positive assertion. You get to
prove yourself correct.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

[Arash Partow]

Trial and error - how else? :)

I believe finding a perfect hash function for
every kind and combination of data is a very
very time consuming operation. Also there is
the common case where the data is online
(ie: stateless) that said it doesn't mean you
can't make assumptions about the kind of data.

Arash Partow
_______________ _______________ _______________ ___________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net
Paul Rubin wrote:

"Arash Partow" <pa****@gmail.c omwrites:

For different data types different hash functions work
better/worse aka fewer or more collisions.

But you give no indication of which of those hashes works best for
what kind of data. How is the user supposed to figure out which one
to choose?

[Arash Partow]

That is true, but I'm not about to do something
that might potentially prove my point wrong... :)

Arash Partow
_______________ _______________ _______________ ___________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net
Robert Kern wrote:

>
You have it backwards. You are the one making the positive assertion. You get to
prove yourself correct.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

[Stefan Behnel]

Arash Partow wrote:

I've ported various hash functions to python if anyone is interested:
[snip]

Ok, so if you think they are useful, what about writing up an article for the
Python Cookbook that describes their usage and specific advantages/disadvantages?

http://aspn.activestate.com/ASPN/Python/Cookbook/

Stefan

[John Machin]

On 17/07/2006 5:52 PM, Arash Partow wrote:

Hi Paul,

For different data types different hash functions work
better/worse aka fewer or more collisions.

I believe the more choice people have and also the more
ways people see how a particular thing can be done, then
the easier it will be for them to come up with their own
specific efficient solutions.

Who is likely to bother? In timbot we trust. Have you read the comments
at the start of Objects/dictobject.c?

>
That said, I believe at least one (most likely more) of
the hash functions in the group above will most always work
better (ala less collisions) than the standard default hash
available in the built-in dict for any random set of strings.

[Aside: it's not "in the built-in dict". Any type which wants its
instances to be hashable defines its own hash method, one that suits the
type.]

This belief would be based on:
(a) actual testing by you
or (b) a refereed academic paper which did such tests on hash functions
(including the Python "standard default hash")
or (c) ...???

What is the Python "standard default hash", anyway? It is written in C.
Wouldn't it have been a good idea to provide a Python function for it,
so that people who are going to "come up with their own specific
efficient solutions" had something to compare with? Or perhaps they are
intended to "port" your functions back into C?

A few more questions:

Why have you truncated the answers to 31 bits?

Have you tested that these functions produce the same output (apart from
the 31-bit thing) as the originals that you worked from? The reason for
asking is that Python unlike C doesn't lose any bits in the <<
operation; if this is followed by a >you may be shifting some unwanted
1-bits back in again.

Talking about not losing bits: For your 36-byte example input, the
SDBMHash (with its << 16) is up to about 566 bits before you truncate it
to 31. A little over the top, perhaps. Maybe not the fastest way of
doing it.

What is the purpose of the calls to long() in PJWHash?

And the $64K question: What is the quintessential difference between
PJWHash and ELFHash?

Cheers,
John

[Arash Partow]

John Machin wrote:

Who is likely to bother? In timbot we trust. Have you read the comments
at the start of Objects/dictobject.c?

No I haven't probably wont be anytime soon, as far as time, well
people interested, as is how started my original port, would be more
than willing to try/assess the routines for sets of strings that they
wish to hash etc.. this site may help explain plus has some code
snippets that may help you understand what I mean.

http://www.partow.net/programming/ha...ons/index.html

[Aside: it's not "in the built-in dict". Any type which wants its
instances to be hashable defines its own hash method, one that suits the
type.]

This belief would be based on:
(a) actual testing by you
or (b) a refereed academic paper which did such tests on hash functions
(including the Python "standard default hash")
or (c) ...???

Experience has shown me that the belief than one "default" way of
hashing is generally not the optimal way for the overwhelming
majority of data, but then again....

What is the Python "standard default hash", anyway? It is written in C.
Wouldn't it have been a good idea to provide a Python function for it,
so that people who are going to "come up with their own specific
efficient solutions" had something to compare with? Or perhaps they are
intended to "port" your functions back into C?

The above link provides a very simple hash test framework, the
"standard default hash" can be placed in there and tested amongst
the other algorithms.

A few more questions:

Why have you truncated the answers to 31 bits?

algorithms were adapted from unsigned int, i should have removed that
final truncation in python.

Have you tested that these functions produce the same output (apart from
the 31-bit thing) as the originals that you worked from? The reason for
asking is that Python unlike C doesn't lose any bits in the <<
operation; if this is followed by a >you may be shifting some unwanted
1-bits back in again.

Some of them do others don't (not really important unless you are
trying to be compatible with other implementations which this is
not), I am aware of python not truncating/wrapping of values under
various operations, I believe its a nice little side effect from
python which gives more bits to play with as long as you don't
truncate them as I have.

Talking about not losing bits: For your 36-byte example input, the
SDBMHash (with its << 16) is up to about 566 bits before you truncate it
to 31. A little over the top, perhaps. Maybe not the fastest way of
doing it.

Possibly, do you have a better solution I'm very keen to learn...

What is the purpose of the calls to long() in PJWHash?

trying to cast to long, looking at it now its rather superfluous.

And the $64K question: What is the quintessential difference between
PJWHash and ELFHash?

Nothing, elf is essentially pjw, its just optimised for 32-bit systems
in that the calculation for th's etc are static where has pjw
required sizeof to calc the th's which i couldn't find a way of doing,
so i fudged it in the hope that maybe sometime in the future a work
around of sorts could be developed.

Again this was just a simple posting, I hoped to maybe gets some
comments and may present some ideas to people, I don't expect anyone
to drop everything and start using these, just thought it might be
something interesting for this NG. btw I'm not a very good python
programmer ATM.


Arash Partow
_______________ _______________ _______________ ___________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net