发一下牢骚和主题无关：
一、哈希表义定
哈希表(或散表列)，是将键名key按指定的散列函数HASH经过HASH(key)算计后映射到表中一个录记，而这个数组就是哈希表。
这里的HASH指意任的函数，例如MD5、CRC32、SHA1或你自义定的函数实现。
二、HashTable性能
HashTable是一种找查性能极高的数据构结，在很多语言部内都实现了HashTable。
幻想况情下HashTable的性能是O(1)的，性能耗消重要会合在散列函数HASH(key)，通过HASH(key)直接定位到表中的录记。
而在现实况情下经常会生发key1 != key2，但HASH(key1) = HASH(key2)，这类况情即Hash撞碰问题，撞碰的率概越低HashTable的性能越好。当然Hash算法过太庞杂也会影响HashTable性能。
三、解理PHP的哈希表实现
在PHP内核也一样实现了HashTable并泛广应用，括包线程安全、全局变量、资源管理等基本上全部的地方都能看到它的身影。
不仅如此，在PHP本脚中数组（PHP的数组本质就是HashTable）也是被泛广用使的，例如数组式形的配置文件、数据库的查询结果等，可以说是无处不在。
那么既然PHP的数组用使率这么高，部内是如何实现的？它如何处理hash撞碰及实现平均分布的？PHP本脚用使数组该应注意哪些？
首先通过图解，大致解理PHP HashTable的实现。
面上通过源码来一步一步分析。
1）HashTable在PHP内核的实现
PHP实现HashTable重要是通过两个数据构结Bucket(桶)和HashTable。
从PHP本脚端来看，HashTable相当于Array对象，而Bucket相当于Array对象里的某个素元。对于多维数组现实就是HashTable的某个Bucket里存储着另一个HashTable。
HashTable构结：
typedef struct _hashtable { uint nTableSize; //表长度，并非素元个数 uint nTableMask;//表的码掩，一直等于nTableSize-1 uint nNumOfElements;//存储的素元个数 ulong nNextFreeElement;//向指下一个空的素元位置 Bucket *pInternalPointer;//foreach循环时，用来录记当前遍历到的素元位置 Bucket *pListHead; Bucket *pListTail; Bucket **arBuckets;//存储的素元数组 dtor_func_t pDestructor;//析构函数 zend_bool persistent;//否是久持保存。从这可以发明，PHP数组是可以实现久持保存在内存中的，而无需每次请求都从新加载。 unsigned char nApplyCount; zend_bool bApplyProtection;} HashTable;
Bucket构结：
typedef struct bucket { ulong h; //数组索引 uint nKeyLength; //字符串索引的长度 void *pData; //现实数据的存储地址 void *pDataPtr; //引入的数据存储地址 struct bucket *pListNext; struct bucket *pListLast; struct bucket *pNext; //单向表链的下一个素元的地址 struct bucket *pLast;//单向表链的最后一个素元地址 char arKey[1]; /* Must be last element */} Bucket;
PHP内核哈希表的散列函数很简略，直接用使 （HashTable->nTableSize & HashTable->nTableMask）的结果作为散列函数的实现。这样做的的目可能也是为了下降Hash算法的庞杂度和高提性能。
1.1)在PHP中初始化一个空数组时，对应内核中是如何建创HashTable的
$array = new Array();
//省略了分部码代，提出重要的逻辑ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC){ uint i = 3; Bucket **tmp; SET_INCONSISTENT(HT_OK); if (nSize >= 0x80000000) {//数组的最大长度是十进制2147483648 /* prevent overflow */ ht->nTableSize = 0x80000000; } else { //数组的长度是向2的整次幂取圆整 //例如数组的里有10个素元，那么现实被配分的HashTable长度是16。100个素元，则被配分128的长度 //HashTable的小最长度是8，而非0。因为默许是将1向移右3位，1<<3=8 while ((1U << i) < nSize) { i++; } ht->nTableSize = 1 << i; } ht->nTableMask = ht->nTableSize - 1; .... return SUCCESS;} 从上看出，即使在PHP中初始化一个空数组或足不8个素元的数组，都会被建创8个长度的HashTable。一样建创100个素元的数组，也会被配分128长度的HashTable。顺次类推。
1.2）内对核PHP添加数字索引的处理方法
PHP数组中，键名可为以数字或字符串类型。而在内核中只允许数字索引，对于字符串索引，内核采用了time33算法将字符串转换为整型。具体的实现面上会具体明说。
$array[0] = "hello hashtable";
每日一道理 闷热的天，蝉儿耐不住寂寞地不停在鸣叫，我孤单一人，寂静的身旁没有一个知音，想疯狂地听摇滚乐，听歇斯底里的歌声，那只为逃避无人的世界里那浓烈的孤单气息。一个人是清冷，两个人便是精彩，于是，莫名的冲动让我格外想念旧日的好友，怀念过去的日子，尽管不够现实的遐想追回不了曾经一切，但却希望思绪可以飞扬于闭上双目后的世界中，印有微笑，印有舞动的身姿，翩翩起舞……
//省略了分部码代，提出重要的逻辑ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC){ ulong h; uint nIndex; Bucket *p; //省略了分部码代，提出重要的逻辑 nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex]; p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent); if (!p) { return FAILURE; } p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */ p->h = h; INIT_DATA(ht, p, pData, nDataSize); if (pDest) { *pDest = p->pData; } ht->arBuckets[nIndex] = p; ht->nNumOfElements++; return SUCCESS;} 上述也说了明，内核中哈希表的散列函数就是简略的h & ht->nTableMask，其中h代表PHP中置设的索引号，nTableMask等于哈希表配分的长度-1。
1.3) 内对核PHP中字符串索引的处理方法
$array['index'] = "hello hashtable";
与数字索引比相，只是多了一步将字符串转换为整型。用到的算法是time33
面上贴出了算法的实现，就是对字符串的每一个字符转换为ASCII码乘上33并且相加失掉的结果。
面上贴出了算法的实现，就是对字符串的每一个字符转换为ASCII码乘上33并且相加失掉的结果。
static inline ulong zend_inline_hash_func(const 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; } return hash;}zend_hash.c//面上省略了分部码代，提出重要的逻辑ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC){ ulong h; uint nIndex; Bucket *p; h = zend_inline_hash_func(arKey, nKeyLength); //字符串转整型 nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex]; p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent); if (!p) { return FAILURE; } p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */ p->h = h; INIT_DATA(ht, p, pData, nDataSize); if (pDest) { *pDest = p->pData; } ht->arBuckets[nIndex] = p; ht->nNumOfElements++; return SUCCESS;}
2) 内核中如何实现平均分布和处理hash撞碰问题的
2.1) 平均分布平均分布是指，将要需存储的各个素元平均的分布到HashTable中。
而责负算计具体分布到表中哪个位置的函数就是散列函数做的事件，所以散列函数的实现直接关系到平均分布的效率。
面上也提到了PHP内核中用了简略的方法实现：h & ht->nTableMask;
2.1)Hash撞碰
Hash撞碰是指，经过Hash算法后失掉的值会现出key1 != key2, 但Hash(key1)却等于Hash(key2)的况情，这就是撞碰问题。在PHP内核来看，就是会现出key1 != key2, 但key1 & ht->nTableMask却等于 key2 & ht->nTableMask的况情。
PHP内核用使单向表链的方法来存储突冲的数据。即Bucket本身也是一个单向表链，当生发突冲时，会将数据按序顺向后排列。
如果不生发突冲，Bucket等于长度为1的的单向表链。
ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData){ ulong h; uint nIndex; Bucket *p; IS_CONSISTENT(ht); h = zend_inline_hash_func(arKey, nKeyLength); nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex]; //找到素元时，并非当即返回，而是要再比对h与nKeyLength，止防hash撞碰。此段码代就是遍历表链,直到表链尾部。 while (p != NULL) { if ((p->h == h) && (p->nKeyLength == nKeyLength)) { if (!memcmp(p->arKey, arKey, nKeyLength)) { *pData = p->pData; return SUCCESS; } } p = p->pNext; } return FAILURE;} 以后，将会写一篇关于用利Hash算法，停止分布式存储的分析。
原文地址：
文章结束给大家分享下程序员的一些笑话语录： 看到有人回帖“不顶不是中国人”，他的本意是想让帖子沉了。