几种流行的hash函数

Comments: No Comments
Published on: 2013 年 03 月 13 日


A comprehensive collection of hash functions, a hash visualiser and some test results [see Mckenzie et al. Selecting a Hashing Algorithm, SP&E 20(2):209-224, Feb 1990] will be available someday. If you just want to have a good hash function, and cannot wait, djb2 is one of the best string hash functions i know. it has excellent distribution and speed on many different sets of keys and table sizes. you are not likely to do better with one of the "well known" functions such as PJW, K&R[1], etc. Also see tpop pp. 126 for graphing hash functions.

djb2

this algorithm (k=33) was first reported by dan bernstein many years ago in comp.lang.c. another version of this algorithm (now favored by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.

1
2
3
4
5
6
7
8
9
10
11
    unsigned long
    hash(unsigned char *str)
    {
        unsigned long hash = 5381;
        int c;
 
        while (c = *str++)
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
 
        return hash;
    }

sdbm

this algorithm was created for sdbm (a public-domain reimplementation of ndbm) database library. it was found to do well in scrambling bits, causing better distribution of the keys and fewer splits. it also happens to be a good general hashing function with good distribution. the actual function is hash(i) = hash(i - 1) * 65599 + str[i]; what is included below is the faster version used in gawk. [there is even a faster, duff-device version] the magic constant 65599 was picked out of thin air while experimenting with different constants, and turns out to be a prime. this is one of the algorithms used in berkeley db (see sleepycat) and elsewhere.

1
2
3
4
5
6
7
8
9
10
11
12
    static unsigned long
    sdbm(str)
    unsigned char *str;
    {
        unsigned long hash = 0;
        int c;
 
        while (c = *str++)
            hash = c + (hash << 6) + (hash << 16) - hash;
 
        return hash;
    }

lose lose

This hash function appeared in K&R (1st ed) but at least the reader was warned: "This is not the best possible algorithm, but it has the merit of extreme simplicity." This is an understatement; It is a terrible hashing algorithm, and it could have been much better without sacrificing its "extreme simplicity." [see the second edition!] Many C programmers use this function without actually testing it, or checking something like Knuth's Sorting and Searching, so it stuck. It is now found mixed with otherwise respectable code, eg. cnews. sigh. [see also: tpop]

1
2
3
4
5
6
7
8
9
10
11
    unsigned long
    hash(unsigned char *str)
    {
	unsigned int hash = 0;
	int c;
 
	while (c = *str++)
	    hash += c;
 
	return hash;
    }

上述三种 source : www.cse.yorku.ca

fast-hash

Basically, Xorshift(http://www.jstatsoft.org/v08/i14/paper) and multiplication are two main methods that mix the bits inside an integer. Often they are interlaced in the mix function as to achieve better non-linearity. It should be noted that both Xorshift and multiplication (multiplied by an odd integer) are invertible in the residue field of power-of-two. This guarantees that no information will get lost after mixing the bits.

The mix function of FastHash consists of two Xorshifts and one multiplication:

#define mix_fasthash(h) ({              \
        (h) ^= (h) >> 23;               \
        (h) *= 0x2127599bf4325c37ULL;   \
        (h) ^= (h) >> 47; })

Whereas MurmurHash2's mix function has two multiplications and one Xorshift:

#define mix_murmur2(h) ({               \
        (h) *= 0xc6a4a7935bd1e995ULL;   \
        (h) ^= (h) >> 47;               \
        (h) *= 0xc6a4a7935bd1e995ULL; })

Generally, multiplication(tens of clocks) is much more expensive than Xorshift (several clocks) on almost all platforms, thus FastHash should be more efficient than MurmurHash2, especially when the input is large. Besides, the mix function of murmurhash2 is slightly flawed since it produces bit biased values according to the SMHasher results.

fash-hash source : http://code.google.com/p/fast-hash/

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期一, 2017 年 11 月 20 日