搜尋
首頁後端開發php教程PHP哈希表原理

PHP哈希表原理

Aug 21, 2017 am 10:15 AM
php原理哈希

簡介

幾乎每個C程式中都會使用到雜湊表。鑑於C語言只允許使用整數作為數組的鍵名,PHP 設計了哈希表,將字串的鍵名透過哈希演算法映射到大小有限的數組中。這樣無法避免的會產生碰撞,PHP 使用了鍊錶解決這個問題。

眾多哈希表的實作方式,無​​一完美。每個設計都著眼於某一個重點,有的減少了 CPU 使用率,有的更合理地使用內存,有的則能夠支持線程級的擴展。

實作雜湊表的方式之所以存在多樣性,是因為每種實作方式都只能在各自的關注點上提升,而無法面面俱到。

資料結構

開始介紹之前,我們需要事先宣告一些事情:

雜湊表的鍵名可能是字串或是整數。當是字串時,我們宣告類型為 zend_string;當是整數時,宣告為 zend_ulong。

哈希表的順序遵循表內元素的插入順序。

哈希表的容量是自動伸縮的。

在內部,哈希表的容量總是2的倍數。

哈希表中每個元素一定是 zval 類型的資料。

以下是 HashTable 的結構體

PHP

struct _zend_array {  
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    reserve)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

   

這個結構體佔56個位元組。

其中最重要的欄位是 arData,它是一個指向 Bucket 類型資料的指針,Bucket 結構定義如下:

