穩(wěn)定復(fù)現(xiàn)的 HashMap 陷阱

當(dāng)我們看了很多哈希函數(shù)的介紹并切換到一個(gè)你認(rèn)為更快的哈希函數(shù)上面時(shí)，大部分代碼都獲得了預(yù)期的速度提升，但有些部分卻莫名其妙地變慢了很多，尤其是在處理大型 hashMap 時(shí)。

如果這聽(tīng)起來(lái)很熟悉，那么您可能遇到了穩(wěn)定復(fù)現(xiàn)的 HashMap 陷阱。

Google SwissTable 是 2017 年 CppCon 上被發(fā)表的一個(gè)高性能的 hashTable 。

從 Rust 1.36 開(kāi)始，SwissTable 就是 Rust HashMap 的標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)。

雖然它有不錯(cuò)的性能，但 SwissTable 旨在以性能為代價(jià)抵御一類(lèi) HashDoS 攻擊。

如果您關(guān)心性能并且不關(guān)心安全問(wèn)題，切換到類(lèi)似 FxHasher 或者 ahash 可以顯著提高性能。

然而，這個(gè)建議的代價(jià)卻很少有人提及 —— 一些 O(n) hashTable 操作，包括反序列化，在一些 case 下它的時(shí)間復(fù)雜度有可能會(huì)升級(jí)到 O(n**2)。

下面博文會(huì)給大家?guī)?lái)測(cè)試 case 以及為什么會(huì)發(fā)生如此大的性能差距

https://morestina.net/blog/1843/the-stable-hashmap-trap

CnosDB 2.0 發(fā)布

特色功能：

專(zhuān)為時(shí)序數(shù)據(jù)設(shè)計(jì)的存儲(chǔ)引擎，優(yōu)化寫(xiě)操作，支持刪除和更新操作；

壓縮算法由用戶靈活指定，壓縮比可調(diào)；

基于 Apache Arrow 及 DataFusion 實(shí)現(xiàn)了查詢引擎；

支持標(biāo)準(zhǔn) SQL，支持 Schemaless 寫(xiě)入；

多索引優(yōu)化了查詢效率；

生態(tài)友好，支持 RESTful 接口，支持 Telegraf、Grafana 等通用第三方生態(tài)組件。

快速上手指南：http://docs.cnosdb.com

GitHub倉(cāng)庫(kù): https://github.com/cnosdb/cnosdb

審核編輯：劉清