PHP HashTable是什么？

PHP HashTable是什么？

PHP HashTable是指散列表，是根据关键码值而直接进行访问的数据结构，也就是它可以通过把关键码值映射到表中一个位置来访问记录，从而可以加快查找的速度，其中存放记录的数组就是散列表。

新版本的HashTable

与老版本的hashtable相比改动还是挺大的

老版本的元素存储是分散的，Bucket **arBuckets 里面存储的是指针 指向bucket的地址，新版的的元素存储是连续的 Bucket *arData;

老版本bucket中有4个指针 新版版中的bucket中只有一个指针，并且只有在hash碰撞的时候才会用到

少了三个指针，看下新版本的hashtable 如何做好按照插入顺序遍历和解决hash冲突

看下hashtable的定义

   typedef struct _zend_array HashTable;
   
	struct _zend_array {
		zend_refcounted_h gc;   //  gc 相关
		union {  //  联合体 
			struct { 
				ZEND_ENDIAN_LOHI_4(
					zend_uchar    flags,
					zend_uchar    nApplyCount,
					zend_uchar    nIteratorsCount,
					zend_uchar    consistency)
			} v;
			uint32_t flags;
		} u;
		uint32_tnTableMask;//  hash表的掩码 用来确定hsh
		Bucket *arData;// bucket数组
		uint32_t    *arHash;    // hashtable 查找  大小为nTableMask 存放指向bucket的指针(疑问在源码定义中未看到)
		uint32_tnNumUsed;  //  元素个数 包含已删除的元素
		uint32_tnNumOfElements;    //  有效的元素个数
		uint32_tnTableSize; //  hash表的大小
		uint32_tnInternalPointer;
		zend_long    nNextFreeElement;
		dtor_func_t  pDestructor;
	};

bucket的定义

typedef struct _Bucket {
	zval    val; 
	zend_ulong   h;    //存的hash 值 用来寻找对比key
	zend_string *key; // 如果key是string 则存放key 如果是数字 则为空
} Bucket;

typedef struct _zval_structzval;
struct _zval_struct {
	zend_value   value;			// value 真正的结构
	union {
		struct {
			ZEND_ENDIAN_LOHI_4(
				zend_uchar    type,			/* active type */
				zend_uchar    type_flags,
				zend_uchar    const_flags,
				zend_uchar    reserved)	    /* call info for EX(This) */
		} v;
		uint32_t type_info;
	} u1;
	union {
		uint32_tnext;    // 重点关注这个  存放hash 冲突下一个元素的位置
		uint32_tcache_slot; /* literal cache slot */
		uint32_tlineno;/* line number (for ast nodes) */
		uint32_tnum_args;   /* arguments number for EX(This) */
		uint32_tfe_pos;/* foreach position */
		uint32_tfe_iter_idx;/* foreach iterator index */
		uint32_taccess_flags;    /* class constant access flags */
		uint32_tproperty_guard;  /* single property guard */
		uint32_textra; /* not further specified */
	} u2;

结构图

推荐教程：《PHP》

以上就是PHP HashTable是什么？的详细内容！

查看更多关于PHP HashTable是什么？的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did55511