Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!rex!spool.mu.edu!snorkelwacker.mit.edu!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.c
Subject: Re: hash function for mac needed
Message-ID: <6766.Jun2023.53.4291@kramden.acf.nyu.edu>
Date: 20 Jun 91 23:53:42 GMT
References: <14207.285B768A@stjhmc.fidonet.org> <14396@dog.ee.lbl.gov>
Organization: IR
Lines: 16

In article <14396@dog.ee.lbl.gov> torek@elf.ee.lbl.gov (Chris Torek) writes:
> 		hash = (hash * 33) + (the character);

I see I've converted you from hash * 31 to hash * 33. :-)

  [ on the typical distribution of hash values with chaining ]

It's worth remembering the power series for exp. If your load factor---
that is, the number N of stored elements divided by the number of hash
values---is x, then there will be about exp(-x)N zero-element chains,
exp(-x)Nx one-element chains, exp(-x)Nx^2/2 two-element, exp(-x)Nx^3/3!
three-element, and so on. This holds up quite well in practice, and lets
you judge accurately how often a branch will be taken or how far it's
worth unrolling a loop when you're working with hash tables.

---Dan