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_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;
	};

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;

結構圖

推薦教學：《PHP》

以上就是PHP HashTable是什麼？的詳細內容，更多請關注TW511.COM其它相關文章！