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;
nTableSize字段用于标示哈希表的容量,哈希表的初始容量最小为8。首先看看哈希表的初始化函数:
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;
//...
if (nSize >= 0x80000000) {
/* prevent overflow */
ht->nTableSize = 0x80000000;
} else {
while ((1U < i++;
}
ht->nTableSize = 1 < }
// ...
ht->nTableMask = ht->nTableSize - 1;
/* Uses ecalloc() so that Bucket* == NULL */
if (persistent) {
tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
if (!tmp) {
return FAILURE;
}
ht->arBuckets = tmp;
} else {
tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
if (tmp) {
ht->arBuckets = tmp;
}
}
return SUCCESS;
}
例如如果设置初始大小为10,则上面的算法将会将大小调整为16。也就是始终将大小调整为接近初始大小的 2的整数次方。
为什么会做这样的调整呢?我们先看看HashTable将哈希值映射到槽位的方法,上一小节我们使用了取模的方式来将哈希值 映射到槽位,例如大小为8的哈希表,哈希值为100, 则映射的槽位索引为: 100
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
从上面的_zend_hash_init()函数中可知,ht->nTableMask的大小为ht->nTableSize -1。 这里使用&操作而不是使用取模,这是因为是相对来说取模操作的消耗和按位与的操作大很多。
mask的作用就是将哈希值映射到槽位所能存储的索引范围内。 例如:某个key的索引值是21, 哈希表的大小为8,则mask为7,则求与时的二进制表示为: 10101 & 111 = 101 也就是十进制的5。 因为2的整数次方-1的二进制比较特殊:后面N位的值都是1,这样比较容易能将值进行映射, 如果是普通数字进行了二进制与之后会影响哈希值的结果。那么哈希函数计算的值的平均分布就可能出现影响。
设置好哈希表大小之后就需要为哈希表申请存储数据的空间了,如上面初始化的代码, 根据是否需要持久保存而调用了不同的内存申请方法。如前面PHP生命周期里介绍的,是否需要持久保存体现在:持久内容能在多个请求之间访问,而非持久存储是会在请求结束时释放占用的空间。 具体内容将在内存管理章节中进行介绍。
HashTable中的nNumOfElements字段很好理解,每插入一个元素或者unset删掉元素时会更新这个字段。 这样在进行count()函数统计数组元素个数时就能快速的返回。
nNextFreeElement字段非常有用。先看一段PHP代码:
$a = array(10 => 'Hello');
$a[] = 'TIPI';
var_dump($a);
array(2) {
[10]=>
string(5) "Hello"
[11]=>
string(5) "TIPI"
}
PHP中可以不指定索引值向数组中添加元素,这时将默认使用数字作为索引, 和C语言中的枚举类似, 而这个元素的索引到底是多少就由nNextFreeElement字段决定了。 如果数组中存在了数字key,则会默认使用最新使用的key + 1,例如上例中已经存在了10作为key的元素, 这样新插入的默认索引就为11了。
数据容器:槽位
下面看看保存哈希表数据的槽位数据结构体:
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];
} Bucket;
如上面各字段的注释。h字段保存哈希表key哈希后的值。这里保存的哈希值而不是在哈希表中的索引值, 这是因为索引值和哈希表的容量有直接关系,如果哈希表扩容了,那么这些索引还得重新进行哈希在进行索引映射, 这也是一种优化手段。 在PHP中可以使用字符串或者数字作为数组的索引。 数字索引直接就可以作为哈希表的索引,数字也无需进行哈希处理。h字段后面的nKeyLength字段是作为key长度的标示, 如果索引是数字的话,则nKeyLength为0。在PHP数组中如果索引字符串可以被转换成数字也会被转换成数字索引。 所以在PHP中例如'10','11'这类的字符索引和数字索引10, 11没有区别。
上面结构体的最后一个字段用来保存key的字符串,而这个字段却申明为只有一个字符的数组, 其实这里是一种长见的变长结构体,主要的目的是增加灵活性。 以下为哈希表插入新元素时申请空间的代码
p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
return FAILURE;
}
memcpy(p->arKey, arKey, nKeyLength);
如代码,申请的空间大小加上了字符串key的长度,然后把key拷贝到新申请的空间里。 在后面比如需要进行hash查找的时候就需要对比key这样就可以通过对比p->arKey和查找的key是否一样来进行数据的 查找。申请空间的大小-1是因为结构体内本身的那个字节还是可以使用的。
在PHP5.4中将这个字段定义成const char* arKey类型了。
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)
{
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
if (!memcmp(p->arKey, arKey, nKeyLength)) {
if (flag & HASH_ADD) {
return FAILURE;
}
HANDLE_BLOCK_INTERRUPTIONS();
if (ht->pDestructor) {
ht->pDestructor(p->pData);
}
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->pData;
}
HANDLE_UNBLOCK_INTERRUPTIONS();
return SUCCESS;
}
}
p = p->pNext;
}
p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
return FAILURE;
}
memcpy(p->arKey, arKey, nKeyLength);
p->nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p->h = h;
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
if (pDest) {
*pDest = p->pData;
}
HANDLE_BLOCK_INTERRUPTIONS();
CONNECT_TO_GLOBAL_DLLIST(p, ht);
ht->arBuckets[nIndex] = p;
HANDLE_UNBLOCK_INTERRUPTIONS();
ht->nNumOfElements++;
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
return SUCCESS;
}
http://www.php-internals.com/book/?p=chapt03/03-01-02-hashtable-in-php