程序员

php7数组的实现及部分源码分析

2020-09-28  本文已影响0人  跑马溜溜的球

1.基本概念

1.1 数组的语义

本质上PHP数组是一个有序字典，它必须同时满足以下2个条件：

1.2 数组的概念

PHP的数组zend_array对应的是HashTable。HashTable(哈希表)是一种通过某种哈希函数将特定的键映射到特定值的一种数据结构，它维护着键和值的一一对应关系，并且可以快速地根据键检索到值，查找效率为O(1)。HashTable的示意如图下：


HashTable示意图

说明：

在具体实现过程中，PHP基于上述基本概念，对bucket以及哈希函数进行了一些补充，增加了hash1函数以生成h值，然后通过hash2函数散列到不同的slot, 示意图如下：


php hash table

说明：

这个h值的作用是什么呢？

1.3 php7中h值的计算方法

php7中h的计算(即1.2节中所说的hash1)采用了DJB hash function，俗称“Times33”算法。很多流行的hash map都使用了这种计算方法，它的思想十分简单：

h(0) = 任意初始值
h(i) = 33 * h(i-1) + str[i]

一个简单的c版本实现如下：

unsigned int DJBHash(char* str, unsigned int len)
{
    //初始值
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {   
      //左移5相当于*32，再加一个自身的值就相当于*33，用位移替代乘法，以提高速度
      hash = ((hash << 5) + hash) + (*str);
   }   

   return hash;
}

php7中源码如下，函数上方还有一大段注释，讲述了一些time33算法的内容，有兴趣可以查看。

//php-7.0.14/Zend/zend_string.h 

static zend_always_inline zend_ulong zend_inline_hash_func(const char *str, size_t len){
    //hash初始值
    register zend_ulong hash = Z_UL(5381);
    /* variant with the hash unrolled eight times */
    //8个一组计算，减少循环次数
    for (; len >= 8; len -= 8) {
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
    }
    //累加字串余下部分(一定小于8)的值
    switch (len) {
        case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *str++; break;
        case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
    }

    /* Hash value can't be zero, so we always set the high bit */
#if SIZEOF_ZEND_LONG == 8
    return hash | Z_UL(0x8000000000000000);
#elif SIZEOF_ZEND_LONG == 4
    return hash | Z_UL(0x80000000);
#else
# error "Unknown SIZEOF_ZEND_LONG"
#endif
}

2.php7数组的实现

PHP7通过链地址法来解决哈希冲突，只不过PHP5的链表是真实物理存在的链表，链表中bucket间的上下游是通过真实存在的指针来维护，而PHP7的链表其实是一种逻辑上的链表，所有的bucket都分配在一段连续的数组内存中，且不再通过指针维护上下游关系，每一个bucket只维护一个bucket在数组中的索引(由于内存是连续的，通过索引可以快速定位到bucket)，即可完成链表上的bucket遍历。

2.1 基本结构

在PHP 7中，数组的核心结构是struct _zend_array和bucket，并且为struct_zend_array起了两个别名：HashTable和zend_array。

zend_array定义如下：

//php-7.0.14/Zend/zend_types.h

typedef struct _zend_array zend_array;
typedef struct _zend_array HashTable;

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

