What is PHP HashTable?

What is PHP HashTable?

PHP HashTable refers to a hash table, which is a data structure that is directly accessed based on the key value. That is, it can access records by mapping the key value to a location in the table, so that it can To speed up the search, the array storing the records is a hash table.

The new version of HashTable

Compared with the old version of hashtable, the changes are quite big

• The elements of the old version The storage is scattered. Bucket **arBuckets stores the address of the pointer pointing to the bucket. The new version's element storage is continuous Bucket *arData;

• There are 4 in the old version of the bucket. Pointers There is only one pointer in the bucket in the new version, and it is only used when hash collisions

• There are three less pointers. Let’s see how to follow the new version of hashtable. Insertion order traversal and resolution of hash conflicts

Look at the definition of 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_t          nTableMask;          //  hash表的掩码 用来确定hsh
		Bucket           *arData;                    // bucket数组
		uint32_t         *arHash;              // hashtable 查找  大小为nTableMask 存放指向bucket的指针(疑问在源码定义中未看到)
		uint32_t          nNumUsed;            //  元素个数 包含已删除的元素
		uint32_t          nNumOfElements;    //  有效的元素个数
		uint32_t          nTableSize;      //  hash表的大小
		uint32_t          nInternalPointer;     
		zend_long         nNextFreeElement;
		dtor_func_t       pDestructor;
	};

The definition of bucket

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

typedef struct _zval_struct     zval;
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_t     next;                   // 重点关注这个  存放hash 冲突下一个元素的位置
		uint32_t     cache_slot;           /* literal cache slot */
		uint32_t     lineno;               /* line number (for ast nodes) */
		uint32_t     num_args;             /* arguments number for EX(This) */
		uint32_t     fe_pos;               /* foreach position */
		uint32_t     fe_iter_idx;          /* foreach iterator index */
		uint32_t     access_flags;         /* class constant access flags */
		uint32_t     property_guard;       /* single property guard */
		uint32_t     extra;                /* not further specified */
	} u2;

Structural diagram

Recommended tutorial: "PHP"

The above is the detailed content of What is PHP HashTable?. For more information, please follow other related articles on the PHP Chinese website!