Re: [mu ComputerScience] hash functions

From: Tom Poindexter (tpoindex@nyx.net)
Date: Sat Mar 18 2000 - 21:02:35 CET


On Sat, Mar 18, 2000 at 06:10:23PM +0100, Michele Andreoli wrote:
>
> I'm interested to hash algoritms and so on. Please, anyone know
> an URL suitable to this kind of lecture?

I don't know of a single page, but you can find many by searching Google,
Altavista, etc. Here are a few:

http://www.ddj.com/articles/1996/9604/9604b/9604b.htm
http://burtleburtle.net/bob/hash/perfect.html
http://www.ics.hawaii.edu/~richardy/project/hash/introduction.html

There's also quite a bit of discussion of hashes in crypto research,
notable, SHA (secure hash algorithm) and MD5. Note that my Tcl Add-on
floppy for muLinux has an implementation of MD5.

I also like this comment from the Tcl source code (tclHash.c):
    /*
     * I tried a zillion different hash functions and asked many other
     * people for advice. Many people had their own favorite functions,
     * all different, but no-one had much idea why they were good ones.
     * I chose the one below (multiply by 9 and add new character)
     * because of the following reasons:
     *
     * 1. Multiplying by 10 is perfect for keys that are decimal strings,
     * and multiplying by 9 is just about as good.
     * 2. Times-9 is (shift-left-3) plus (old). This means that each
     * character's bits hang around in the low-order bits of the
     * hash value for ever, plus they spread fairly rapidly up to
     * the high-order bits to fill out the hash value. This seems
     * works well both for decimal and non-decimal strings.
     */

and the actual code is:

static unsigned int
HashString(string)
    register CONST char *string;/* String from which to compute hash value. */
{
    register unsigned int result;
    register int c;
    result = 0;
    while (1) {
        c = *string;
        string++;
        if (c == 0) {
            break;
        }
        result += (result<<3) + c;
    }
    return result;
}

-- 
Tom Poindexter
tpoindex@nyx.net
http://www.nyx.net/~tpoindex/
---------------------------------------------------------------------
To unsubscribe, e-mail: mulinux-unsubscribe@sunsite.auc.dk
For additional commands, e-mail: mulinux-help@sunsite.auc.dk


This archive was generated by hypermail 2.1.6 : Sat Feb 08 2003 - 15:27:13 CET