Subject: Re: Hash function for compression algorithms

From: [email-masked] (Khanh Nguyen)
Date: 28 Nov 1994 16:15:31 GMT

In article <[email-masked]>  writes:
> Hello all,
> 
> I'm writing (or at least trying to write) a new compression
> algorithm/program, and like many others, I'm using hash tables
> to access strings from the input.
> I've experimented a few days, but wasn't able to find anything
> satisfactory, so instead of re-inventing the wheel, I ask for
> your kind suggestions: What hash funcition is well suited for
> this (i.e from strings of varied length to integers).
> If ineterst is shown, I'll post a summary of replies.
> 
> Thanx,
> 
> --Eitan.
Take a look at the article " Fast Hashing of Variable Length Text Strings  
" of Peter K. Pearson in Communications of the ACM , June 1990 volume 33  
number 6.
AFAIN, it is the most proper thing for you.
I am writing some compression programs too, so hoping we can exchange some  
ideas ?
All the bests,
Khanh Nguyen
Vienna University of Technology

---

From: [email-masked] (Chris W. Rea [UL])
Date: Tue, 29 Nov 1994 22:54:09 GMT

In article <[email-masked]>,
>If ineterst is shown, I'll post a summary of replies.

This is one I use for a project I'm currently working on:

/* HashWord takes W, the ASCII string we want to hash
**                S, the length of string W (ie: strlen(W))
**                R, choose the next R'th value to resolve a collision
*/
ULONG HashWord(UBYTE *W, UBYTE S, UWORD R)
{
  ULONG HashValue=0;
  UWORD Seed[3]={0,0,0}, i=0;

  Seed[0]=R+119;
  Seed[1]=R*727+R*R;
  Seed[2]=5033-R*R*R;

  seed48(Seed);
  for(i=0; i<S; i++) { HashValue+=mrand48()*W[i]*W[i]+i; }

  return(HashValue);
}

That is nearly as good a hash function as you can get. It takes the first
character, squares it, then multiplies that times a random number. It
sums these up and then returns that as a long integer.

The 'R' field I added to help with collision resolution, since I use open
addressing in my hash file. I start by passing it the string and R=0...
if that collides with a record already in that position in the hash file,
I set R=1, rehash, etc...

I've got an application that currently has 135000 out of 300000 or so records
full, and with the above hashing algorithm I get an average of 1.3 seeks to
find a record. Of course, I'll have to wait until the hash file nears 80%
or 90% capacity before I get a good estimate, but I'm guessing it won't
grow larger than 2 seeks to find a record.

 -| CHRIS W. REA [UL] U. of T. CompSci    [email-masked] |-
 [| "I open my mouth and some idiot speaks" -Midnight Oil (Naked Flame) |]
 -| Zl bcvavbaf ner zl bja; vs lbh qba'g nterr jvgu gurz, gura shpx bss |-