散列函数time33学习随笔

年底项目任务中,忙里偷闲更新一篇.
众所周知,PHP拥有一个万能的数据结构--Array.这货实在是太易用太强大了,导致PHP程序员在程序员界都混不下去了.使用PHP的Array几乎可以实现在大学数据结构课本里出现的所有数据结构.
实际上在PHP内部,Array是由Zend引擎中的Zend HashTable实现的.其实不光是Array,包括各种常量,变量,函数体,class等都是用它来组织的.
在PHP的源代码里找到zend_hash.c后不难发现,zend hashtable包含两个结构体,分别是bucket

typedef struct bucket {
ulong h;       /* Used for numeric indexing */
uint nKeyLength;     /* key 长度 */
void *pData;      /* 指向Bucket中保存的数据的指针 */
void *pDataPtr;     /* 指针数据 */
struct bucket *pListNext;   /* 指向HashTable桶列中下一个元素 */
struct bucket *pListLast;    /* 指向HashTable桶列中前一个元素 */
struct bucket *pNext;    /* 指向具有同一个hash值的桶列的后一个元素 */
struct bucket *pLast;    /* 指向具有同一个hash值的桶列的前一个元素 */
char arKey[1];      /* 必须是最后一个成员,key名称*/
} Bucket;

以及_hashtable

typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;
Bucket *pListTail; 
Bucket **arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

这篇博文的重点并不在这里,相信每一个从事PHP行业的职业PHPer都对这些烂熟于心了.今天主要学习一下PHP使用的DJBX33A哈希算法
DJBX33A (Daniel J. Bernstein, Times 33 with Addition)普遍叫做time33算法,这个算法被广泛运用与多个软件项目,它是已知的最好的哈希算法之一,在处理以字符串为键值的哈希时,有着极快的计算效率和很好哈希分布.
如果用映射关系来表达的话就是如下形式,很简单:

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

以下是PHP内部使用的time33版本:

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; 
} 

用位运算代替乘法,效率更高.待续..