**按圖索驥。** PHP中使用最為頻繁的數據類型非字符串和數組莫屬，PHP比較容易上手也得益于非常靈活的數組類型。在開始詳細介紹這些數據類型之前有必要介紹一下哈希表(HashTable)。 哈希表是PHP實現中尤為關鍵的數據結構。 哈希表在實踐中使用的非常廣泛，例如編譯器通常會維護的一個符號表來保存標記，很多高級語言中也顯式的支持哈希表。哈希表通常提供查找(Search)，插入(Insert)，刪除(Delete)等操作，這些操作在最壞的情況下和鏈表的性能一樣為O(n)。不過通常并不會這么壞，合理設計的哈希算法能有效的避免這類情況，通常哈希表的這些操作時間復雜度為O(1)。這也是它被鐘愛的原因。 正是因為哈希表在使用上的便利性及效率上的表現，目前大部分動態語言的實現中都使用了哈希表。 ### 基本概念 為了方便讀者閱讀后面的內容，這里列舉一下HashTable實現中出現的基本概念。哈希表是一種通過哈希函數，將特定的鍵映射到特定值的一種數據結構，它維護鍵和值之間一一對應關系。 - 鍵(key)：用于操作數據的標示，例如PHP數組中的索引，或者字符串鍵等等。 - 槽(slot/bucket)：哈希表中用于保存數據的一個單元，也就是數據真正存放的容器。 - 哈希函數(hash function)：將key映射(map)到數據應該存放的slot所在位置的函數。 - 哈希沖突(hash collision)：哈希函數將兩個不同的key映射到同一個索引的情況。 哈希表可以理解為數組的擴展或者關聯數組，數組使用數字下標來尋址，如果關鍵字(key)的范圍較小且是數字的話，我們可以直接使用數組來完成哈希表，而如果關鍵字范圍太大，如果直接使用數組我們需要為所有可能的key申請空間。很多情況下這是不現實的。即使空間足夠，空間利用率也會很低，這并不理想。同時鍵也可能并不是數字，在PHP中尤為如此，所以人們使用一種映射函數(哈希函數)來將key映射到特定的域中： h(key) -> index 通過合理設計的哈希函數，我們就能將key映射到合適的范圍，因為我們的key空間可以很大(例如字符串key)，在映射到一個較小的空間中時可能會出現兩個不同的key映射被到同一個index上的情況，這就是我們所說的出現了沖突。 目前解決hash沖突的方法主要有兩種：鏈接法和開放尋址法。 ### 沖突解決 #### 鏈接法 鏈接法通過使用一個鏈表來保存slot值的方式來解決沖突，也就是當不同的key映射到一個槽中的時候使用鏈表來保存這些值。所以使用鏈接法是在最壞的情況下，也就是所有的key都映射到同一個槽中了，這樣哈希表就退化成了一個鏈表，這樣的話操作鏈表的時間復雜度則成了O(n)，這樣哈希表的性能優勢就沒有了，所以選擇一個合適的哈希函數是最為關鍵的。 由于目前大部分的編程語言的哈希表實現都是開源的，大部分語言的哈希算法都是公開的算法，雖然目前的哈希算法都能良好的將key進行比較均勻的分布，而這個假使的前提是key是隨機的，正是由于算法的確定性，這就導致了別有用心的黑客能利用已知算法的可確定性來構造一些特殊的key，讓這些key都映射到同一個槽位導致哈希表退化成單鏈表，導致程序的性能急劇下降，從而造成一些應用的吞吐能力急劇下降，尤其是對于高并發的應用影響很大，通過大量類似的請求可以讓服務器遭受DoS(服務拒絕攻擊)，這個問題一直就存在著，只是最近才被各個語言重視起來。 哈希沖突攻擊利用的哈希表最根本的弱點是：**開源算法和哈希實現的確定性以及可預測性**，這樣攻擊者才可以利用特殊構造的key來進行攻擊。要解決這個問題的方法則是讓攻擊者無法輕易構造能夠進行攻擊的key序列。 > 在筆者編寫這節內容的時候PHP語言也采取了相應的措施來防止這類的攻擊，PHP采用的是一種 治標不治本的做法: [限制用戶提交數據字段數量](http://cn2.php.net/manual/en/info.configuration.php#ini.max-input-vars) 這樣可以避免大部分的攻擊，不過應用程序通常會有很多的數據輸入方式，比如，SOAP，REST等等， 比如很多應用都會接受用戶傳入的JSON字符串，在執行json_decode()的時候也可能會遭受攻擊。 所以最根本的解決方法是讓哈希表的碰撞key序列無法輕易的構造，目前PHP中還沒有引入不增加額外的復雜性情況下的完美解決方案。 目前PHP中HashTable的哈希沖突解決方法就是鏈接法。 #### 開放尋址法 通常還有另外一種解決沖突的方法：開放尋址法。使用開放尋址法是槽本身直接存放數據，在插入數據時如果key所映射到的索引已經有數據了，這說明發生了沖突，這是會尋找下一個槽，如果該槽也被占用了則繼續尋找下一個槽，直到尋找到沒有被占用的槽，在查找時也使用同樣的策略來進行。 由于開放尋址法處理沖突的時候占用的是其他槽位的空間,這可能會導致后續的key在插入的時候更加容易出現哈希沖突，所以采用開放尋址法的哈希表的裝載因子不能太高，否則容易出現性能下降。 > _裝載因子_是哈希表保存的元素數量和哈希表容量的比，通常采用鏈接法解決沖突的哈希表的裝載 因子最好不要大于1，而采用開放尋址法的哈希表最好不要大于0.5。 ### 哈希表的實現 在了解到哈希表的原理之后要實現一個哈希表也很容易，主要需要完成的工作只有三點： 1. 實現哈希函數 1. 沖突的解決 1. 操作接口的實現 #### 數據結構 首先我們需要一個容器來保存我們的哈希表，哈希表需要保存的內容主要是保存進來的的數據，同時為了方便的得知哈希表中存儲的元素個數，需要保存一個大小字段，第二個需要的就是保存數據的容器了。作為實例，下面將實現一個簡易的哈希表。基本的數據結構主要有兩個，一個用于保存哈希表本身，另外一個就是用于實際保存數據的單鏈表了，定義如下： typedef struct _Bucket { char *key; void *value; struct _Bucket *next; } Bucket; ? typedef struct _HashTable { int size; int elem_num; Bucket** buckets; } HashTable; 上面的定義和PHP中的實現類似，為了便于理解裁剪了大部分無關的細節，在本節中為了簡化，key的數據類型為字符串，而存儲的數據類型可以為任意類型。 Bucket結構體是一個單鏈表，這是為了解決多個key哈希沖突的問題，也就是前面所提到的的鏈接法。當多個key映射到同一個index的時候將沖突的元素鏈接起來。 #### 哈希函數實現 哈希函數需要盡可能的將不同的key映射到不同的槽(slot或者bucket)中，首先我們采用一種最為簡單的哈希算法實現：將key字符串的所有字符加起來，然后以結果對哈希表的大小取模，這樣索引就能落在數組索引的范圍之內了。 static int hash_str(char *key) { int hash = 0; ? char *cur = key; ? while(*(cur++) != '\0') { hash += *cur; } ? return hash; } ? // 使用這個宏來求得key在哈希表中的索引 #define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size) 這個哈希算法比較簡單，它的效果并不好，在實際場景下不會使用這種哈希算法，例如PHP中使用的是稱為[DJBX33A](http://blog.csdn.net/zuiaituantuan/archive/2010/12/06/6057586.aspx)算法，[這里](http://blog.minidx.com/2008/01/27/446.html)列舉了Mysql，OpenSSL等開源軟件使用的哈希算法，有興趣的讀者可以前往參考。 有興趣的讀者可以運行本小節實現的哈希表實現,在輸出日志中將看到很多的哈希沖突,這是本例中使用的哈希算法過于簡單造成的. #### 操作接口的實現 為了操作哈希表，實現了如下幾個操作接口函數： int hash_init(HashTable *ht); // 初始化哈希表 int hash_lookup(HashTable *ht, char *key, void **result); // 根據key查找內容 int hash_insert(HashTable *ht, char *key, void *value); // 將內容插入到哈希表中 int hash_remove(HashTable *ht, char *key); // 刪除key所指向的內容 int hash_destroy(HashTable *ht); 下面以初始化、插入和獲取操作函數為例： int hash_init(HashTable *ht) { ht->size = HASH_TABLE_INIT_SIZE; ht->elem_num = 0; ht->buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *)); ? if(ht->buckets == NULL) return FAILED; ? LOG_MSG("[init]\tsize: %i\n", ht->size); ? return SUCCESS; } 初始化的主要工作是為哈希表申請存儲空間，函數中使用calloc函數的目的是確保數據存儲的槽為都初始化為0，以便后續在插入和查找時確認該槽為是否被占用。 int hash_insert(HashTable *ht, char *key, void *value) { // check if we need to resize the hashtable resize_hash_table_if_needed(ht); ? int index = HASH_INDEX(ht, key); ? Bucket *org_bucket = ht->buckets[index]; Bucket *tmp_bucket = org_bucket; ? // check if the key exits already while(tmp_bucket) { if(strcmp(key, tmp_bucket->key) == 0) { LOG_MSG("[update]\tkey: %s\n", key); tmp_bucket->value = value; ? return SUCCESS; } ? tmp_bucket = tmp_bucket->next; } ? Bucket *bucket = (Bucket *)malloc(sizeof(Bucket)); ? bucket->key = key; bucket->value = value; bucket->next = NULL; ? ht->elem_num += 1; ? if(org_bucket != NULL) { LOG_MSG("[collision]\tindex:%d key:%s\n", index, key); bucket->next = org_bucket; } ? ht->buckets[index]= bucket; ? LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n", index, key, ht->elem_num); ? return SUCCESS; } 上面這個哈希表的插入操作比較簡單，簡單的以key做哈希，找到元素應該存儲的位置，并檢查該位置是否已經有了內容，如果發生碰撞則將新元素鏈接到原有元素鏈表頭部。 由于在插入過程中可能會導致哈希表的元素個數比較多，如果超過了哈希表的容量，則說明肯定會出現碰撞，出現碰撞則會導致哈希表的性能下降，為此如果出現元素容量達到容量則需要進行擴容。由于所有的key都進行了哈希，擴容后哈希表不能簡單的擴容，而需要重新將原有已插入的預算插入到新的容器中。 static void resize_hash_table_if_needed(HashTable *ht) { if(ht->size - ht->elem_num < 1) { hash_resize(ht); } } ? static int hash_resize(HashTable *ht) { // double the size int org_size = ht->size; ht->size = ht->size * 2; ht->elem_num = 0; ? LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size); ? Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *)); ? Bucket **org_buckets = ht->buckets; ht->buckets = buckets; ? int i = 0; for(i=0; i < org_size; ++i) { Bucket *cur = org_buckets[i]; Bucket *tmp; while(cur) { // rehash: insert again hash_insert(ht, cur->key, cur->value); ? // free the org bucket, but not the element tmp = cur; cur = cur->next; free(tmp); } } free(org_buckets); ? LOG_MSG("[resize] done\n"); ? return SUCCESS; } 哈希表的擴容首先申請一塊新的內存，大小為原來的2倍，然后重新將元素插入到哈希表中，讀者會發現擴容的操作的代價為O(n)，不過這個問題不大，因為只有在到達哈希表容量的時候才會進行。 在查找時也使用插入同樣的策略，找到元素所在的位置，如果存在元素，則將該鏈表的所有元素的key和要查找的key依次對比， 直到找到一致的元素，否則說明該值沒有匹配的內容。 int hash_lookup(HashTable *ht, char *key, void **result) { int index = HASH_INDEX(ht, key); Bucket *bucket = ht->buckets[index]; ? if(bucket == NULL) goto failed; ? while(bucket) { if(strcmp(bucket->key, key) == 0) { LOG_MSG("[lookup]\t found %s\tindex:%i value: %p\n", key, index, bucket->value); *result = bucket->value; ? return SUCCESS; } ? bucket = bucket->next; } ? failed: LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key); return FAILED; } PHP中數組是基于哈希表實現的，依次給數組添加元素時，元素之間是有先后順序的，而這里的哈希表在物理位置上顯然是接近平均分布的，這樣是無法根據插入的先后順序獲取到這些元素的，在PHP的實現中Bucket結構體還維護了另一個指針字段來維護元素之間的關系。具體內容在后一小節PHP中的HashTable中進行詳細說明。上面的例子就是PHP中實現的一個精簡版。 > 本小節的HashTable實例完整代碼可以在$TIPI_ROOT/book/sample/chapt03/03-01-01-hashtable目錄中找到。 或者在github上瀏覽: [https://github.com/reeze/tipi/tree/master/book/sample/chapt03/03-01-01-hashtable](#) ### 參考文獻 - 《Data.Structures.and.Algorithm.Analysis.in.C》 - 《算法導論: 第二版》