The Hash Algorithm in PHP中文EN

Calling the Hash Table the core of PHP is no exaggeration.
Arrays, associative arrays, object properties, function tables, symbol tables — in PHP all of them use a HashTable as their container.
PHP's HashTable resolves collisions by chaining; that needs no further explanation. What I want to focus on today is PHP's hash algorithm itself, and some of the thinking it reveals.
PHP uses DJBX33A (Daniel J. Bernstein, Times 33 with Addition), currently the most widespread hash of its kind. It is used across many software projects — Apache, Perl, Berkeley DB, and others. For strings it is the best hash function known to date, because it is both extremely fast and distributes very well (few collisions, even spread).
The core idea of the algorithm is:

	hash(i) = hash(i-1) * 33 + str[i]

In zend_hash.h we can find PHP's version of this algorithm:

static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
{
    register ulong hash = 5381;
    /* variant with the hash unrolled eight times */
    for (; nKeyLength >= 8; nKeyLength -= 8) {
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
    }
    switch (nKeyLength) {
        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *arKey++; break;
        case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
    }
    return hash;
}

Compared with the classic Times 33 algorithm used directly in Apache and 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;
  }

we can spot several subtle differences in PHP's hash algorithm.
First, and most notably, PHP does not multiply by 33 directly; instead it uses:

  hash << 5 + hash

which is of course faster than a multiplication.
Then there is the unrolling, which deserves special attention. A few days ago I read an article about Discuz's caching mechanism; one point was that Discuz applies different caching strategies depending on a thread's popularity and on user habits, caching only the first page of a thread (because few people actually page through a thread).
PHP applies a similar idea: it optimizes for character indexes of eight or fewer, unrolling in units of eight to improve efficiency. This, too, is a very fine-grained, very carefully considered detail.
There is also the use of inline and register variables — you can see that PHP's developers put a great deal of effort into optimizing the hash.
Finally, the initial hash value is set to 5381. Compared with the times algorithm in Apache and the hash algorithm in Perl (both of which start the hash at 0), why 5381? I don't know the exact reason, but I did find some properties of 5381:

Magic Constant 5381:
  1. odd number
  2. prime number
  3. deficient number
  4. 001/010/100/000/101 b

Seeing these, I have reason to believe this choice of initial value provides better distribution.
As for why Times 33 rather than times some other number, the comments on PHP's hash algorithm say something about it too. Hopefully it's useful to anyone interested:

  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>