apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From f...@apache.org
Subject cvs commit: apr/tables apr_hash.c
Date Thu, 22 Mar 2001 17:35:11 GMT
fanf        01/03/22 09:35:11

  Modified:    tables   apr_hash.c
  Log:
  better hash function citation
  
  Revision  Changes    Path
  1.18      +13 -8     apr/tables/apr_hash.c
  
  Index: apr_hash.c
  ===================================================================
  RCS file: /home/cvs/apr/tables/apr_hash.c,v
  retrieving revision 1.17
  retrieving revision 1.18
  diff -u -u -r1.17 -r1.18
  --- apr_hash.c	2001/03/10 00:07:09	1.17
  +++ apr_hash.c	2001/03/22 17:35:08	1.18
  @@ -222,12 +222,18 @@
   	klen = strlen(key);
   
       /*
  -     * This is Daniel J. Bernstein's popular `times 33' hash function
  -     * as posted by him years ago on comp.lang.c and used by perl.
  -     * This is one of the best known hash functions for strings
  -     * because it is both computed very fast and distributes very
  -     * well.
  +     * This is the popular `times 33' hash algorithm which is used by
  +     * perl and also appears in Berkeley DB. This is one of the best
  +     * known hash functions for strings because it is both computed
  +     * very fast and distributes very well.
        *
  +     * The originator may be Dan Bernstein but the code in Berkeley DB
  +     * cites Chris Torek as the source. The best citation I have found
  +     * is "Chris Torek, Hash function for text in C, Usenet message
  +     * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich
  +     * Salz's USENIX 1992 paper about INN which can be found at
  +     * <http://citeseer.nj.nec.com/salz92internetnews.html>.
  +     *
        * 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
  @@ -248,9 +254,8 @@
        * 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.
  +     * be very fast to compute, those few numbers should be preferred.
  +     *
        *                  -- Ralf S. Engelschall <rse@engelschall.com>
        */
       hash = 0;
  
  
  

Mime
View raw message