# 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)