穩定復現的 HashMap 陷阱

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

如果這聽起來很熟悉，那么您可能遇到了穩定復現的 HashMap 陷阱。

Google SwissTable 是 2017 年 CppCon 上被發表的一個高性能的 hashTable 。

從 Rust 1.36 開始，SwissTable 就是 Rust HashMap 的標準庫實現。

雖然它有不錯的性能，但 SwissTable 旨在以性能為代價抵御一類 HashDoS 攻擊。

如果您關心性能并且不關心安全問題，切換到類似 FxHasher 或者 ahash 可以顯著提高性能。

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

下面博文會給大家帶來測試 case 以及為什么會發生如此大的性能差距

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

CnosDB 2.0 發布

特色功能：

專為時序數據設計的存儲引擎，優化寫操作，支持刪除和更新操作；

壓縮算法由用戶靈活指定，壓縮比可調；

基于 Apache Arrow 及 DataFusion 實現了查詢引擎；

支持標準 SQL，支持 Schemaless 寫入；

多索引優化了查詢效率；

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

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

GitHub倉庫: https://github.com/cnosdb/cnosdb

審核編輯：劉清