Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > python hash function

Reply
Thread Tools

python hash function

 
 
Damien Morton
Guest
Posts: n/a
 
      06-24-2003
Ive been doing some investigation of python hashtables and the hash
function used in Python.

It turns out, that when running pystone.py, as much time is spent in
string_hash() as is spent in lookdict_string(). If you look at
python's hash function, shown below, you can get an idea why - a
multiply is used for every character in the string.

static long
string_hash1(register char *p, int size)
{
register int len;
register long x;

len = size;
x = *p << 7;
while (--len >= 0)
x = (100003*x) ^ *p++;
x ^= size;
return x;
}

Looking around the web I found the following hash function, which is
much faster, and seems to distribute better than the python hash
function.

static long
string_hash3(register char *p, register int size)
{
register long x;
register char c;

x = 0xd2d84a61;
while (c = *p++)
x ^= ( (x<<7) + c + (x>>5) );
return x;
}

I also came up with a hash function of my own, which seems to
distribute near-perfectly (in the sense of being comparable to
assigning, as hashes, random numbers to unique strings) and be faster
yet (at least, on my P4 box).

static long
string_hash6(register unsigned short *p, int size)
{
register short s;
register unsigned long x = 0;

if (size == 0) return 0;

len = (size+1) >> 1;
while (len--) {
x += (x>>14) + (*p++ * 0xd2d84a61);
}
x += (x>>14) + (size*0xd2d84a61);

return x;
}

Ive tested these functions by hashing a large set of strings generated
by instrumenting the python interpeter to emit a string every time a
string is added to a dictionary. These strings are hashed and thrown
into the buckets of various sized tables. I then calculate sigma
statistics (sum((observed-expected)^2)/(N-1)) for the number of items
in the buckets of those tables.

Im not sure what other tests to try out. Im hoping that someone on
c.l.py has some experience in testing hash functions, and can suggest
some additional tests and/or tweaks.
 
Reply With Quote
 
 
 
 
John J. Lee
Guest
Posts: n/a
 
      06-24-2003
http://www.velocityreviews.com/forums/(E-Mail Removed) (Damien Morton) writes:

> Ive been doing some investigation of python hashtables and the hash
> function used in Python.

[...]

Have you had a look at the python-dev archives? Bound to be stuff
there about this general area.


John
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
Hash#select returns an array but Hash#reject returns a hash... Srijayanth Sridhar Ruby 19 07-02-2008 12:49 PM
In 'HashMap.put', "if (e.hash == hash && eq(k, e.key))" ? Red Orchid Java 3 01-30-2006 07:04 PM
write a function such that when ever i call this function in some other function .it should give me tha data type and value of calling function parameter komal C++ 6 01-25-2005 11:13 AM
standard library for hash table storage and hash algorithm Pieter Claassen C Programming 1 08-04-2004 03:11 AM



Advertisments