typedef struct _Bucket {  
    zval              val;
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

   

Bucket 中不再使用指向一個 zval類型資料的指針,而是直接使用資料本身。因為在 PHP7 中,zval 不再使用堆分配,因為需要堆分配的資料會作為 zval 結構中的一個指標儲存。 (例如 PHP 的字串)。

下面是 arData 在記憶體中儲存的結構:

我們注意到所有的Bucket都是依序存放的。

插入元素

PHP 會保證陣列的元素按照插入的順序儲存。這樣當使用 foreach 循環陣列時,能夠依照插入的順序遍歷。假設我們有這樣的陣列:

$a = [9 => "foo", 2 => 42, []];
var_dump($a);
 
array(3) {  
    [9]=>
    string(3) "foo"
    [2]=>
    int(42)
    [10]=>
    array(0) {
    }
}

所有的資料在記憶體上都是相鄰的。

這樣做,處理雜湊表的迭代器的邏輯就變得相當簡單。只需要直接遍歷 arData 數組即可。遍歷記憶體中相鄰的數據,將會極大的利用 CPU 快取。因為 CPU 快取能夠讀取到整個 arData 的數據,存取每個元素將在微妙級。

size_t i;  
Bucket p;  
zval val;
 
for (i=0; i < ht->nTableSize; i++) {  
    p   = ht->arData[i];
    val = p.val;
    /* do something with val */
}

   

如你所見,資料會依序存放在 arData 中。為了實現這樣的結構,我們需要知道下一個可用的節點的位置。這個位置保存在陣列結構體中的 nNumUsed 欄位中。

每當新增一個新的資料時,我們儲存後,就會執行 ht->nNumUsed++。當 nNumUsed 值到達雜湊表所有元素的最大值(nNumOfElements)時,會觸發「壓縮或擴容」的演算法。

以下是將元素插入雜湊表的簡單實作範例:

idx = ht->nNumUsed++; /* take the next avalaible slot number */  
ht->nNumOfElements++; /* increment number of elements */  
/* ... */
p = ht->arData + idx; /* Get the bucket in that slot from arData */  
p->key = key; /* Affect it the key we want to insert at */  
/* ... */
p->h = h = ZSTR_H(key); /* save the hash of the current key into the bucket */  
ZVAL_COPY_VALUE(&p->val, pData); /* Copy the value into the bucket&#39;s value : add operation */

   

我們可以看到,插入時只會在 arData 陣列的結尾插入,而不會填入已經刪除的節點。

刪除元素

當刪除雜湊表中的一個元素時,雜湊表不會自動伸縮實際儲存的資料空間,而是設定了一個值為 UNDEF 的 zval,表示當前節點已經被刪除。

如下圖:

因此,在循環陣列元素時,需要特殊判斷空節點:

size_t i;  
Bucket p;  
zval val;
 
for (i=0; i < ht->nTableSize; i++) {  
    p   = ht->arData[i];
    val = p.val;
    if (Z_TYPE(val) == IS_UNDEF) { /* empty hole ? */
        continue; /* skip it */
    }
    /* do something with val */
}

   

即使是十分巨大的哈希表,循環每個節點並跳過那些刪除的節點也是非常快速的,這要歸功於 arData 的節點在記憶體中存放的位置總是相鄰的。

哈希定位元素

當我們得到一個字串的鍵名,我們必須使用哈希演算法計算得到哈希後的值,並且能夠透過哈希值索引找到 arData 中對應的那個元素。

我們無法直接使用雜湊後的值作為 arData 數組的索引,因為這樣就無法保證元素按照插入順序儲存。

舉例:如果我插入的鍵名先是 foo,然後是 bar,假設 foo 哈希後的結果是5,而 bar 哈希後的結果是3。如果我們將 foo 存在 arData[5],而 bar 存在 arData[3],這表示 bar 元素要在 foo 元素的前面,這和我們插入的順序正好是相反的。

所以,当我们通过算法哈希了键名后,我们需要一张 转换表,转换表保存了哈希后的结果与实际存储的节点的映射关系。

这里在设计的时候取了个巧:将转换表存储以 arData 起始指针为起点做镜面映射存储。这样,我们不需要额外的空间存储,在分配 arData 空间的同时也分配了转换表。

以下是有8个元素的哈希表 + 转换表的数据结构:

现在,当我们要访问 foo 所指的元素时,通过哈希算法得到值后按照哈希表分配的元素大小做取模,就能得到我们在转换表中存储的节点索引值。

如我们所见,转换表中的节点的索引与数组数据元素的节点索引是相反数的关系,nTableMask 等于哈希表大小的负数值,通过取模我们就能得到0到-7之间的数,从而定位到我们所需元素所在的索引值。综上,我们为 arData 分配存储空间时,需要使用 tablesize * sizeof(bucket) + tablesize * sizeof(uint32) 的计算方式计算存储空间大小。

在源码里也清晰的划分了两个区域:

#define HT_HASH_SIZE(nTableMask) (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))
#define HT_DATA_SIZE(nTableSize) ((size_t)(nTableSize) * sizeof(Bucket))
#define HT_SIZE_EX(nTableSize, nTableMask) (HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask)))
#define HT_SIZE(ht) HT_SIZE_EX((ht)->nTableSize, (ht)->nTableMask)
 
Bucket *arData;  
arData = emalloc(HT_SIZE(ht)); /* now alloc this */

我们将宏替换的结果展开:

(((size_t)(((ht)->nTableSize)) * sizeof(Bucket)) + (((size_t)(uint32_t)-(int32_t)(((ht)->nTableMask))) * sizeof(uint32_t)))

碰撞冲突

接下来我们看看如何解决哈希表的碰撞冲突问题。哈希表的键名可能会被哈希到同一个节点。所以,当我们访问到转换后的节点,我们需要对比键名是否我们查找的。如果不是,我们将通过 zval.u2.next 字段读取链表上的下一个数据。

注意这里的链表结构并没像传统链表一样在在内存中分散存储。我们直接读取 arData 整个数组,而不是通过堆(heap)获取内存地址分散的指针。

这是 PHP7 性能提升的一个重要点。数据局部性让 CPU 不必经常访问缓慢的主存储,而是直接从 CPU 的 L1 缓存中读取到所有的数据。

所以,我们看到向哈希表添加一个元素是这样操作的:

    idx = ht->nNumUsed++;
    ht->nNumOfElements++;
    if (ht->nInternalPointer == HT_INVALID_IDX) {
        ht->nInternalPointer = idx;
    }
    zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
    p = ht->arData + idx;
    p->key = key;
    if (!ZSTR_IS_INTERNED(key)) {
        zend_string_addref(key);
        ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
        zend_string_hash_val(key);
    }
    p->h = h = ZSTR_H(key);
    ZVAL_COPY_VALUE(&p->val, pData);
    nIndex = h | ht->nTableMask;
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

同样的规则也适用于删除元素:

#define HT_HASH_TO_BUCKET_EX(data, idx) ((data) + (idx))
#define HT_HASH_TO_BUCKET(ht, idx) HT_HASH_TO_BUCKET_EX((ht)->arData, idx)
 
h = zend_string_hash_val(key); /* get the hash from the key (assuming string key here) */  
nIndex = h | ht->nTableMask; /* get the translation table index */
 
idx = HT_HASH(ht, nIndex); /* Get the slot corresponding to that translation index */  
while (idx != HT_INVALID_IDX) { /* If there is a corresponding slot */  
    p = HT_HASH_TO_BUCKET(ht, idx); /* Get the bucket from that slot */
    if ((p->key == key) || /* Is it the right bucket ? same key pointer ? */
        (p->h == h && /* ... or same hash */
         p->key && /* and a key (string key based) */
         ZSTR_LEN(p->key) == ZSTR_LEN(key) && /* and same key length */
         memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) == 0)) { /* and same key content ? */
        _zend_hash_del_el_ex(ht, idx, p, prev); /* that&#39;s us ! delete us */
        return SUCCESS;
    }
    prev = p;
    idx = Z_NEXT(p->val); /* get the next corresponding slot from current one */
}
return FAILURE;

