PHP内核之旅-5.强大的数组

一、数组的内部结构

1.底层实现为散列表(HashTable,也称作哈希表)

2.散列表的概念:

是根据关键码值(Key value)而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。复杂度为O(1)。

文件路径\Zend\zend_types.h

_zend_array结构:

 1 typedef struct _zend_array zend_array;
 2 typedef struct _zend_array HashTable;
 3 
 4 struct _zend_array {
 5     zend_refcounted_h gc;
 6     union {
 7         struct {
 8             ZEND_ENDIAN_LOHI_4(
 9                 zend_uchar    flags,
10                 zend_uchar    nApplyCount,
11                 zend_uchar    nIteratorsCount,
12                 zend_uchar    consistency)
13         } v;
14         uint32_t flags;
15     } u;
16     uint32_t          nTableMask;
17     Bucket           *arData;
18     uint32_t          nNumUsed;
19     uint32_t          nNumOfElements;
20     uint32_t          nTableSize;
21     uint32_t          nInternalPointer;
22     zend_long         nNextFreeElement;
23     dtor_func_t       pDestructor;
24 };

zend_array和HashTable结构相同 

arData:散列表中保存存储元素的数组,其内存是连续的,arData指向数组的起始位置,其内存连续。

nTableSize:数组的总容量,可以容纳的元素数,大小是2的幂次方,最小为8

nTableMask: 映射元素的存储位置用到,nTableSize的负数

nNumUsed: 数组当前使用的Bucket数,删除元素时,不会将其从数组中移除,将这个元素的类型标为IS_UNDEF,当数组容量超限,扩容时才会删除。

nNumOfElements:数组中有效元素的位置

nNextFreeElement:下一个数值的索引

pDestructor:删除或覆盖数组中的某个元素时,则调用此函数对旧元素进行处理

u:辅助作用

Bucket结构:

1 typedef struct _Bucket {
2     zval              val;
3     zend_ulong        h;                /* hash value (or numeric index)   */
4     zend_string      *key;              /* string key or NULL for numerics */
5 } Bucket;

 val: 具体的value

 h: key的hash值,或者数值索引

*key: 存储元素的key,如果元素是数值索引则为NULL

二、数组的基本实现

散列函数:将元素进行hash运算后的值,对数组大小取模之后的值(下标:0~7)分配到中间映射表

中间映射表:元素和下标的映射关系表。可以通过arData向前访问到

元素数组:实际存储元素的数组,按照下标有序存储元素

三、数组的初始化

\Zend\zend_hash.c

 1 ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
 2 {
 3     GC_REFCOUNT(ht) = 1;
 4     GC_TYPE_INFO(ht) = IS_ARRAY | (persistent ? 0 : (GC_COLLECTABLE << GC_FLAGS_SHIFT));
 5     ht->u.flags = (persistent ? HASH_FLAG_PERSISTENT : 0) | HASH_FLAG_APPLY_PROTECTION | HASH_FLAG_STATIC_KEYS;
 6     ht->nTableMask = HT_MIN_MASK;
 7     HT_SET_DATA_ADDR(ht, &uninitialized_bucket);
 8     ht->nNumUsed = 0;
 9     ht->nNumOfElements = 0;
10     ht->nInternalPointer = HT_INVALID_IDX;
11     ht->nNextFreeElement = 0;
12     ht->pDestructor = pDestructor;
13     ht->nTableSize = zend_hash_check_size(nSize);
14 }

\Zend\zend_API.c

1 ZEND_API int _array_init(zval *arg, uint32_t size ZEND_FILE_LINE_DC) /* {{{ */
2 {
3     ZVAL_NEW_ARR(arg);
4     _zend_hash_init(Z_ARRVAL_P(arg), size, ZVAL_PTR_DTOR, 0 ZEND_FILE_LINE_RELAY_CC);
5     return SUCCESS;
6 }

 四、插入

插入时首先会检查数组已经分配存储空间,初始化时没有实际分配arData的内存,第一次插入时才会根据nTableSize的大小分配,分配完以后会把HashTable->u.flags打上HASH_FLAG_INITIALIZED掩码,下次插入时发现已经分配了就不会再重复操作。

 1 static zend_always_inline void zend_hash_check_init(HashTable *ht, int packed)
 2 {
 3     HT_ASSERT_RC1(ht);
 4     if (UNEXPECTED(!((ht)->u.flags & HASH_FLAG_INITIALIZED))) {
 5         zend_hash_real_init_ex(ht, packed);
 6     }
 7 }
 8 
 9 #define CHECK_INIT(ht, packed) \
10     zend_hash_check_init(ht, packed)

参考资料:

http://www.php-internals.com/

PHP7内核剖析

作  者: Jackson0714 出  处:http://www.cnblogs.com/jackson0714/ 关于作者:专注于微软平台的项目开发。如有问题或建议,请多多赐教! 版权声明:本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。 特此声明:所有评论和私信都会在第一时间回复。也欢迎园子的大大们指正错误,共同进步。或者直接私信我 声援博主:如果您觉得文章对您有帮助,可以点击文章右下角推荐一下。您的鼓励是作者坚持原创和持续写作的最大动力!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ4260: Codechef REBXOR (01Tire树)

11330
来自专栏Java成神之路

HQL语句大全

Hibernate配备了一种非常强大的查询语言,这种语言看上去很像SQL。但是不要被语法结构 上的相似所迷惑,HQL是非常有意识的被设计为完全面向对象的查询,它...

21350
来自专栏专注 Java 基础分享

Hibernate框架学习之注解映射实体类

     前面的相关文章中,我们已经介绍了使用XML配置文件映射实体类及其各种类型的属性的相关知识。然而不论是时代的潮流还是臃肿繁杂的配置代码告诉我们,注解配置...

22990
来自专栏应兆康的专栏

Python Web - Flask笔记5

MySQL Workbench是一款专为MySQL设计的ER/数据库建模工具。它是著名的数据库设计工具DBDesigner4的继任者。你可以用MySQL Wor...

20610
来自专栏JAVA后端开发

给mybatis添加自动建表,自动加字段的功能

以前项目用惯了hibernate,jpa,它有个自动建表功能,只要在PO里加上配置就可以了,感觉很爽. 但现在用mybatis,发现没有该功能,每次都加个字段...

56230
来自专栏MasiMaro 的技术博文

windows错误处理

在调用windows API时函数会首先对我们传入的参数进行校验,然后执行,如果出现什么情况导致函数执行出错,有的函数可以通过返回值来判断函数是否出错,比如对于...

14920
来自专栏数据结构与算法

Day5上午解题报告

预计分数:100+40+30=170 实际假分数:0+0+0=0 CE*3 实际真分数:60+50+0=110 老师没把我的程序放的文件夹里面,于是。。。。。 ...

36160
来自专栏Golang语言社区

Golang中time包用法--转

time包中包括两类时间:时间点(某一时刻)和时常(某一段时间) 1时间常量(时间格式化) const ( ANSIC = "Mon Jan...

1.7K80
来自专栏数据结构与算法

BZOJ3798: 特殊的质数(分段打表)

对于这种求$[A, B]$区间内xxx的数的个数,然后$B$又不算是特别大的题,考虑分段打表

83620
来自专栏个人分享

Hive metastore整体代码分析及详解

  从上一篇对Hive metastore表结构的简要分析中,我再根据数据设计的实体对象,再进行整个代码结构的总结。那么我们先打开metadata的目录,其目录...

75530

扫码关注云+社区

领取腾讯云代金券