struct _zend_array {    
    zend_refcounted_h gc;
    union {        
        struct {            
            ZEND_ENDIAN_LOHI_4(                
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,                
                zend_uchar    reserve)
        } v;
        uint32_t flags;
    } u;    
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

2.1.1 bucket结构分析

由于不再依赖于物理指针，整个bucket变得清爽了很多，只有val、h、key3个字段。

bucket从使用角度可以分为3种：未使用bucket、有效bucket、无效bucket。

在内存分布上，有效bucket和无效bucket会交替分布，但都在未使用bucket的前面。插入的时候永远在未使用bucket上进行。当由于删除等操作，导致无效bucket非常多，而有效bucket很少时，会对整个bucket数组进行rehash操作。这样，稀疏的有效bucket就会变得连续而紧密，部分无效bucket会被重新利用而变为有效bucket。还有一部分有效bucket和无效bucket会被释放出来，重新变为未使用bucket。

2.1.2 HashTable结构分析

接下来看看HashTable。

HashTable结构

nTableSize、nNumUsed、nNumOfElements三者关系如下：


nTableSize、nNumUsed、nNumOfElements三者关系 
//php-7.0.14/Zend/zend_hash.h
#define HASH_FLAG_PERSISTENT       (1<<0)   //是否使用持久化内存，不使用内存池
#define HASH_FLAG_APPLY_PROTECTION (1<<1)   //是否开启递归遍历保护
#define HASH_FLAG_PACKED           (1<<2)   //是否是packed array
#define HASH_FLAG_INITIALIZED      (1<<3)   //是否已经初始化
#define HASH_FLAG_STATIC_KEYS      (1<<4)   //标记key为数字key或者字符串key
#define HASH_FLAG_HAS_EMPTY_IND    (1<<5)   //是否存在空的间接val

2.1.3 为什么HashTable的掩码是负数

PHP 7在分配bucket数组内存时，在bucket数组的前面额外多申请了一些内存，这段内存是一个索引数组（也叫索引表），数组里面的每个元素代表一个slot，存放着每个slot链表的第一个bucket在bucket数组中的下标。如果当前slot没有任何bucket元素，那么索引值为-1。而为了实现逻辑链表，由于bucket元素的val是zval, PHP 7通过bucket.val.u2.next表达链表中下一个元素在数组中的下标，如下图（n等于nTableSize）所示。


索引

这里一个非常巧妙的设计是索引数组仍然通过HashTable.arData来引用。由于索引数组和bucket数组是连续的内存，因此arData[0...n-1]表示bucket数组元素，((uint32_t*) (arData))[-1...-n]表示索引数组元素。因此在计算bucket属于哪个slot时，要做的就是确定它在索引数组中的下标，而这个下标是从-n～-1的负数，分别代表slot1到slotN。

为了得到介于[-n, -1]之间的负数的下标，PHP7的HashTable设计中的hash2函数（根据h值取得slot值）是这样的（其中nIndex就是slot值）：

nIndex = h | ht->nTableMask;

以nTableSize=8为例，nTableMask=-8，二进制表示是：

11111111111111111111111111111000

任何整数和它进行按位或之后的结果只有以下8种，这恰好满足[-n, -1]的取值范围：

11111111111111111111111111111000    //-8
11111111111111111111111111111001    //-7
11111111111111111111111111111010    //-6
11111111111111111111111111111011    //-5
11111111111111111111111111111100    //-4
11111111111111111111111111111101    //-3
11111111111111111111111111111110    //-2
11111111111111111111111111111111    //-1

2.2 packed array和hash array的区别

PHP数组有两种用法:

例如：

$a = [1, 2, 3];   //纯数组
$b = ["a" => 1, "b" => 2, "c" => 3];  //map

对于上面的两种用法，PHP7引申出了 Packed Array 和 Hash Array的概念。当HashTable的u.v.flags & HASH_FALG_PACKED > 0时，表示当前数组是Packed Array，否则是Hash Array。

2.2.1 内存的本质区别

packed array和hash array的区别在哪里呢？先看下面两段代码：

//array1.php
$start = memory_get_usage();
$test = [];
for($i=0; $i<=200000; $i++){
    $test[$i] = $i;
}

$end = memory_get_usage();

echo $end - $start, "\n"

//array2.php
$start = memory_get_usage();
$test = [];
for($i=200000; $i>=0; $i--){
    $test[$i] = $i;
}
$end = memory_get_usage();

echo $end - $start, "\n";

运行结果如下：

php array1.php
8392840

php array2.php
9437320

array2.php比array1.php多使用了1M左右内存，这是为什么呢？原因就在于这两种写法，test数组的内存结构是有区别的，一种是packed array，另一种是hash array。

2.2.2 packed array

packed array具有以下约束和特性。

它实际上利用了bucket数组的连续性特点，对于某些只有数字key的场景进行的优化。由于不再需要索引数组，从内存空间上节省了(nTableSize-2 )*sizeof(uint32_t) 个字节。另外，由于存取bucket是直接操作bucket数组，在性能上也有所提升。

接下来我们看下本小节开头举的例子，array1.php中test的key都是数字key，且key插入顺序为0，1，2,满足递增的特性，所以它是Packed Array。示意图如下:


packed array

说明：

2.2.3 hash array

hash array依赖索引数组来维护每一个slot链表中首元素在bucket数组中的下标。对array2.php，$test的key不是递增的，因此它不是packed array，而是hash array。示意图如下：


hash array

下面以$test[199999]为例，说明hash方式如何寻找其值。

2.2.4 几个例子

$a = [1=>'a', 3=>'b', 5=>'c'];  //packed array
$b = [1=>'a', 5=>'c', 3=>'b'];  //hash array
    
$c = [1=>'a', 8=>'b'];  //hash array

说明：

bucket数组中下标为2～7的6个bucket为了保持packed array特性，无法再插入元素，成为浪费的空间。因此，PHP 7会在packed array的空间效率以及时间效率优化与空间浪费之间做一个平衡，当空间浪费比较多的时候，PHP 7会将packed array转化为hash array，变成下面的样子：


转化为hash array

2.3 哈希冲突的解决

数据在插入HashTable时，不同的key经过哈希函数得到的值可能相同，导致插入索引数组冲突，理论上需要在索引数组外再加一个链表把所有冲突的value以双链表的形式关联起来，然后读取的时候去遍历这个双链表中的数据，比较对应的key。

PHP7的hash array的做法是，不单独维护一个双链表，而是把每个冲突的idx存储在bucket的zval.u2.next中，插入的时候把老的value存储的地址（idx）放到新value的next中，再把新value的存储地址更新到索引数组中。

举个例子，假如顺次插入的第1、2、3元素, 它们的h|nTableMask相同，均为-6， 发生哈希冲突，那么解决方法如下图所示：


冲突解决

2.4 扩容和rehash操作

在hash array中unset一个key的时候并不会真正触发删除，是只做一个标记，删除是在扩容和rehash(重建索引)的时候才会触发。插入时触发扩容及rehash的整体流程如下图所示：


插入流程

说明：

ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)