转换表和哈希表的初始化

HT_INVALID_IDX 作为一个特殊的标记,在转换表中表示:对应的数据节点没有有效的数据,直接跳过。

哈希表之所以能极大地减少那些创建时就是空值的数组的开销,得益于他的两步的初始化过程。当新的哈希表被创建时,我们只创建两个转换表节点,并且都赋予 HT_INVALID_IDX 标记。

#define HT_MIN_MASK ((uint32_t) -2)
#define HT_HASH_SIZE(nTableMask) (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))
#define HT_SET_DATA_ADDR(ht, ptr) do { (ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); } while (0)
 
static const uint32_t uninitialized_bucket[-HT_MIN_MASK] = {HT_INVALID_IDX, HT_INVALID_IDX};
 
/* hash lazy init */
ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)  
{
    /* ... */
    ht->nTableSize = zend_hash_check_size(nSize);
    ht->nTableMask = HT_MIN_MASK;
    HT_SET_DATA_ADDR(ht, &uninitialized_bucket);
    ht->nNumUsed = 0;
    ht->nNumOfElements = 0;
}

   

注意到这里不需要使用堆分配内存,而是使用静态的内存区域,这样更轻量。

然后,当第一个元素插入时,我们会完整的初始化哈希表,这时我们才创建所需的转换表的空间(如果不确定数组大小,则默认是8个元素)。这时,我们将使用堆分配内存。

#define HT_HASH_EX(data, idx) ((uint32_t*)(data))[(int32_t)(idx)]
#define HT_HASH(ht, idx) HT_HASH_EX((ht)->arData, idx)
 
(ht)->nTableMask = -(ht)->nTableSize;
HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT));  
memset(&HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask))

   

HT_HASH 宏能够使用负数偏移量访问转换表中的节点。哈希表的掩码总是负数,因为转换表的节点的索引值是 arData 数组的相反数。这才是C语言的编程之美:你可以创建无数的节点,并且不需要关心内存访问的性能问题。

以下是一个延迟初始化的哈希表结构:

哈希表的碎片化、重组和压缩

当哈希表填充满并且还需要插入元素时,哈希表必须重新计算自身的大小。哈希表的大小总是成倍增长。当对哈希表扩容时,我们会预分配 arBucket 类型的C数组,并且向空的节点中存入值为 UNDEF 的 zval。在节点插入数据之前,这里会浪费 (new_size – old_size) * sizeof(Bucket) 字节的空间。

如果一个有1024个节点的哈希表,再添加元素时,哈希表将会扩容到2048个节点,其中1023个节点都是空节点,这将消耗 1023 * 32 bytes = 32KB 的空间。这是 PHP 哈希表实现方式的缺陷,因为没有完美的解决方案。

编程就是一个不断设计妥协式的解决方案的过程。在底层编程中,就是对 CPU 还是内存的一次取舍。

哈希表可能全是 UNDEF 的节点。当我们插入许多元素后,又删除了它们,哈希表就会碎片化。因为我们永远不会向 arData 中间节点插入数据,这样我们就可能会看到很多 UNDEF 节点。

举个例子来说:

重组 arData 可以整合碎片化的数组元素。当哈希表需要被重组时,首先它会自我压缩。当它压缩之后,会计算是否需要扩容,如果需要的话,同样是成倍扩容。如果不需要,数据会被重新分配到已有的节点中。这个算法不会在每次元素被删除时运行,因为需要消耗大量的 CPU 计算。

以下是压缩后的数组:

压缩算法会遍历所有 arData 里的元素并且替换原来有值的节点为 UNDEF。如下所示:

Bucket *p;  
uint32_t nIndex, i;  
HT_HASH_RESET(ht);  
i = 0;  
p = ht->arData;
 
