映射函数

2.2.2 映射函数

映射函数(即:散列函数)是散列表的关键部分,它将key与value建立映射关系,一般映射函数可以根据key的哈希值与Bucket数组大小取模得到,即key->h % ht->nTableSize,但是PHP却不是这么做的:

nIndex = key->h | ht->nTableMask;

显然位运算要比取模更快。

nTableMasknTableSize的负数,即:nTableMask = -nTableSize,因为nTableSize等于2^n,所以nTableMask二进制位右侧全部为0,也就保证了nIndex落在数组索引的范围之内(|nIndex| <= nTableSize):

11111111 11111111 11111111 11111000   -8
11111111 11111111 11111111 11110000   -16
11111111 11111111 11111111 11100000   -32
11111111 11111111 11111111 11000000   -64
11111111 11111111 11111111 10000000   -128
联系我们

邮箱 626512443@qq.com
电话 18611320371(微信)
QQ群 235681453

Copyright © 2015-2024

备案号:京ICP备15003423号-3