则将已删除元素从HashTable中移除，并重建索引(rehash)。如果未到阈值，则要进行扩容操作，新的容量扩大到当前大小的2倍（即2*nTableSize），将当前bucket数组复制到新的空间，然后重建索引。

相关源码如下：

//php-7.0.14/Zend/zend_hash.c
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
    IS_CONSISTENT(ht);
    HT_ASSERT(GC_REFCOUNT(ht) == 1);
    
    if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */
        HANDLE_BLOCK_INTERRUPTIONS();
        //触发条件，重建索引，以便释放空间
        zend_hash_rehash(ht);
        HANDLE_UNBLOCK_INTERRUPTIONS();
    } 
    //将现有空间翻倍
    else if (ht->nTableSize < HT_MAX_SIZE) {  /* Let's double the table size */
        //获取新旧arData位置
        void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
        //此时nsize为2*nTableSize，加法比*2快
        uint32_t nSize = ht->nTableSize + ht->nTableSize;
        Bucket *old_buckets = ht->arData;

        HANDLE_BLOCK_INTERRUPTIONS();        
        //申请新的数组内存大小
        new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ht->u.flags & HASH_FLAG_PERSISTENT);
        
        //设置新的table大小
        ht->nTableSize = nSize;
        //hash array中，nTableMask等于-nTableSize
        ht->nTableMask = -ht->nTableSize;
        //设置新的arData位置
        HT_SET_DATA_ADDR(ht, new_data);
        //拷贝旧的bucket数组数据到新的arData
        memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
        //释放旧的arData数据
        pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT);
        //重建索引
        zend_hash_rehash(ht);
        HANDLE_UNBLOCK_INTERRUPTIONS();
    } else {
        //内存不够，报错
        zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%zu * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
    }
}

下面我们对rehash作更详细的说明：

  1. 重置所有nIndex数组为-1；
  2. 初始化两个bucket类型的指针p、q，循环遍历bucket数组；
  3. 每次循环，p++，遇到第一个IS_UNDEF时，q=p；继续循环数组；
  4. 当再一次遇到一个正常数据时，把正常数据拷贝到q指向的位置，q++；
  5. 直到遍历完数组，更新nNumUsed等计数。

下面来看源码

//php-7.0.14/Zend/zend_hash.c

ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
    Bucket *p;
    uint32_t nIndex, i;

    IS_CONSISTENT(ht);
    
    //数组里没有元素
    if (UNEXPECTED(ht->nNumOfElements == 0)) {
        if (ht->u.flags & HASH_FLAG_INITIALIZED) {            
            ht->nNumUsed = 0;
            //索引区的值均置为HT_INVALID_IDX(-1)
            HT_HASH_RESET(ht);
        }
        return SUCCESS;
    }

    HT_HASH_RESET(ht);
    i = 0;
    p = ht->arData;
    /*
     * 数组里没有删除的元素
     * 重新计算索引数组即可
     */
    if (ht->nNumUsed == ht->nNumOfElements) {
        do {
            nIndex = p->h | ht->nTableMask;
            //zval.u2.next记录开链(有hash冲突的情况)
            Z_NEXT(p->val) = HT_HASH(ht, nIndex);
            //在索引区(nIndex处)记录当前元素位置
            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
            p++;
        } while (++i < ht->nNumUsed);
    }
    else{
        do{
            /*此时表明有已删除元素
             *则将后面的value依次前移，压实Bucket数组
             */
            if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
                //j记录了当前实际有效元素的个数
                uint32_t j = i;                
                //q记录下第一个被删除元素的位置
                Bucket *q = p;
                
                ... ...
                
                while (++i < ht->nNumUsed) {
                    p++;
                    //p碰到非IS_UNDEF元素时，将其复制到q所指的位置
                    if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
                        ZVAL_COPY_VALUE(&q->val, &p->val);
                        q->h = p->h;
                        nIndex = q->h | ht->nTableMask;
                        q->key = p->key;
                        Z_NEXT(q->val) = HT_HASH(ht, nIndex);
                        HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
                        if (UNEXPECTED(ht->nInternalPointer == i)) {
                            ht->nInternalPointer = j;
                        }
                        //q向前移动
                        q++;
                        //有效元素增加一个
                        j++;
                    }
                }
            
                ... ...
                //数据被压实了，所以ht->nNumUsed即为当前有效元素的个数
                ht->nNumUsed = j;
                break;
            }
            
            //未碰到IS_UNDEF元素前走此逻辑，只需要重算索引
            nIndex = p->h | ht->nTableMask;
            Z_NEXT(p->val) = HT_HASH(ht, nIndex);
            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
            p++;
        }while (++i < ht->nNumUsed);
    }
    
     return SUCCESS;
}