do {  
    if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
        uint32_t j = i;
        Bucket *q = p;
        while (++i < ht->nNumUsed) {
            p++;
            if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
                ZVAL_COPY_VALUE(&q->val, &p->val);
                q->h = p->h;
                nIndex = q->h | ht->nTableMask;
                q->key = p->key;
                Z_NEXT(q->val) = HT_HASH(ht, nIndex);
                HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
                if (UNEXPECTED(ht->nInternalPointer == i)) {
                    ht->nInternalPointer = j;
                }
                q++;
                j++;
            }
        }
        ht->nNumUsed = j;
        break;
    }
    nIndex = p->h | ht->nTableMask;
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
    p++;
} while (++i < ht->nNumUsed);

结语

到此,PHP 哈希表的实现基础已经介绍完毕,关于哈希表还有一些进阶的内容没有翻译,因为接下来我准备继续分享 PHP 内核的其他知识点,关于哈希表感兴趣的同学可以移步到原文。

以上是PHP哈希表原理的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
使用數據庫存儲會話的優點是什麼?使用數據庫存儲會話的優點是什麼?Apr 24, 2025 am 12:16 AM

使用數據庫存儲會話的主要優勢包括持久性、可擴展性和安全性。 1.持久性:即使服務器重啟,會話數據也能保持不變。 2.可擴展性:適用於分佈式系統,確保會話數據在多服務器間同步。 3.安全性:數據庫提供加密存儲,保護敏感信息。

您如何在PHP中實現自定義會話處理?您如何在PHP中實現自定義會話處理?Apr 24, 2025 am 12:16 AM

在PHP中實現自定義會話處理可以通過實現SessionHandlerInterface接口來完成。具體步驟包括:1)創建實現SessionHandlerInterface的類,如CustomSessionHandler;2)重寫接口中的方法(如open,close,read,write,destroy,gc)來定義會話數據的生命週期和存儲方式;3)在PHP腳本中註冊自定義會話處理器並啟動會話。這樣可以將數據存儲在MySQL、Redis等介質中,提升性能、安全性和可擴展性。

什麼是會話ID?什麼是會話ID?Apr 24, 2025 am 12:13 AM

SessionID是網絡應用程序中用來跟踪用戶會話狀態的機制。 1.它是一個隨機生成的字符串,用於在用戶與服務器之間的多次交互中保持用戶的身份信息。 2.服務器生成並通過cookie或URL參數發送給客戶端,幫助在用戶的多次請求中識別和關聯這些請求。 3.生成通常使用隨機算法保證唯一性和不可預測性。 4.在實際開發中,可以使用內存數據庫如Redis來存儲session數據,提升性能和安全性。

您如何在無狀態環境(例如API)中處理會議?您如何在無狀態環境(例如API)中處理會議?Apr 24, 2025 am 12:12 AM

在無狀態環境如API中管理會話可以通過使用JWT或cookies來實現。 1.JWT適合無狀態和可擴展性,但大數據時體積大。 2.Cookies更傳統且易實現,但需謹慎配置以確保安全性。

您如何防止與會議有關的跨站點腳本(XSS)攻擊?您如何防止與會議有關的跨站點腳本(XSS)攻擊?Apr 23, 2025 am 12:16 AM

要保護應用免受與會話相關的XSS攻擊,需採取以下措施:1.設置HttpOnly和Secure標誌保護會話cookie。 2.對所有用戶輸入進行輸出編碼。 3.實施內容安全策略(CSP)限制腳本來源。通過這些策略,可以有效防護會話相關的XSS攻擊,確保用戶數據安全。

您如何優化PHP會話性能?您如何優化PHP會話性能?Apr 23, 2025 am 12:13 AM

优化PHP会话性能的方法包括:1.延迟会话启动,2.使用数据库存储会话,3.压缩会话数据,4.管理会话生命周期,5.实现会话共享。这些策略能显著提升应用在高并发环境下的效率。

什麼是session.gc_maxlifetime配置設置?什麼是session.gc_maxlifetime配置設置?Apr 23, 2025 am 12:10 AM

theSession.gc_maxlifetimesettinginphpdeterminesthelifespanofsessiondata,setInSeconds.1)它'sconfiguredinphp.iniorviaini_set().2)abalanceisesneededeededeedeedeededto toavoidperformance andunununununexpectedLogOgouts.3)

您如何在PHP中配置會話名?您如何在PHP中配置會話名?Apr 23, 2025 am 12:08 AM

在PHP中,可以使用session_name()函數配置會話名稱。具體步驟如下:1.使用session_name()函數設置會話名稱,例如session_name("my_session")。 2.在設置會話名稱後,調用session_start()啟動會話。配置會話名稱可以避免多應用間的會話數據衝突,並增強安全性,但需注意會話名稱的唯一性、安全性、長度和設置時機。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)