# 8.1 使用HashTable与{数组} # 8.1 使用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能够包容各种类型的数据，从小小的标量，到复杂的PHP5中实现的类等复合数据。本章接下来的内容，我们将详细的研究如何使用zend内置的API来操作HashTable这个数据结构。 ## links - 8 [使用HashTable与{数组}](8.html) - 8.2 [操作HashTable的API](8.2.html)