来看一个例子：

//生成hash array
for($i=7; $i>=0; $i--){
    $arr[$i] = $i * 10;
}

//产生空洞
unset($arr[3]);
unset($arr[4]);
unset($arr[5]);

/*
 * ht->nNumUsed = 8
 * ht->nNumOfElements = 5
 * 插入新元素满足ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)
 * 所以触发rehash
 */
$arr[11] = 110;

rehash之前


rehash之前

rehash之后


rehash之后

值得注意的是，rehash后，bucket数组中第6，7两个位置存储的值依然在，只是索引中找不到他们的位置。另外使用gdb可看到nNumUsed = 6，也表明6，7两个位置是未使用的。

2.5 packed array与hash array的转换

转换代码如下：

//packed array 转hash array
ZEND_API void ZEND_FASTCALL zend_hash_packed_to_hash(HashTable *ht)
{
    //获取新旧arData数据位置
    void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
    //记录原有的ht->arData位置
    Bucket *old_buckets = ht->arData;

    HT_ASSERT(GC_REFCOUNT(ht) == 1);
    HANDLE_BLOCK_INTERRUPTIONS();
    
    //去掉packed array标记
    ht->u.flags &= ~HASH_FLAG_PACKED;
    //为新hash array申请bucket数组空间
    new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, -ht->nTableSize), (ht)->u.flags & HASH_FLAG_PERSISTENT);
    //重新设置ht->nTableMask（packed array的nTableMask为-2,所以要重设）
    ht->nTableMask = -ht->nTableSize;
    //ht->arData指向新地址
    HT_SET_DATA_ADDR(ht, new_data);
    //拷贝旧数据到新的arData
    memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
    //释放老的arData空间
    pefree(old_data, (ht)->u.flags & HASH_FLAG_PERSISTENT);
    //重建索引
    zend_hash_rehash(ht);
    HANDLE_UNBLOCK_INTERRUPTIONS();
}

下面我们结合gdb看一个转换的例子，php代码如下：

//hash.php

$arr[] = 'foo';
echo "packed array\n";
var_dump($arr);
$arr['a'] = 'bar';
echo "hash array\n";
var_dump($arr);

在命令行下执行gdb php， 进入gdb调试。

/*在var_dump处设置断点，查看数组变化*/
b php_var_dump
Breakpoint 1 at 0x597040: file /usr/local/src/php-7.0.14/ext/standard/var.c, line 79.

(gdb) run hash.php 
packed array

