torek@elf.ee.lbl.gov (Chris Torek) (06/22/91)
In an article whose referent was deleted by bogus fidonet software (and whose tabs were changed to spaces), I provided this example hashing function: >> hash = 0; >> for (each character) >> hash = (hash * 33) + (the character); >> hash_index = hash & ((some power of two) - 1); In article <14491.28619071@stjhmc.fidonet.org> Dave.Harris@f14.n15.z1.fidonet.org (Dave Harris) writes: >Is the *33 use to keep short sequences has key more random or does it >really help in the distribution of large string too? I am not sure what you are asking here. There are basically three questions you can ask about a hash function: a) Is it fast enough? (complicated functions often take longer than the searches they replace) b) Does it produce a good distribution? (the hash function h(input)=0 is very fast but produces horrible distributions) c) If (b) is true, why does it work? The first two can really only be answered in some specific context. In all the contexts I have tried, this one answers `yes' to both (which is why I recommend it). The third question is the hardest. What *does* that 33 do? I have no idea. All I know is that I have experimented with `easy' functions (functions for which `fast enough' should generally be true) and this one also produces a good distribution. I doubt I still have the mail, but when Margo Seltzer was writing the database code to replace ndbm, she tried a bunch of different functions on a bunch of different data. This one usually worked well---it did not always give the best distributions, but it never performed poorly; some functions that gave better distributions on some data gave much worse on other. Maybe there are some theory people out there who can explain it. Probably some staring at Knuth vol. 3 would help. -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov
kpv@ulysses.att.com (Phong Vo[drew]) (06/24/91)
Somewhere in this thread, Chris Torek proposed as a hash function: > >> hash = 0; > >> for (each character) > >> hash = (hash * 33) + (the character); > >> hash_index = hash & ((some power of two) - 1); > Chris then asked, > ... What *does* that 33 do? > > Maybe there are some theory people out there who can explain it. > Probably some staring at Knuth vol. 3 would help. A good property for a hash function is if you keep feeding it a constant character, it performs as if it's a random number generator. The hash function f(h,c) = 33*h + c is derived from a class of random number generators called linear congruential. At the start of Knuth Vol 2, there is a good discussion of these generators. Let's apply some of the theorems in that section and see what we get. Keep in mind that we are working with random numbers mod 2^x where x is usually 16 or 32. Assuming that c is some fixed odd value, Theorem A guarantees that 33 is good because (33-1)%4 == 0. In the same reasoning, 31 is not good since (31-1)%4 == 2 != 0. Here good means that if you keep feeding c, you'll cycle thru the entire set of values [0,2^x). On the other hand, 33 is not a primitive element for 2^x when x > 3 (Theorem C), so it isn't a good multiplicator if you keep feeding in 0's. For example, 37 is a better value from that point of view. To summarize, a good multiplicator is any number with 101 as their low order 3 bits. At this point, we depart from theory. We typically hash byte strings and we want the bits to mix in the 16-bit or 32-bit registers relatively fast. This suggests that some value larger than 2^8 (but not too large) may do better as a multiplicator. After a little experimentation, here's a pretty decent hash function: hash = 0; for(each byte c) hash = (hash<<8) + (hash<<2) + hash + c; This corresponds to the multiplicator 261 whose bit pattern is 100000101. Try it, you'll like it.
torek@elf.ee.lbl.gov (Chris Torek) (06/24/91)
In an article whose referent is long gone, I described this hash function: for (each character) hash = (hash * 33) + (the character); hash_index = hash & ((some power of two) - 1); and noted: >>Maybe there are some theory people out there who can explain [why 33 >>works well]. In article <15027@ulysses.att.com> kpv@ulysses.att.com (Phong Vo[drew]) writes: >A good property for a hash function is if you keep feeding it >a constant character, it performs as if it's a random number generator. >The hash function f(h,c) = 33*h + c is derived from a class of random >number generators called linear congruential. At the start of Knuth Vol 2, >there is a good discussion of these generators. ... and indeed, if you turn to Knuth vol. 2, chapter 3, you will find all sorts of interesting stuff, such as a proof that the low-order n bits of the usual rand() repeat with period $2^n$. (rand() uses a modulus of either $2^15$ or $2^31$.) >... Assuming that c is some fixed odd value, Theorem A guarantees that >33 is good because (33-1)%4 == 0. ... Here good means that if you keep >feeding c, you'll cycle thru the entire set of values [0,2^x). This is approaching what I was getting at, but is not quite there. Basically it says that 33 is `good' because it is `not bad'. An LCRNG is defined as h = ( a h + c ) mod m (where h is each a value of the n+1 n n variable `hash' in the for loop) (in quote `>' above, $m = 2^x$). With a `bad' multiplier for $a$---and what is `bad' depends on $c$ and $m$---the generator will not produce all $m$ possible values; with a `good' one it will. Intuitively, then, the `bad' one will miss some of the hash buckets entirely; the `good' one will not. But *why* is it true that `A good property is [that] it performs as if it's a [good] random number generator'? This is now `obvious' (from the above result) *if* we feed in constant values of $c$, i.e., if all the strings are made of the same characters, but are different lengths. But we rarely do that---the strings we hash are full of weird junk. How do LCRNGs get in there? Why do the varying values of $c$ not mess things up? (Of course, they do, but not enough to matter. Why not?) >At this point, we depart from theory. We typically hash byte strings ... Actually, I typically hash ASCII text. 33 is the `easiest' `good' multiplier (as defined above) that is >= 26. I have no idea whether this is significant, or merely coincidental. >... This suggests that some value larger than 2^8 (but not too large) >may do better as a multiplicator. ... > hash = 0; > for(each byte c) > hash = (hash<<8) + (hash<<2) + hash + c; I will see if I can get this one run on the same data as the `33 hash'. This is more work than hash = (hash << 5) + hash + c; and distribution improvements may be outweighed by additional hash time (or may not: who knows?). -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (06/25/91)
In article <15027@ulysses.att.com> kpv@ulysses.att.com (Phong Vo[drew]) writes: > A good property for a hash function is if you keep feeding it > a constant character, it performs as if it's a random number generator. No, I don't think so. This is commonly true of good hash functions and commonly false of bad ones, but keep in mind that pseudo-random sequences have to keep working 100, 1000, 1000000 elements later, while simple string hash functions are rarely applied to strings with more than 80 characters. [ as a generator mod 2^n, 37 is better than 33 is better than 31 ] Again, I don't think this is accurate. Each number has a sufficiently long period mod 2^n that you don't have to worry about repeats. > We typically hash byte strings and we want > the bits to mix in the 16-bit or 32-bit registers relatively fast. [ so use a multipler of 261 ] Again, practically any good multiplier works. I think you're worrying about the fact that 31c + d doesn't cover any reasonable range of hash values if c and d are between 0 and 255. That's why, when I discovered the 33 hash function and started using it in my compressors, I started with a hash value of 5381. I think you'll find that this does just as well as a 261 multiplier. ---Dan
kpv@ulysses.att.com (Phong Vo[drew]) (06/26/91)
> Again, practically any good multiplier works. I think you're worrying > about the fact that 31c + d doesn't cover any reasonable range of hash > values if c and d are between 0 and 255. That's why, when I discovered > the 33 hash function and started using it in my compressors, I started > with a hash value of 5381. I think you'll find that this does just as > well as a 261 multiplier. > > ---Dan 261 is just a number that was picked out of a hat that satisfies the conditions outlined in the theorems in Knuth. These conditions are pretty minimal so yes there are lots and lots of numbers that would do just as well. For compressors, if you work with binary files, it isn't infrequent to have strings of 0's. In such a case, you'll want the multiplier to have the nice properties of a RNG. For this reason, 261 type of numbers may be a little better than 33 (in either case, don`t forget to start the hash sum at some odd value!). For everyone's entertainment, I did a simple (and admittedly contrived) test of hashing 1000000 numbers starting at 1000000 into 1000000 buckets. This is done by treating each number which is stored in a word as a string of 4 bytes. With 261, 927300 of these numbers are in their own buckets, the rest are in 36350 buckets each with 2 elements. This is almost as good as a perfect hash function. The result for 33 is much worse. The largest bucket has 64 elements in it and there are 4050 such buckets. The key difference is the 8th bit in 261 which causes the mixing to go a little faster.
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (06/26/91)
In article <15047@ulysses.att.com> kpv@ulysses.att.com (Phong Vo[drew]) writes: > For everyone's entertainment, I did a simple (and admittedly contrived) test > of hashing 1000000 numbers starting at 1000000 into 1000000 buckets. > This is done by treating each number which is stored in a word as a > string of 4 bytes. [ results supposedly showing 261 much better than 33 ] Sorry, but the mod has to be a power of 2. Also, your test is remarkably contrived: we're talking about string hash functions, and typical strings (a) are concentrated on a few character values, not spread evenly over the entire character set; (b) do not all have the same high byte; (c) do not all have the same length. Surely you noticed that a multiplier of 256 will produce perfect hashing in this case. Does that mean you're recommending a multiplier of 256? The profiling statistics I've saved from various compressors form a much more realistic sample. They show 33 as slightly better than random hashing on typical files, 37 as slightly worse. I've never tried 261 or 31, but I'll bet 261 does worse than 33 on text files. ---Dan
evans@syd.dit.CSIRO.AU (Bruce.Evans) (06/26/91)
In article <14583@dog.ee.lbl.gov> torek@elf.ee.lbl.gov (Chris Torek) writes: >>> hash = 0; >>> for (each character) >>> hash = (hash * 33) + (the character); >>> hash_index = hash & ((some power of two) - 1); > >In article <14491.28619071@stjhmc.fidonet.org> >Dave.Harris@f14.n15.z1.fidonet.org (Dave Harris) writes: >>Is the *33 use to keep short sequences has key more random or does it >>really help in the distribution of large string too? > >The third question is the hardest. What *does* that 33 do? I have no >idea. All I know is that I have experimented with `easy' functions I don't think there are any theoretical mysteries behind the 33. 33 = 32 + 1. The 32 is to avoid mixing bits with previous hash bits. 256 would avoid all mixing (with 8-bit chars) but it would throw away too many bits. The 1 is to avoid throwing away bits. Rotating the bits instead of shifting left would probably be a better way to avoid this. The following hash function worked well for me in an assembler. It implements the ideas that hashing all the chars in the string is unnecessary (and maybe even bad if too many bits get shifted out) and that the middle char is more random than leading or trailing chars. In the program this was extracted from, the string length was already known. Avoiding looking at all the chars in the string is not such a good idea when strlen has to do it anyway. Also, this probably does best with a lot of short strings. --- extern unsigned strlen(); /* #include <string.h> */ #define SPTSIZE 1024 extern struct sym_s *spt[SPTSIZE]; #define hconv(ch) ((unsigned char) (ch) - 0x41) /* better form for hashing */ struct sym_s **gethashptr(str) register char *str; { register unsigned hashval; register unsigned length; /* Hash function is a weighted xor of 1 to 4 chars in the string. * This seems to work better than looking at all the chars. * It is important that the function be fast. * The multiplication by MULTIPLIER should compile as a shift. */ #define MULTIPLIER (SPTSIZE / (1 << USEFUL_BITS_IN_ASCII)) #define USEFUL_BITS_IN_ASCII 6 length = strlen(str); if (length <= 3) { if (length <= 2) hashval = hconv(str[-1]) * MULTIPLIER; else hashval = hconv(str[-2]) * MULTIPLIER, hashval ^= hconv(str[-1]); } else hashval = hconv(str[-(length / 2)]) * MULTIPLIER, hashval ^= hconv(str[-2]) << 2, hashval ^= hconv(str[-1]); return spt + (hashval ^ (hconv(str[0]) << 1)) % SPTSIZE; } --- -- Bruce Evans evans@syd.dit.csiro.au
dik@cwi.nl (Dik T. Winter) (06/26/91)
In article <17918.Jun2608.17.5091@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > In article <15047@ulysses.att.com> kpv@ulysses.att.com (Phong Vo[drew]) writes: > > For everyone's entertainment, I did a simple (and admittedly contrived) test > > of hashing 1000000 numbers starting at 1000000 into 1000000 buckets. > > This is done by treating each number which is stored in a word as a > > string of 4 bytes. > > Sorry, but the mod has to be a power of 2. Why? (If you are telling me for speed I'll scream.) > > Surely you noticed that a multiplier of 256 will produce perfect hashing > in this case. Does that mean you're recommending a multiplier of 256? Only on big-endian machines of course :-) > > The profiling statistics I've saved from various compressors form a much > more realistic sample. They show 33 as slightly better than random > hashing on typical files, 37 as slightly worse. I've never tried 261 or > 31, but I'll bet 261 does worse than 33 on text files. > I did some simple tests, hashing all entries of /usr/dict/words, counting how many entries fall in each bucket. I did this with the four multipliers Dan just mentioned. I did this for 16 buckets to 8192 buckets (only powers of two done). I calculated also the standard deviations involved. I will not bore you with all those digits, the result can be stated simply: it does not matter very much what multiplier you use. For each multiplier there is a number of buckets where that multiplier has the smallest standard deviation. So use whatever you like. -- dik t. winter, cwi, amsterdam, nederland dik@cwi.nl
martin@adpplz.UUCP (Martin Golding) (06/27/91)
In <15047@ulysses.att.com> kpv@ulysses.att.com (Phong Vo[drew]) writes: >For everyone's entertainment, I did a simple (and admittedly contrived) test >of hashing 1000000 numbers starting at 1000000 into 1000000 buckets. >This is done by treating each number which is stored in a word as a >string of 4 bytes. With 261, 927300 of these numbers are >in their own buckets, the rest are in 36350 buckets each with 2 elements. >This is almost as good as a perfect hash function. The result for 33 is >much worse. The largest bucket has 64 elements in it and there are 4050 >such buckets. The key difference is the 8th bit in 261 which causes the >mixing to go a little faster. Your test is probably irrelevant, being contiguous sequential numbers. The best hash in this case is for( hash = (i = 0); i < len(numstr); hash = hash*10 + numstring[i++]); hash = hash % numberofbuckets; This will yield the best possible distribution for any number of hash buckets. The proof is left to the reader. The point is not that there is a better hash for sequential numbers, but that the performance of _any_ hash function is highly dependent on your keys; if you any idea of the values or kinds of values to expect you can choose a better function. If you can _control_ the values of your keys you can sometimes get a _much_ better function; viz the numbers above. If all this is old and boring stuff, I apologise for interrupting you all just to look like an idiot (flame me by email), and I now return you to your regularly scheduled newsgroup. Martin Golding | sync, sync, sync, sank ... sunk: Dod #0236 | He who steals my code steals trash. A poor old decrepit Pick programmer. Sympathize at: {mcspdx,pdxgate}!adpplz!martin or martin@adpplz.uucp
martin@adpplz.UUCP (Martin Golding) (06/27/91)
In <843@adpplz.UUCP> martin@adpplz.UUCP (Martin Golding) writes:
A bunch of nonsense, unless you realize I misread the previous post,
and was thinking of a string of ascii digits. Then it all becomes
clear, and I stand by everything I said, all of which was irrelevant.
Sorry.
Martin Golding | sync, sync, sync, sank ... sunk:
Dod #0236 | He who steals my code steals trash.
A poor old decrepit Pick programmer. Sympathize at:
{mcspdx,pdxgate}!adpplz!martin or martin@adpplz.uucptorek@elf.ee.lbl.gov (Chris Torek) (06/27/91)
>In article <14583@dog.ee.lbl.gov> I wrote: >>The [`why'] question is the hardest. What *does* that 33 do? I have no >>idea. ... In article <1991Jun26.112724.20539@syd.dit.CSIRO.AU> evans@syd.dit.CSIRO.AU (Bruce.Evans) writes: >I don't think there are any theoretical mysteries behind the 33. 33 = 32 + 1. >The 32 is to avoid mixing bits with previous hash bits. 256 would avoid all >mixing (with 8-bit chars) but it would throw away too many bits. The 1 is to >avoid throwing away bits. This answer just does not hold up: if this were the case, 65, 129, etc., should work as well as 33. They do not. Why not? >The following hash function worked well for me in an assembler. ... > length = strlen(str); ... hashval = hconv(str[-1]) * MULTIPLIER; At this point, str[-1] is unlikely to exist. The function seems to expect a pointer to the last character, rather than the first. -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov