我使用的是第三方API(来自https://lib.rs/crates/gcloud-sdk的GCloud SDK),它在类型中使用HashMaps将键/值对传递给GCloud Web服务并返回。包含这样一个散列Map的字段是这样指定的:
pub labels: ::std::collections::HashMap<
::prost::alloc::string::String,
::prost::alloc::string::String,
>,
这只是说HashMap<String,String>的一个很长的方式。其中许多字段将包含空哈希Map或单条目哈希Map。由于默认的散列器被认为是“慢”的,我希望能够优化这些Map,如果他们成为一个瓶颈。我在这里的意图,现在,真的只是优化的能力,如果它成为一个问题,而不是在我知道它是一个问题之前过早地优化。
性能问题包括两个方面:
- 生成一个新的RandomState是非常昂贵的(即使是从/dev/urandom读取,也是AFAIK),甚至会影响空的哈希Map
- 散列单个键的代价有点高,比上述的要低,但对于单元素Map来说仍然是大材小用,因为散列Map的优点很少适用于单元素Map
因此,我最初的想法是用一个更简单的哈希算法代替哈希算法,对于空Map甚至用一个无操作。不过,我不明白这是怎么回事。我写了一个no-op实现,被一个像这样的函数 Package :
pub fn create_nop_hash_map<K, V>() -> HashMap<K, V, NopBuildHasher> {...}
我省略了NopBuildHasher的实现,因为它很简单,与我遇到的问题无关。
这给了我一个错误:
labels: create_nop_hash_map(),
^^^^^^^^^^^^^^^^^^^^^ expected `HashMap<String, String>`, found `HashMap<_, _, NopBuildHasher>`
“labels”字段是在第三方库中定义的,所以我不可能更改它的类型。我当然可以要求作者改变这个字段,但是它应该是什么样子呢?图书馆无法提前知道我会把哪些Map留空。在我看来,我唯一能实际要求作者的事情是为每个Map类型字段定义一个新的类型参数,因为这些参数将级联在封闭的结构体中,整个库将被散列算法的类型参数所混杂。这对我来说似乎不现实。
我想尝试的另一种方法是保留默认的Siphash-1-3算法,只使用硬编码的初始值,但我也不能这样做,因为RandomState字段是私有的,没有构造函数直接指定它们。
我能想到的最后一件事是要求库的作者不要对这些字段使用哈希Map,而是要使用e.g. key-value-pairs,但在我看来我完全走错了路,因为我认为使用自定义哈希算法是许多人以前做过的一个常见用例。
将哈希Map与自定义哈希算法传递给第三方API的惯用方法是什么?或者,优化空或单元素哈希Map的惯用方法是什么?
1条答案
按热度按时间hi3rlvi21#
在当前版本的Rust中,创建一个新的
RandomState
示例非常便宜。只有线程创建的第一个RandomState
示例才使用随机密钥初始化。所有其他示例reuse the cached keys和simply increment one of them by one。这应该可以减轻对空哈希Map的任何担忧。性能问题在2016年7月发布的Rust 1.10中得到修复,而潜在的DOS问题在2016年12月发布的Rust 1.14中得到修复。使用单个键的哈希Map的主要成本很可能是分配器,而不是哈希器。如果散列Map包含一个键,它需要分配内存,这很可能比计算单个散列要昂贵得多。优化散列器不太可能对这个用例有任何重要的帮助。