cityhasher

CityHash，一个由Google的Geoff Pike和Jyrki Alakuijala开发的散列算法的纯Rust实现，它具有出色的性能和散列质量。

此crate实现了CityHash的当前版本（v1.1），适用于32位和64位输出。如果需要其他功能，请提交问题。

此crate是通过直接移植C++参考实现实现的。C++代码库的测试套件也被移植，并且此实现通过了测试套件。此crate的目标是提供一个纯Rust实现，该实现产生的输出与C++参考实现相同。

为什么使用CityHash？

在考虑为什么使用CityHash之前，避免使用CityHash的主要原因是你需要一个适合加密的散列算法。否则，从Google的公告

我们受到了之前散列工作的极大启发，特别是Austin Appleby的MurmurHash。我们方法的关键优势是大多数步骤至少包含两个独立的数学运算。现代CPU倾向于以这种方式代码表现最佳。

我们方法的不利之处在于，代码比大多数流行的替代方案更复杂。我们决定优化速度而不是简单性，甚至为短输入包含了特殊案例。

no_std支持

当未启用std特性时，此crate支持no_std环境。由于此功能默认启用，请添加不带默认功能的crate以确保no_std兼容性

cityhasher = { version = "*", default-features = false }

功能标志

• std：启用对HashMap和HashSet的类型别名的支持。默认启用。
• disable-bounds-checking：当此标志启用时，此crate利用unsafe代码在不进行边界检查的情况下访问正在散列的数据。此crate不使用其他unsafe代码。默认启用。

使用此crate的HashMap/HashSet

此crate导出类型别名，使得使用标准库集合类型变得简单

let mut map = cityhasher::HashMap::new();
map.insert(1, "hello");
map.insert(2, "world");
assert_eq!(map.get(&1), Some(&"hello"));

let mut set = cityhasher::HashSet::new();
set.insert(1);
set.insert(2);
assert!(set.contains(&1));

如果启用了std特性，则包含这些类型别名。

使用此crate散列字节

该包提供了两个哈希数据的功能： hash 和 hash_with_seed。这两个函数都使用泛型参数来控制哈希算法。如果您需要与其他 CityHash 的实现兼容，请确保您在 Rust 中使用与期望输出大小相同的无符号类型。

原始的 CityHash 库没有提供与 32 位哈希兼容的 hash_with_seed 实现。

let hash32: u32 = cityhasher::hash("hello");
let hash64: u64 = cityhasher::hash("hello");let bytes =
assert_ne!(hash32 as u64, hash64);

let hash64_seeded: u64 = cityhasher::hash_with_seed("hello", 1);
assert_ne!(hash64_seeded, hash64);

基准测试

在开发者的机器上使用基准测试时，该包的表现几乎与原始的 C++ 实现相同。

RUSTFLAGS="-C target-cpu=native" cargo +nightly bench -p benchmarks --features unsafe,nightly

该包不需要 nightly，但 cityhash-sys 当前需要（v1.0.5）。

32 位哈希

这个基准测试测量了产生不同字节长度输入的 32 位哈希值所需的时间。与之比较的其他包有 cityhash-sys 和 crc32fast

32bit/cityhasher/2      time:   [4.1483 ns 4.1721 ns 4.1993 ns]
32bit/cityhash-sys/2    time:   [3.6513 ns 3.6723 ns 3.6947 ns]
32bit/crc32fast/2       time:   [2.4503 ns 2.4559 ns 2.4617 ns]

32bit/cityhasher/4      time:   [5.3657 ns 5.4042 ns 5.4434 ns]
32bit/cityhash-sys/4    time:   [4.2997 ns 4.3064 ns 4.3149 ns]
32bit/crc32fast/4       time:   [3.8654 ns 3.9192 ns 3.9758 ns]

32bit/cityhasher/8      time:   [4.2414 ns 4.2749 ns 4.3351 ns]
32bit/cityhash-sys/8    time:   [3.5043 ns 3.5184 ns 3.5350 ns]
32bit/crc32fast/8       time:   [8.0307 ns 8.0413 ns 8.0532 ns]

32bit/cityhasher/16     time:   [5.5017 ns 5.5311 ns 5.5709 ns]
32bit/cityhash-sys/16   time:   [5.6581 ns 5.6704 ns 5.6841 ns]
32bit/crc32fast/16      time:   [18.174 ns 18.221 ns 18.274 ns]

32bit/cityhasher/32     time:   [9.0291 ns 9.0965 ns 9.1629 ns]
32bit/cityhash-sys/32   time:   [8.9324 ns 8.9682 ns 9.0069 ns]
32bit/crc32fast/32      time:   [39.367 ns 39.514 ns 39.721 ns]

32bit/cityhasher/64     time:   [15.288 ns 15.325 ns 15.362 ns]
32bit/cityhash-sys/64   time:   [14.604 ns 14.618 ns 14.634 ns]
32bit/crc32fast/64      time:   [20.384 ns 20.460 ns 20.559 ns]

32bit/cityhasher/96     time:   [17.496 ns 17.617 ns 17.744 ns]
32bit/cityhash-sys/96   time:   [17.076 ns 17.195 ns 17.354 ns]
32bit/crc32fast/96      time:   [76.879 ns 76.966 ns 77.074 ns]

32bit/cityhasher/128    time:   [22.088 ns 22.120 ns 22.163 ns]
32bit/cityhash-sys/128  time:   [22.174 ns 22.343 ns 22.518 ns]
32bit/crc32fast/128     time:   [9.0384 ns 9.0418 ns 9.0454 ns]

32bit/cityhasher/256    time:   [38.263 ns 38.442 ns 38.665 ns]
32bit/cityhash-sys/256  time:   [38.025 ns 38.295 ns 38.714 ns]
32bit/crc32fast/256     time:   [16.311 ns 16.370 ns 16.472 ns]

32bit/cityhasher/1024   time:   [139.20 ns 139.45 ns 139.75 ns]
32bit/cityhash-sys/1024 time:   [137.39 ns 137.58 ns 137.77 ns]
32bit/crc32fast/1024    time:   [62.221 ns 62.513 ns 63.034 ns]

64 位哈希

这个基准测试测量了产生不同字节长度输入的 64 位哈希值所需的时间。与之比较的其他包有 cityhash-sys 和 fnv

64bit/cityhasher/2      time:   [1.9630 ns 1.9703 ns 1.9782 ns]
64bit/cityhash-sys/2    time:   [2.6516 ns 2.6580 ns 2.6664 ns]
64bit/fnv/2             time:   [1.2426 ns 1.2501 ns 1.2592 ns]

64bit/cityhasher/4      time:   [1.6810 ns 1.6823 ns 1.6841 ns]
64bit/cityhash-sys/4    time:   [2.4811 ns 2.4863 ns 2.4932 ns]
64bit/fnv/4             time:   [1.8129 ns 1.8194 ns 1.8279 ns]

64bit/cityhasher/8      time:   [2.0259 ns 2.0272 ns 2.0294 ns]
64bit/cityhash-sys/8    time:   [2.7576 ns 2.7611 ns 2.7652 ns]
64bit/fnv/8             time:   [3.4148 ns 3.4985 ns 3.5753 ns]

64bit/cityhasher/16     time:   [2.0576 ns 2.0651 ns 2.0725 ns]
64bit/cityhash-sys/16   time:   [2.9018 ns 2.9384 ns 2.9808 ns]
64bit/fnv/16            time:   [7.8188 ns 7.8976 ns 7.9746 ns]

64bit/cityhasher/32     time:   [2.3330 ns 2.3428 ns 2.3557 ns]
64bit/cityhash-sys/32   time:   [2.9538 ns 2.9643 ns 2.9756 ns]
64bit/fnv/32            time:   [19.301 ns 19.387 ns 19.513 ns]

64bit/cityhasher/64     time:   [4.4110 ns 4.4556 ns 4.4919 ns]
64bit/cityhash-sys/64   time:   [4.5723 ns 4.5807 ns 4.5907 ns]
64bit/fnv/64            time:   [48.732 ns 48.889 ns 49.102 ns]

64bit/cityhasher/96     time:   [12.336 ns 12.410 ns 12.504 ns]
64bit/cityhash-sys/96   time:   [11.522 ns 11.548 ns 11.578 ns]
64bit/fnv/96            time:   [84.950 ns 85.080 ns 85.232 ns]

64bit/cityhasher/128    time:   [12.197 ns 12.224 ns 12.259 ns]
64bit/cityhash-sys/128  time:   [11.168 ns 11.205 ns 11.252 ns]
64bit/fnv/128           time:   [113.30 ns 113.33 ns 113.35 ns]

64bit/cityhasher/256    time:   [19.206 ns 19.284 ns 19.372 ns]
64bit/cityhash-sys/256  time:   [17.944 ns 17.997 ns 18.064 ns]
64bit/fnv/256           time:   [235.58 ns 236.00 ns 236.53 ns]

64bit/cityhasher/1024   time:   [58.193 ns 58.214 ns 58.236 ns]
64bit/cityhash-sys/1024 time:   [57.869 ns 57.896 ns 57.928 ns]
64bit/fnv/1024          time:   [962.78 ns 963.07 ns 963.42 ns]