tim33

php,apache,perl,bsddb 는 모두 time 33 해시 를 사용 합 니 다.
가장 쉬 운 버 전.
    uint32_t time33(char const *str, int len)     {         uint32_t  hash = 0;         for (int i = 0; i < len; i++) {             hash = hash *33 + (unsigned long) str[i];         }         return hash;     }
이 버 전 은 time 33 의 알고리즘 사고방식 을 가장 잘 나 타 낼 수 있어 서 매우 간단 하 다.
 
곱셈 조작 을 비트 조작 으로 바꾸다        unsigned long time33(char const *str, int len)
    {
        unsigned long  hash = 0;
        for (int i = 0; i < len; i++) {
            hash = ((hash <<5) + hash) + (unsigned long) str[i];
        }
        return hash;
    }
59 글자 1000 0000 회 실행(gcc 는 최 적 화 를 열지 않 았 습 니 다.최 적 화 된 두 함수 의 실제 코드 가 같 기 때 문 입 니 다)
첫 번 째:
real    0m4.389s user    0m4.388s sys     0m0.000s
두 번 째:
real    0m4.137s user    0m4.120s sys     0m0.000s
gcc–O2 최적화 후
real    0m1.367s user    0m1.360s sys     0m0.000s
 
php 버 전
inline unsigned time33(char const*str, int len) {      unsigned long hash = 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;     }     return hash; }
59 글자,1000 0000 회
real    0m1.088s user    0m1.068s sys     0m0.000s
속도 향상 은 주로 순환 전개 에 있 습 니 다.짧 은 문자 에 대해 서 는 뚜렷 하지 않 습 니 다.
php 버 전의 hash 초기 값 은 5381 입 니 다.
Magic Constant 5381:
  1. odd number
  2. prime number
  3. deficient number
  4. 001/010/100/000/101 b
아파 치 버 전
unsigned long time33(char const  *str, int *len) {     unsigned long hash = 0;
    const char *p=str;     if (*len<=0) {         for(p = str; *p; p++) {             hash = hash * 33 + *p;         }         *len = p - str;     }     else {         int i = *len;         for (p = str;i; i--, p++) {             hash = hash * 33 + *p;         }     }     return hash; }
테스트 결과
real    0m1.418s user    0m1.412s sys     0m0.004s
 
종합 적 으로 나의 개선 버 전
#define likely(x) __builtin_expect((x),1) #define unlikely(x) __builtin_expect((x),0)     //php 버 전    unsigned long time33(char const *str, int len=-1)     {         unsigned long hash = 5381;         /* variant with the hash unrolled eight times */         char const *p = str;         if (unlikely(len<0)) {                 for(; *p; p++) {                     hash = hash * 33 + *p;                 }                 return hash;         }
#define TIME33_HASH_MIXED_CH()  hash = ((hash<<5)+hash) + *p++         for (; len >= 8; len -= 8) {             TIME33_HASH_MIXED_CH(); //1             TIME33_HASH_MIXED_CH(); //2             TIME33_HASH_MIXED_CH(); //3             TIME33_HASH_MIXED_CH(); //4             TIME33_HASH_MIXED_CH(); //5             TIME33_HASH_MIXED_CH(); //6             TIME33_HASH_MIXED_CH(); //7             TIME33_HASH_MIXED_CH(); //8        }        switch (len) {            case 7: TIME33_HASH_MIXED_CH(); /* fallthrough... */            case 6: TIME33_HASH_MIXED_CH(); /* fallthrough... */            case 5: TIME33_HASH_MIXED_CH(); /* fallthrough... */            case 4: TIME33_HASH_MIXED_CH(); /* fallthrough... */            case 3: TIME33_HASH_MIXED_CH(); /* fallthrough... */            case 2: TIME33_HASH_MIXED_CH(); /* fallthrough... */            case 1: TIME33_HASH_MIXED_CH(); break;            case 0: break;        }        return hash;    }
#undef TIME33_HASH_MIXED_CH
테스트 결과
real    0m1.072s user    0m1.064s sys     0m0.000s
테스트 해 봤 는데 중 복 률 은 1/2000 입 니 다.
 
왜 33 의 배수 입 니까?

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 [email protected]

기타 배수
Ngix 는 time 31 을 사용 합 니 다.
Tokyo Cabinet 는 time 37 을 사용 합 니 다.
Bob 은 그의 글 에서 소문 자 영어 어 휘 는 33 에 적합 하고 대소 문 자 를 섞 어 65 를 사용한다 고 말 했다.time 33 은 영어 어휘 hash 에 적합 합 니 다.