程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> PHP綜合 >> php內核解析:PHP中的哈希表

php內核解析:PHP中的哈希表

編輯:PHP綜合

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)。 所以選擇一個合適的哈希函數是最為關鍵的。目前PHP中HashTable的實現就是采用這種方式來解決沖突的。
開放尋址法:通常還有另外一種解決沖突的方法:開放尋址法。使用開放尋址法是槽本身直接存放數據, 在插入數據時如果key所映射到的索引已經有數據了,這說明發生了沖突,這是會尋找下一個槽, 如果該槽也被占用了則繼續尋找下一個槽,直到尋找到沒有被占用的槽,在查找時也使用同樣的策律來進行。

哈希表的實現

在了解到哈希表的原理之後要實現一個哈希表也很容易,主要需要完成的工作只有三點:
實現哈希函數
沖突的解決
操作接口的實現
首先我們需要一個容器來保存我們的哈希表,哈希表需要保存的內容主要是保存進來的的數據, 同時為了方便的得知哈希表中存儲的元素個數,需要保存一個大小字段, 第二個需要的就是保存數據的容器了。作為實例,下面將實現一個簡易的哈希表。基本的數據結構主要有兩個, 一個用於保存哈希表本身,另外一個就是用於實際保存數據的單鏈表了,定義如下:

復制代碼 代碼如下:
typedef struct _Bucket
{
 char *key;
 void *value;
 struct _Bucket *next;

} Bucket;

typedef struct _HashTable
{
 int size;
 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算法, 這裡列舉了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_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); // 找到key所映射到的索引

Bucket *org_bucket = ht->buckets[index];
 Bucket *bucket = (Bucket *)malloc(sizeof(Bucket)); // 為新元素申請空間

bucket->key = strdup(key);
 // 將值內容保存進來, 這裡只是簡單的將指針指向要存儲的內容,而沒有將內容復制。
 bucket->value = value;

LOG_MSG("Insert data p: %p\n", value);

ht->elem_num += 1; // 記錄一下現在哈希表中的元素個數

if(org_bucket != NULL) { // 發生了碰撞,將新元素放置在鏈表的頭部
 LOG_MSG("Index collision found with org hashtable: %p\n", org_bucket);
 bucket->next = org_bucket;
 }

ht->buckets[index]= bucket;

LOG_MSG("Element inserted at index %i, now we have: %i elements\n",
 index, ht->elem_num);

return SUCCESS;
 }
 

上面這個哈希表的插入操作比較簡單,簡單的以key做哈希,找到元素應該存儲的位置,並檢查該位置是否已經有了內容, 如果發生碰撞則將新元素鏈接到原有元素鏈表頭部。在查找時也按照同樣的策略,找到元素所在的位置,如果存在元素, 則將該鏈表的所有元素的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) return FAILED;

 // 查找這個鏈表以便找到正確的元素,通常這個鏈表應該是只有一個元素的,也就不用多次
 // 循環。要保證這一點需要有一個合適的哈希算法,見前面相關哈希函數的鏈接。
 while(bucket)
 {
 if(strcmp(bucket->key, key) == 0)
 {
 LOG_MSG("HashTable found key in index: %i with key: %s value: %p\n",
 index, key, bucket->value);
 *result = bucket->value;
 return SUCCESS;
 }

 bucket = bucket->next;
 }

 LOG_MSG("HashTable lookup missed the key: %s\n", key);
 return FAILED;
}

PHP中數組是基於哈希表實現的,依次給數組添加元素時,元素之間是有先後順序的,而這裡的哈希表在物理位置上顯然是接近平均分布的, 這樣是無法根據插入的先後順序獲取到這些元素的,在PHP的實現中Bucket結構體還維護了另一個指針字段來維護元素之間的關系。 具體內容在後一小節PHP中的HashTable中進行詳細說明。上面的例子就是PHP中實現的一個精簡版。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved