一、使用 open addressing 的 Hash 表載荷過高會(huì)降低 CPU 的緩存命中率的原因

在計(jì)算機(jī)程序中，哈希表（Hash Table）是一種常見的數(shù)據(jù)結(jié)構(gòu)，它用于實(shí)現(xiàn)字典、集合等高效的數(shù)據(jù)存儲(chǔ)和檢索。其中，開放尋址（Open Addressing）是一種哈希表的實(shí)現(xiàn)方式，它采用線性探測(cè)或二次探測(cè)等方式解決哈希沖突，將元素直接存儲(chǔ)在哈希表中，而不是通過鏈表等方式鏈接在一起。

當(dāng)哈希表中元素的數(shù)量超過哈希表的容量時(shí)，哈希表的載荷因子就會(huì)增加，這意味著哈希表中每個(gè)桶中存儲(chǔ)的元素?cái)?shù)量也會(huì)增加。當(dāng)載荷因子過高時(shí)，哈希表的性能可能會(huì)受到影響。

1、哈希表的查找效率受緩存命中率的影響

CPU 中的緩存是一種高速存儲(chǔ)器，用于暫時(shí)存儲(chǔ)最近使用過的數(shù)據(jù)。當(dāng) CPU 訪問內(nèi)存時(shí)，它通常會(huì)先從緩存中查找數(shù)據(jù)，如果數(shù)據(jù)存在于緩存中，就可以快速訪問它，否則需要從內(nèi)存中加載數(shù)據(jù)，這會(huì)消耗更多的時(shí)間。當(dāng)哈希表中的元素?cái)?shù)量過多時(shí)，它們可能無法完全存儲(chǔ)在緩存中，這就會(huì)導(dǎo)致 CPU 在訪問哈希表時(shí)頻繁地從內(nèi)存中加載數(shù)據(jù)，從而降低了緩存命中率。

2、哈希表的沖突率可能會(huì)增加

當(dāng)哈希表的載荷因子過高時(shí)，不同的元素可能會(huì)被哈希到相同的桶中，這就會(huì)導(dǎo)致哈希表的沖突率增加。為了解決沖突，哈希表需要進(jìn)行線性探測(cè)或二次探測(cè)等操作，這會(huì)增加程序訪問內(nèi)存的次數(shù)，從而降低了緩存命中率。