| 关于Hashtable collisions 数据的基本组织可以分为三种形式: 结构体(或对象) 数组 链表 其他任何的数据组织形式都可以看作是这三种数据组织形式的组合变体。就存取数据的 速度而言,数组要远远优于链表，因为数组可以在O(1)的时间复杂内完成指定位置元素的读 写操作。所以在理想状态，如果一个数组足够长，且存在一个函数可以将每一个key映射到 唯一的一个数组下标，那么我们就可以很完美的解决问题。但往往资源都是有限的，我们没 有那么大的空间，也不能设计一个无比负责的映射算法保证每一个key对应到一个唯一的数 组下标。 hash table便是为解决这类问题而存在的,hash操作其本质上就是将一个数据映射成另 一个数据，通常情况下原数据的长度比hash后的数据容量大。这种映射的关系我们叫做哈希 函数。一般情况下 哈希函数的输入可能的总数要远远多于哈希值所能表示的总数，所以就 有可能两个不同的输入对应同一个哈希值，比如著名的md5碰撞。 解决冲突的方式主要分两类： 开放定址法(Open addressing)：这种方法就是在计算一个key的哈希的时候，发现目标 地址已经有值了，即发生冲突了，这个时候通过相应的函数在此地址后面的地址去找，直到 没有冲突为止。这个方法常用的有线性探测，二次探测，再哈希。 链接法(Separate chaining)：链接法是通过数组和链表组合而成的。当发生冲突的时 候只要将其加到对应的链表中即可。 PHP使用链接法解决冲突，如果攻击者能够人为的制造大量hash冲突，将PHP底层保存 POST数据的Hash表退化成链表，造成性能的急剧下降。 PHP的Hash函数 PHP的Hash函数采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition)，代码可以在这里查 看：http://lxr.php.net/xref/PHP_5_2/Zend/zend_hash.h#zend_inline_hash_func -----------------code------------------------- static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength) 255 { 256 register ulong hash = 5381; 257 258 /* variant with the hash unrolled eight times */ 259 for (; nKeyLength >= 8; nKeyLength -= 8) { 260 hash = ((hash << 5) + hash) + *arKey++; 261 hash = ((hash << 5) + hash) + *arKey++; 262 hash = ((hash << 5) + hash) + *arKey++; 263 hash = ((hash << 5) + hash) + *arKey++; 264 hash = ((hash << 5) + hash) + *arKey++; 265 hash = ((hash << 5) + hash) + *arKey++; 266 hash = ((hash << 5) + hash) + *arKey++; 267 hash = ((hash << 5) + hash) + *arKey++; 268 } 269 switch (nKeyLength) { 270 case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ 271 case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ 272 case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ 273 case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ 274 case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ 275 case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ 276 case 1: hash = ((hash << 5) + hash) + *arKey++; break; 277 case 0: break; 278 EMPTY_SWITCH_DEFAULT_CASE() 279 } 280 return hash; 281 } ---------------------- 核心算法是 hash = ((hash << 5) + hash) + *arKey++; |
