第三节 PHP的哈希表实现

[c]
typedef struct _hashtable { 
	uint nTableSize;    	// hash Bucket的大小，最小为8，以2x增长。
	uint nTableMask;		// nTableSize-1 ， 索引取值的优化
	uint nNumOfElements; 	// hash Bucket中当前存在的元素个数，count()函数会直接返回此值 
	ulong nNextFreeElement;	// 下一个数字索引的位置
	Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
	Bucket *pListHead;          // 存储数组头元素指针
	Bucket *pListTail;          // 存储数组尾元素指针
	Bucket **arBuckets;         // 存储hash数组
	dtor_func_t pDestructor;	// 在删除元素时执行的回调函数，用于资源的释放
	zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
	unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
	zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
	int inconsistent;
#endif
} HashTable;

[c]
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) < nSize) {
			i++;
		}
		ht->nTableSize = 1 << i;
	}
	// ...
	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;
}

[c]
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;

NOTE mask的作用就是将哈希值映射到槽位所能存储的索引范围内。 例如：某个key的索引值是21， 哈希表的大小为8，则mask为7，则求与时的二进制表示为： 10101 & 111 = 101 也就是十进制的5。 因为2的整数次方-1的二进制比较特殊：后面N位的值都是1，这样比较容易能将值进行映射， 如果是普通数字进行了二进制与之后会影响哈希值的结果。那么哈希函数计算的值的平均分布就可能出现影响。

[php]
<?php
$a = array(10 => 'Hello');
$a[] = 'TIPI';
var_dump($a);
// ouput
array(2) {
  [10]=>
  string(5) "Hello"
  [11]=>
  string(5) "TIPI"
}

[c]
typedef struct bucket {
	ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
	uint nKeyLength;	// hash关键字的长度，如果数组索引为数字，此值为0
	void *pData;		// 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
	void *pDataPtr;		//如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
	struct bucket *pListNext;	// 整个hash表的下一元素
	struct bucket *pListLast;   // 整个哈希表该元素的上一个元素
	struct bucket *pNext;		// 存放在同一个hash Bucket内的下一个元素
	struct bucket *pLast;		// 同一个哈希bucket的上一个元素
	// 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
	char arKey[1]; 		
} Bucket;

[c]
p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
	return FAILURE;
}
memcpy(p->arKey, arKey, nKeyLength);

NOTE 在PHP5.4中将这个字段定义成const char* arKey类型了。

• Bucket结构体维护了两个双向链表，pNext和pLast指针分别指向本槽位所在的链表的关系。
• 而pListNext和pListLast指针指向的则是整个哈希表所有的数据之间的链接关系。 HashTable结构体中的pListHead和pListTail则维护整个哈希表的头元素指针和最后一个元素的指针。

NOTE PHP中数组的操作函数非常多，例如：array_shift()和array_pop()函数，分别从数组的头部和尾部弹出元素。 哈希表中保存了头部和尾部指针，这样在执行这些操作时就能在常数时间内找到目标。 PHP中还有一些使用的相对不那么多的数组操作函数：next()，prev()等的循环中， 哈希表的另外一个指针就能发挥作用了：pInternalPointer，这个用于保存当前哈希表内部的指针。 这在循环时就非常有用。

1. 插入Bucket1时，哈希表为空，经过哈希后定位到索引为1的槽位。此时的1槽位只有一个元素Bucket1。 其中Bucket1的pData或者pDataPtr指向的是Bucket1所存储的数据。此时由于没有链接关系。pNext， pLast，pListNext，pListLast指针均为空。同时在HashTable结构体中也保存了整个哈希表的第一个元素指针， 和最后一个元素指针，此时HashTable的pListHead和pListTail指针均指向Bucket1。
2. 插入Bucket2时，由于Bucket2的key和Bucket1的key出现冲突，此时将Bucket2放在双链表的前面。 由于Bucket2后插入并置于链表的前端，此时Bucket2.pNext指向Bucket1，由于Bucket2后插入。 Bucket1.pListNext指向Bucket2，这时Bucket2就是哈希表的最后一个元素，这是HashTable.pListTail指向Bucket2。
3. 插入Bucket3，该key没有哈希到槽位1，这时Bucket2.pListNext指向Bucket3，因为Bucket3后插入。 同时HashTable.pListTail改为指向Bucket3。

• 初始化操作，例如zend_hash_init()函数，用于初始化哈希表接口，分配空间等。
• 查找，插入，删除和更新操作接口，这是比较常规的操作。
• 迭代和循环，这类的接口用于循环对哈希表进行操作。
• 复制，排序，倒置和销毁等操作。

[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)
{
	 //...省略变量初始化和nKeyLength <=0 的异常处理
	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();
				//..省略debug输出
				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]); //Bucket双向链表操作
	if (pDest) {
		*pDest = p->pData;
	}
	HANDLE_BLOCK_INTERRUPTIONS();
	CONNECT_TO_GLOBAL_DLLIST(p, ht);    // 将新的Bucket元素添加到数组的链接表的最后面
	ht->arBuckets[nIndex] = p;
	HANDLE_UNBLOCK_INTERRUPTIONS();
	ht->nNumOfElements++;
	ZEND_HASH_IF_FULL_DO_RESIZE(ht);		/*  如果此时数组的容量满了，则对其进行扩容。*/
	return SUCCESS;
}

1. 生成hash值，通过与nTableMask执行与操作，获取在arBuckets数组中的Bucket。
2. 如果Bucket中已经存在元素，则遍历整个Bucket，查找是否存在相同的key值元素，如果有并且是update调用，则执行update数据操作。
3. 创建新的Bucket元素，初始化数据，并将新元素添加到当前hash值对应的Bucket链表的最前面（CONNECT_TO_BUCKET_DLLIST）。
4. 将新的Bucket元素添加到数组的链接表的最后面（CONNECT_TO_GLOBAL_DLLIST）。
5. 将元素个数加1，如果此时数组的容量满了，则对其进行扩容。这里的判断是依据nNumOfElements和nTableSize的大小。 如果nNumOfElements > nTableSize则会调用zend_hash_do_resize以2X的方式扩容（nTableSize << 1）。