[ 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) {
        /* 链表中还没有任何元素 */
        people = last_person = person;
        return;
    }
    /* 将链表最后一个元素指向person */
    last_person->next = person;

    /* 更新链表末尾 */
    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)
    {
            /* 链表中还没有任何元素 */
            people = last_person = person;
            person->prev = NULL;
            return;
    }
    /* 将链表最后一个元素指向person，同时将person上一个元素指向当前最后一个元素 */
    last_person->next = person;
    person->prev = last_person;

    /* 更新列表末尾 */
    last_person = person;
}

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

// 单向链表删除节点元素
void name_remove(namelist *person)
{
    namelist *p;
    // 如果删除元素是链表第一个元素
    if (person == people) {
        // 链表首元素后移
        people = person->next;
        // 同时删除元素也是最后一个元素，将最后一个元素置为NULL
        if (last_person == person) {
            last_person = NULL;
        }
        return;
    }
    /* 循环遍历链表搜索被删除元素的前一个元素 */
    p = people;
    while (p) {
        if (p->next == person) {
            // 将被删除元素的前一个元素的下一个元素指针指向被删除元素的下一个元素
            p->next = person->next;
            // 如果是最后一个元素的话，更新链表末尾节点
            if (last_person == person) {
                last_person = p;
            }
            return;
        }
        p = p->next;
    }
    /* 在链表中没有找到 */
}

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

// 双向链表删除节点元素
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 引擎中 HashTable 的元素其实是指针，这个改进使得 HashTable 能够包容各种类型的数据 —— 从简单的标量，到复杂的 PHP 5 中实现的类等复合数据。本章接下来的内容将详细研究如何使用 Zend 内置的 API 来操作 HashTable 这个数据结构。