PHP中的哈希表是什么-創(chuàng)新互聯(lián)

本篇內(nèi)容主要講解“PHP中的哈希表是什么”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“PHP中的哈希表是什么”吧!

創(chuàng)新互聯(lián)專(zhuān)注于茂南網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。熱誠(chéng)為您提供茂南營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，茂南網(wǎng)站制作、茂南網(wǎng)頁(yè)設(shè)計(jì)、茂南網(wǎng)站官網(wǎng)定制、小程序開(kāi)發(fā)服務(wù)，打造茂南網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供茂南網(wǎng)站排名全網(wǎng)營(yíng)銷(xiāo)落地服務(wù)。

PHP中使用最為頻繁的數(shù)據(jù)類(lèi)型非字符串和數(shù)組莫屬，PHP比較容易上手也得益于非常靈活的數(shù)組類(lèi)型。在開(kāi)始詳細(xì)介紹這些數(shù)據(jù)類(lèi)型之前有必要介紹一下哈希表(HashTable)。哈希表是PHP實(shí)現(xiàn)中尤為關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。

哈希表在實(shí)踐中使用的非常廣泛，例如編譯器通常會(huì)維護(hù)的一個(gè)符號(hào)表來(lái)保存標(biāo)記，很多高級(jí)語(yǔ)言中也顯式的支持哈希表。哈希表通常提供查找(Search)，插入(Insert)，刪除(Delete)等操作，這些操作在最壞的情況下和鏈表的性能一樣為O(n)。不過(guò)通常并不會(huì)這么壞，合理設(shè)計(jì)的哈希算法能有效的避免這類(lèi)情況，通常哈希表的這些操作時(shí)間復(fù)雜度為O(1)。這也是它被鐘愛(ài)的原因。
正是因?yàn)楣１碓谑褂蒙系谋憷约靶噬系谋憩F(xiàn)，目前大部分動(dòng)態(tài)語(yǔ)言的實(shí)現(xiàn)中都使用了哈希表。

為了方便讀者閱讀后面的內(nèi)容，這里提前列舉一下HashTable實(shí)現(xiàn)中出現(xiàn)的基本概念。哈希表是一種通過(guò)哈希函數(shù)，將特定的鍵映射到特定值的一種數(shù)據(jù)結(jié)構(gòu)，它維護(hù)鍵和值之間一一對(duì)應(yīng)關(guān)系。
鍵(key)：用于操作數(shù)據(jù)的標(biāo)示，例如PHP數(shù)組中的索引，或者字符串鍵等等。

槽(slot/bucket)：哈希表中用于保存數(shù)據(jù)的一個(gè)單元，也就是數(shù)據(jù)真正存放的容器。

哈希函數(shù)(hash function)：將key映射(map)到數(shù)據(jù)應(yīng)該存放的slot所在位置的函數(shù)。

哈希沖突(hash collision)：哈希函數(shù)將兩個(gè)不同的key映射到同一個(gè)索引的情況。

哈希表可以理解為數(shù)組的擴(kuò)展或者關(guān)聯(lián)數(shù)組，數(shù)組使用數(shù)字下標(biāo)來(lái)尋址，如果關(guān)鍵字(key)的范圍較小且是數(shù)字的話(huà)，我們可以直接使用數(shù)組來(lái)完成哈希表，而如果關(guān)鍵字范圍太大，如果直接使用數(shù)組我們需要為所有可能的key申請(qǐng)空間。很多情況下這是不現(xiàn)實(shí)的。即使空間足夠，空間利用率也會(huì)很低，這并不理想。同時(shí)鍵也可能并不是數(shù)字，在PHP中尤為如此，所以人們使用一種映射函數(shù)(哈希函數(shù))來(lái)將key映射到特定的域中：

復(fù)制代碼代碼如下:

h(key) -> index

通過(guò)合理設(shè)計(jì)的哈希函數(shù)，我們就能將key映射到合適的范圍，因?yàn)槲覀兊膋ey空間可以很大(例如字符串key)，在映射到一個(gè)較小的空間中時(shí)可能會(huì)出現(xiàn)兩個(gè)不同的key映射被到同一個(gè)index上的情況，這就是我們所說(shuō)的出現(xiàn)了沖突。目前解決hash沖突的方法主要有兩種：鏈接法和開(kāi)放尋址法。

