部分语言hash算法

PHP 7哈希算法times33(Zend/zend_string.h):

/*
* DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
*
* This is Daniel J. Bernstein's popular `times 33' hash function as
* posted by him years ago on comp.lang.c. It basically uses a function
* like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
* known hash functions for strings. Because it is both computed very
* fast and distributes very well.
*
* The magic of number 33, i.e. why it works better than many other
* constants, prime or not, has never been adequately explained by
* anyone. So I try an explanation: if one experimentally tests all
* multipliers between 1 and 256 (as RSE did now) one detects that even
* numbers are not useable at all. The remaining 128 odd numbers
* (except for the number 1) work more or less all equally well. They
* all distribute in an acceptable way and this way fill a hash table
* with an average percent of approx. 86%.
*
* If one compares the Chi^2 values of the variants, the number 33 not
* even has the best value. But the number 33 and a few other equally
* good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
* advantage to the remaining numbers in the large set of possible
* multipliers: their multiply operation can be replaced by a faster
* operation based on just one shift plus either a single addition
* or subtraction operation. And because a hash function has to both
* distribute good _and_ has to be very fast to compute, those few
* numbers should be preferred and seems to be the reason why Daniel J.
* Bernstein also preferred it.
*
*
* -- Ralf S. Engelschall <rse@engelschall.com>
*/

static zend_always_inline zend_ulong zend_inline_hash_func(const char *str, size_t len)
{
        zend_ulong hash = Z_UL(5381);

        /* variant with the hash unrolled eight times */
        for (; len >= 8; len -= 8) {
                hash = ((hash << 5) + hash) + *str++;
                hash = ((hash << 5) + hash) + *str++;
                hash = ((hash << 5) + hash) + *str++;
                hash = ((hash << 5) + hash) + *str++;
                hash = ((hash << 5) + hash) + *str++;
                hash = ((hash << 5) + hash) + *str++;
                hash = ((hash << 5) + hash) + *str++;
                hash = ((hash << 5) + hash) + *str++;
        }
        switch (len) {
                case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
                case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
                case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
                case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
                case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
                case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
                case 1: hash = ((hash << 5) + hash) + *str++; break;
                case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
        }

        /* Hash value can't be zero, so we always set the high bit */
#if SIZEOF_ZEND_LONG == 8
        return hash | Z_UL(0x8000000000000000);
#elif SIZEOF_ZEND_LONG == 4
        return hash | Z_UL(0x80000000);
#else
# error "Unknown SIZEOF_ZEND_LONG"
#endif
}

Apache和Perl 哈希算法:

hashing function used in Perl 5.005:
# Return the hashed value of a string: $hash = perlhash("key")
# (Defined by the PERL_HASH macro in hv.h)
sub perlhash
{
    $hash = 0;
    foreach (split //, shift) {
        $hash = $hash*33 + ord($_);
    }
    return $hash;
}

 

Java native哈希算法:

key.hashCode()

 

Java HashMap 哈希算法:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

参考资料:https://www.ibm.com/developerworks/cn/java/j-lo-hash/

Leave a Comment