您的位置 首页 技术

PHP HashTable是什么?

PHP HashTable是什么? 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表的掩码 用来确定hshBucket           *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 值 用来寻找对比keyzend_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;

结构图

Snipaste_2020-06-24_14-23-46.png

推荐教程:《PHP》

以上就是PHP HashTable是什么?的详细内容,更多请关注24课堂在线网其它相关文章!

本文来自网络,不代表24小时课堂在线立场,转载请注明出处:http://www.24ketang.cn/87944.html

为您推荐

返回顶部