[ PHP 内核与扩展开发系列] Array 与 HashTable：数组与链表

内容简介：[ PHP 内核与扩展开发系列] Array 与 HashTable：数组与链表

我们在评选各种数据结构时，往往会考虑我们需要处理的数据规模以及需要的性能。下面让我们简要的看一下看 C 语言中数组和链表的一些事情。

数组

作者这里用的不是 Array，而是 Vector，可能指的是 C++ 里的 Vector，它与数组几乎是完全一样的，唯一的不同便是可以实现动态存储。本节下文都是用数组一词代替之，请各位注意。数组是内存中一块连续的区域，其每一个元素都具有一个唯一的下标值。

int a[3];
a[0]=1;
a[2]=3;

不仅是整数，其它类型的变量也可以保存在数组中，比如我们上一章用到的 zend_get_parameters_array_ex() ，便把很多 zval** 类型的变量保存到一个数组里，为了使其正常工作，我们提前向系统申请了相应大小的内存空间。

zval ***args = safe_emalloc(ZEND_NUM_ARGS(), sizeof(zval**), 0);

这里我们仍然可以用一个整数来当作下标去数组中取出我们想要的数据，就像 var_dump() 的实现中通过 args[i] 来获取参数并把它传递给 php_var_dump() 函数那样。使用数组最大的好处便是速度！读写都可以在 O(1) 内完成，因为它每个元素的大小都是一致的，只要知道下标，便可以瞬间计算出其对应的元素在内存中的位置，从而直接取出或者写入。

链表

链表也是一种经常被使用的一种数据结构。链表中的每一个元素都至少有两个元素，一个指向它的下一个元素，一个用来存放它自己的数据，就像下面定义的那样：

typedef struct _namelist namelist;
struct _namelist
{
    struct _namelist *next;
    char *name;
};

我们可以声明一个其类型的元素：

static namelist *people;

假设每一个元素都代表一个人，元素中的 name 属性便是这个人的名字，我们通过这样的语句来得到它： people->name ，第二个属性指向后面的一个元素，那我们便可以这样来访问下一个人的名字： people->next->name ，或者下下一个人的名字： people->next->next->name ，依次类推，直到 next 的值是 NULL，代表结束。

// 通过一个循环来遍历这个链表中的所有人~
void name_show(namelist *p)
{
    while (p)
    {
            printf("Name: %s\n", p->name);
            p = p->next;
    }
}

链表可以被用来实现 FIFO 模式，达到先进者先出的目的！

static namelist *people = NULL, *last_person = NULL;
void name_add(namelist *person)
{
    person->next = NULL;
    if (!last_person) {
        /* No one in the list yet */
        people = last_person = person;
        return;
    }
    /* Append new person to the end of the list */
    last_person->next = person;

    /* Update the list tail */
    last_person = person;
}
namelist *name_pop(void)
{
    namelist *first_person = people;
    if (people) {
        people = people->next;
    }
    return first_person;
}

这样，我们便可以随意的向这个链表中添加或者删除数据，而不像数组那样，谨慎的考虑是否越界等问题。上面实现的结构的学名叫做单向链表，也有地方叫单链表。它有一个致命的缺点，就是我们在插入或者读取某条数据的时候，都需要从这个链表的开始，一个个元素的向下寻找，直到找到这个元素为止。如果链表中的元素比较多，那它很容易成为我们程序中的 CPU 消耗大户，进而引起性能问题。为了解决这个问题，先人们发明了双向链表：

typedef struct _namelist namelist;
struct
{
    namelist *next, *prev;
    char *name;
} _namelist;

改动其实不大，就是在每个元素中都添加了一个 prev 属性，用来指向它的上一个元素。

void name_add(namelist *person)
{
    person->next = NULL;
    if (!last_person)
    {
            /* No one in the list yet */
            people = last_person = person;
            person->prev = NULL;
            return;
    }
    /* Append new person to the end of the list */
    last_person ->next = person;
    person->prev = last_person;

    /* Update the list tail */
    last_person = person;
}

单单通过上面的程序你还体会不到它的好处，但是设想一下，如果现在你有这个链表中其中一个元素的地址，并且想把它从链表中删除，那我们该怎么做呢？如果是单向链表的话，我们只能这样做：

void name_remove(namelist *person)
{
    namelist *p;
    if (person == people) {
        /* Happens to be the first person in the list */
        people = person->next;
        if (last_person == person) {
            /* Also happens to be the last person */
            last_person = NULL;
        }
        return;
    }
    /* Search for prior person */
    p = people;
    while (p) {
        if (p->next == person) {
            /* unlink */
            p->next = person->next;
            if (last_person == person) {
                /* This was the last element */
                last_person = p;
            }
            return;
        }
        p = p->next;
    }
    /* Not found in list */
}

现在让我们来看看双向链表是怎样来处理这个问题的：

void name_remove(namelist *person)
{
    if (people == person) {
        people = person->next;
    }
    if (last_person == person) {
        last_person = person->prev;
    }
    if (person->prev) {    
        person->prev->next = person->next;
    }
    if (person->next) {
        person->next->prev = person->prev;
    }
}

对元素的遍历查找不见了，取而代之的是一个 O(1) 的运算，这将极大的提升我们程序的性能。

王者归来：HashTable 才是我们的银弹！

也许你已经非常喜欢使用数组或者链表了，但我还是要向你推荐一种威力极大的数据结构，有了它之后，你可能会立即抛弃前两者，它就是 HashTable。HashTable 既具有双向链表的优点，同时具有能与数组匹敌的操作性能，这个数据结构几乎是 PHP 内核实现的基础，我们在内核代码的任何地方都发现它的痕迹。

第二章我们接触过，所有的用户端定义的变量保存在一个符号表里，而这个符号表其实就是一个 HashTable，它的每一个元素都是一个 zval* 类型的变量。不仅如此，保存用户定义的函数、类、资源等的容器都是以HashTable 的形式在内核中实现的。Zend Engine 中 HashTable 的元素其实是指针，这个改进使得HashTable 能够包容各种类型的数据 —— 从小小的标量，到复杂的 PHP 5 中实现的类等复合数据。本章接下来的内容，我们将详细的研究如何使用 Zend 内置的 API 来操作 HashTable 这个数据结构。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• C语言指针数组和数组指针
• 数组 – 如何在Swift中将数组拆分成两半？
• 菜鸡的算法修炼：数组（旋转数组的最小数字）
• 交换数组元素，使得数组的和的差最小
• JS数组专题1️⃣ ➖ 数组扁平化
• 算法-计算小数组在大数组中的索引

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。