沖突解決

鏈接法：鏈接法通過(guò)使用一個(gè)鏈表來(lái)保存slot值的方式來(lái)解決沖突，也就是當(dāng)不同的key映射到一個(gè)槽中的時(shí)候使用鏈表來(lái)保存這些值。所以使用鏈接法是在最壞的情況下，也就是所有的key都映射到同一個(gè)槽中了，操作鏈表的時(shí)間復(fù)雜度為O(n)。所以選擇一個(gè)合適的哈希函數(shù)是最為關(guān)鍵的。目前PHP中HashTable的實(shí)現(xiàn)就是采用這種方式來(lái)解決沖突的。
開(kāi)放尋址法：通常還有另外一種解決沖突的方法：開(kāi)放尋址法。使用開(kāi)放尋址法是槽本身直接存放數(shù)據(jù)，在插入數(shù)據(jù)時(shí)如果key所映射到的索引已經(jīng)有數(shù)據(jù)了，這說(shuō)明發(fā)生了沖突，這是會(huì)尋找下一個(gè)槽，如果該槽也被占用了則繼續(xù)尋找下一個(gè)槽，直到尋找到?jīng)]有被占用的槽，在查找時(shí)也使用同樣的策律來(lái)進(jìn)行。

哈希表的實(shí)現(xiàn)

在了解到哈希表的原理之后要實(shí)現(xiàn)一個(gè)哈希表也很容易，主要需要完成的工作只有三點(diǎn)：
實(shí)現(xiàn)哈希函數(shù)
沖突的解決
操作接口的實(shí)現(xiàn)
首先我們需要一個(gè)容器來(lái)保存我們的哈希表，哈希表需要保存的內(nèi)容主要是保存進(jìn)來(lái)的的數(shù)據(jù)，同時(shí)為了方便的得知哈希表中存儲(chǔ)的元素個(gè)數(shù)，需要保存一個(gè)大小字段，第二個(gè)需要的就是保存數(shù)據(jù)的容器了。作為實(shí)例，下面將實(shí)現(xiàn)一個(gè)簡(jiǎn)易的哈希表。基本的數(shù)據(jù)結(jié)構(gòu)主要有兩個(gè)，一個(gè)用于保存哈希表本身，另外一個(gè)就是用于實(shí)際保存數(shù)據(jù)的單鏈表了，定義如下：

復(fù)制代碼代碼如下:

typedef struct _Bucket
{
char *key;
void *value;
struct _Bucket *next;

} Bucket;

typedef struct _HashTable
{
int size;
Bucket* buckets;
} HashTable;

上面的定義和PHP中的實(shí)現(xiàn)類(lèi)似，為了便于理解裁剪了大部分無(wú)關(guān)的細(xì)節(jié)，在本節(jié)中為了簡(jiǎn)化， key的數(shù)據(jù)類(lèi)型為字符串，而存儲(chǔ)的數(shù)據(jù)類(lèi)型可以為任意類(lèi)型。
Bucket結(jié)構(gòu)體是一個(gè)單鏈表，這是為了解決多個(gè)key哈希沖突的問(wèn)題，也就是前面所提到的的鏈接法。當(dāng)多個(gè)key映射到同一個(gè)index的時(shí)候?qū)_突的元素鏈接起來(lái)。
哈希函數(shù)需要盡可能的將不同的key映射到不同的槽(slot或者bucket)中，首先我們采用一種最為簡(jiǎn)單的哈希算法實(shí)現(xiàn)：將key字符串的所有字符加起來(lái)，然后以結(jié)果對(duì)哈希表的大小取模，這樣索引就能落在數(shù)組索引的范圍之內(nèi)了。

復(fù)制代碼代碼如下:

static int hash_str(char *key)
{
int hash = 0;

char *cur = key;

while(*(cur++) != '\0') {
hash += *cur;
}

return hash;
}