Breakpoint 1, php_var_dump (struc=0x7ffff7813160, level=1) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79      {

//struc即是$arr
(gdb) p struc
$1 = (zval *) 0x7ffff7813160

(gdb) p *struc.value.arr
$3 = {gc = {refcount = 2, u = {v = {type = 7 '\a', flags = 0 '\000', gc_info = 0}, type_info = 7}}, u = {v = {
      flags = 30 '\036', nApplyCount = 0 '\000', nIteratorsCount = 0 '\000', reserve = 0 '\000'}, flags = 30}, 
  nTableMask = 4294967294, arData = 0x7ffff785c788, nNumUsed = 1, nNumOfElements = 1, nTableSize = 8, nInternalPointer = 0, 
  nNextFreeElement = 1, pDestructor = 0x62faa0 <_zval_ptr_dtor>}

//查看第0个元素内容为foo，符合预期
(gdb) p *struc.value.arr.arData[0].val.value.str.val@3
$3 = "foo"

接下来查看变成hash的arr

(gdb) c
Continuing.
array(1) {
  [0]=>

Breakpoint 1, php_var_dump (struc=0x7ffff785c788, level=3) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79      {
(gdb) c
Continuing.
  string(3) "foo"
}
//输出hash array后，说明是插入a=bar的$arr了
hash array

Breakpoint 1, php_var_dump (struc=0x7ffff7813160, level=1) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79      {

(gdb) p *struc.value.arr
$7 = {gc = {refcount = 2, u = {v = {type = 7 '\a', flags = 0 '\000', gc_info = 0}, type_info = 7}}, u = {v = {
      flags = 26 '\032', nApplyCount = 0 '\000', nIteratorsCount = 0 '\000', reserve = 0 '\000'}, flags = 26}, 
  nTableMask = 4294967288, arData = 0x7ffff785c8e0, nNumUsed = 2, nNumOfElements = 2, nTableSize = 8, nInternalPointer = 0, 
  nNextFreeElement = 1, pDestructor = 0x62faa0 <_zval_ptr_dtor>}

(gdb) p struc.value.arr.arData[0]
//第0个元素h=0
$11 = {val = {value = {lval = 140737345758432, dval = 6.9533487626122526e-310, counted = 0x7ffff78024e0, 
      str = 0x7ffff78024e0, arr = 0x7ffff78024e0, obj = 0x7ffff78024e0, res = 0x7ffff78024e0, ref = 0x7ffff78024e0, 
      ast = 0x7ffff78024e0, zv = 0x7ffff78024e0, ptr = 0x7ffff78024e0, ce = 0x7ffff78024e0, func = 0x7ffff78024e0, ww = {
        w1 = 4152370400, w2 = 32767}}, u1 = {v = {type = 6 '\006', type_flags = 0 '\000', const_flags = 0 '\000', 
        reserved = 0 '\000'}, type_info = 6}, u2 = {var_flags = 4294967295, next = 4294967295, cache_slot = 4294967295, 
      lineno = 4294967295, num_args = 4294967295, fe_pos = 4294967295, fe_iter_idx = 4294967295}}, h = 0, key = 0x0}
//第0个元素内容foo
(gdb) p *struc.value.arr.arData[0].val.value.str.val@3
$12 = "foo"

//第1个元素h=9223372036854953478
(gdb) p struc.value.arr.arData[1]
$13 = {val = {value = {lval = 140737345758560, dval = 6.9533487626185766e-310, counted = 0x7ffff7802560, 
      str = 0x7ffff7802560, arr = 0x7ffff7802560, obj = 0x7ffff7802560, res = 0x7ffff7802560, ref = 0x7ffff7802560, 
      ast = 0x7ffff7802560, zv = 0x7ffff7802560, ptr = 0x7ffff7802560, ce = 0x7ffff7802560, func = 0x7ffff7802560, ww = {
        w1 = 4152370528, w2 = 32767}}, u1 = {v = {type = 6 '\006', type_flags = 0 '\000', const_flags = 0 '\000', 
        reserved = 0 '\000'}, type_info = 6}, u2 = {var_flags = 4294967295, next = 4294967295, cache_slot = 4294967295, 
      lineno = 4294967295, num_args = 4294967295, fe_pos = 4294967295, fe_iter_idx = 4294967295}}, h = 9223372036854953478, 
  key = 0x7ffff7802540}
//第一个元素内容为bar
(gdb) p *struc.value.arr.arData[1].val.value.str.val@3
$14 = "bar"
//第一个元素key为a
(gdb) p *struc.value.arr.arData[1].key
$16 = {gc = {refcount = 0, u = {v = {type = 6 '\006', flags = 2 '\002', gc_info = 0}, type_info = 518}}, 
  h = 9223372036854953478, len = 1, val = "a"}

下面来看看索引区

/* 第0个元素, h=0，0|-8= -8, 所以index为-8
 * 查看索引数组第8个位置，存储的索引为0
 */
(gdb) p ((uint32_t *)struc.value.arr.arData)[-8]
$17 = 0
/* 第1个元素, h=9223372036854953478, 9223372036854953478|-8 = -2, 所以index为-2
 * 查看索引数组第2个位置，存储的索引为1
 */
(gdb) p ((uint32_t *)struc.value.arr.arData)[-2]
$18 = 1

3. 一些启示

  1. 以后对字串进行hash，除了md5，还可以考虑time33
  2. 数组扩容和packed array转换为hash array时会触发rehash，这是个耗费cpu的操作。
  3. 当数组特别大时，要小心扩容的边界，在边界上，多出一个元素，就可能让你的内存增大一倍。
上一篇 下一篇

猜你喜欢

热点阅读