一、使用 open addressing 的 Hash 表載荷過高會降低 CPU 的緩存命中率的原因
在計算機程序中,哈希表(Hash Table)是一種常見的數據結構,它用于實現字典、集合等高效的數據存儲和檢索。其中,開放尋址(Open Addressing)是一種哈希表的實現方式,它采用線性探測或二次探測等方式解決哈希沖突,將元素直接存儲在哈希表中,而不是通過鏈表等方式鏈接在一起。
當哈希表中元素的數量超過哈希表的容量時,哈希表的載荷因子就會增加,這意味著哈希表中每個桶中存儲的元素數量也會增加。當載荷因子過高時,哈希表的性能可能會受到影響。
1、哈希表的查找效率受緩存命中率的影響
CPU 中的緩存是一種高速存儲器,用于暫時存儲最近使用過的數據。當 CPU 訪問內存時,它通常會先從緩存中查找數據,如果數據存在于緩存中,就可以快速訪問它,否則需要從內存中加載數據,這會消耗更多的時間。當哈希表中的元素數量過多時,它們可能無法完全存儲在緩存中,這就會導致 CPU 在訪問哈希表時頻繁地從內存中加載數據,從而降低了緩存命中率。
2、哈希表的沖突率可能會增加
當哈希表的載荷因子過高時,不同的元素可能會被哈希到相同的桶中,這就會導致哈希表的沖突率增加。為了解決沖突,哈希表需要進行線性探測或二次探測等操作,這會增加程序訪問內存的次數,從而降低了緩存命中率。