// 使用這個(gè)宏來(lái)求得key在哈希表中的索引
#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)

這個(gè)哈希算法比較簡(jiǎn)單，它的效果并不好，在實(shí)際場(chǎng)景下不會(huì)使用這種哈希算法，例如PHP中使用的是稱(chēng)為DJBX33A算法，這里列舉了Mysql，OpenSSL等開(kāi)源軟件使用的哈希算法，有興趣的讀者可以前往參考。
操作接口的實(shí)現(xiàn)
為了操作哈希表，實(shí)現(xiàn)了如下幾個(gè)操作函數(shù)：

復(fù)制代碼代碼如下:

int hash_init(HashTable *ht); // 初始化哈希表
int hash_lookup(HashTable *ht, char *key, void **result); // 根據(jù)key查找內(nèi)容
int hash_insert(HashTable *ht, char *key, void *value); // 將內(nèi)容插入到哈希表中
int hash_remove(HashTable *ht, char *key); // 刪除key所指向的內(nèi)容
int hash_destroy(HashTable *ht);

下面以插入和獲取操作函數(shù)為例：

復(fù)制代碼代碼如下:

int hash_insert(HashTable *ht, char *key, void *value)
{
// check if we need to resize the hashtable
resize_hash_table_if_needed(ht); // 哈希表不固定大小，當(dāng)插入的內(nèi)容快占滿(mǎn)哈表的存儲(chǔ)空間
// 將對(duì)哈希表進(jìn)行擴(kuò)容，以便容納所有的元素

int index = HASH_INDEX(ht, key); // 找到key所映射到的索引

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

bucket->key = strdup(key);
// 將值內(nèi)容保存進(jìn)來(lái)，這里只是簡(jiǎn)單的將指針指向要存儲(chǔ)的內(nèi)容，而沒(méi)有將內(nèi)容復(fù)制。
bucket->value = value;

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

ht->elem_num += 1; // 記錄一下現(xiàn)在哈希表中的元素個(gè)數(shù)

if(org_bucket != NULL) { // 發(fā)生了碰撞，將新元素放置在鏈表的頭部
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;
}

上面這個(gè)哈希表的插入操作比較簡(jiǎn)單，簡(jiǎn)單的以key做哈希，找到元素應(yīng)該存儲(chǔ)的位置，并檢查該位置是否已經(jīng)有了內(nèi)容，如果發(fā)生碰撞則將新元素鏈接到原有元素鏈表頭部。在查找時(shí)也按照同樣的策略，找到元素所在的位置，如果存在元素，則將該鏈表的所有元素的key和要查找的key依次對(duì)比，直到找到一致的元素，否則說(shuō)明該值沒(méi)有匹配的內(nèi)容。

復(fù)制代碼代碼如下:

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;

// 查找這個(gè)鏈表以便找到正確的元素，通常這個(gè)鏈表應(yīng)該是只有一個(gè)元素的，也就不用多次
// 循環(huán)。要保證這一點(diǎn)需要有一個(gè)合適的哈希算法，見(jiàn)前面相關(guān)哈希函數(shù)的鏈接。
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中數(shù)組是基于哈希表實(shí)現(xiàn)的，依次給數(shù)組添加元素時(shí)，元素之間是有先后順序的，而這里的哈希表在物理位置上顯然是接近平均分布的，這樣是無(wú)法根據(jù)插入的先后順序獲取到這些元素的，在PHP的實(shí)現(xiàn)中Bucket結(jié)構(gòu)體還維護(hù)了另一個(gè)指針字段來(lái)維護(hù)元素之間的關(guān)系。具體內(nèi)容在后一小節(jié)PHP中的HashTable中進(jìn)行詳細(xì)說(shuō)明。上面的例子就是PHP中實(shí)現(xiàn)的一個(gè)精簡(jiǎn)版。

到此，相信大家對(duì)“PHP中的哈希表是什么”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)建站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！

網(wǎng)站名稱(chēng)：PHP中的哈希表是什么-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)鏈接：http://www.muchs.cn/article42/dsocec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、微信公眾號(hào)、定制開(kāi)發(fā)、虛擬主機(jī)、商城網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容