Automatically exported from code.google.com/p/cityhash
城市哈希（CityHash）：字符串哈希函数家族
简介
城市哈希提供了一系列用于字符串的哈希函数。这些函数能充分混合输入位，但不适合作为密码学用途。请参阅下方的“哈希质量”部分，了解关于CityHash如何测试和验证的详细信息。
我们提供了用C++编写的参考实现，并使用友好的MIT许可证。
CityHash32() 返回一个32位哈希值。
CityHash64() 及其类似函数返回一个64位哈希值。
CityHash128() 和其类似函数针对至少几百字节的字符串进行了优化，提供128位哈希值。根据您的编译器和硬件，对于足够长的字符串，它可能会比CityHash64()更快。但对于较短的字符串，速度可能较慢，但我们认为这种情况相对不那么重要。
CityHashCrc128() 和类似函数是依赖于_mm_crc32_u64()内联函数的CityHash128()变体，该内联函数在某些CPU上编译为CRC32指令。然而，我们提供的所有函数都不是真正的CRC。
CityHashCrc256() 是CityHashCrc128()的一个变体，同样依赖于_mm_crc32_u64()。它返回一个256位哈希值。
CityHash家族的所有成员都基于Austin Appleby、Bob Jenkins等人之前的工作而设计。例如，CityHash32与Murmur3a有许多相似之处。
长字符串性能：64位CPU
我们对CityHash64()及其变体在短字符串上的表现最为兴奋，但是长字符串也同样有趣。
CityHash旨在在尽可能快的情况下产生高质量的哈希值。对于具有CRC32指令的CPU，CRC是快速的，但它不是为了作为哈希函数而设计，因此不应被当作哈希函数使用。CityHashCrc128()不是一个CRC，但利用了CRC32机制。
在一个2.67GHz的Intel Xeon X5550单核上，CityHashCrc256的峰值约为5到5.5字节/周期。其他CityHashCrc函数是对CityHashCrc256的包装，在长字符串上的性能应相近（v1.0.3版本的CityHashCrc256更快，但我们发现它不够全面）。CityHash128的峰值约为4.3字节/周期。同款硬件上的最快Murmur变体Murmur3F峰值约为2.4字节/周期。我们预计CityHash128的峰值速度会优于更偏重于短字符串或哈希表使用的CityHash64。
对于长字符串，Bob Jenkins的新函数SpookyHash在Intel x86-64 CPU上仅略慢于CityHash128，但在AMD x86-64 CPU上明显更快。在AMD CPU上以及/或者没有CRC指令的CPU上，SpookyHash可能是与CityHash变体一样好甚至更好的选择，用于哈希长字符串。
短字符串性能：64位CPU
对于短字符串，如大多数哈希表键，CityHash64比CityHash128更快，具体取决于字符串长度的组合。以下是在相同硬件上的部分结果（不切实际地反复测试单一字符串长度）：
哈希函数 结果
CityHash64 v1.0.3 对于1字节为7ns，8字节为6ns，64字节为9ns Murmur2 (64位) 对于1字节为6ns，8字节为6ns，64字节为15ns Murmur3F 对于1字节为14ns，8字节为15ns，64字节为23ns
对于v1.1版的CityHash64，我们还没有基准测试结果，但预计数字会相似。
32位CPU性能
CityHash32是CityHash家族的最新变体，主要面向32位硬件，但主要在x86平台上进行了测试。我们的基准测试表明，在x86上，Murmur3是CityHash32最接近的竞争者。我们不知道有哪个更快的函数在可比质量下能超过它。在我们的测试中，速度排名如下：CityHash32 > Murmur3f > Murmur3a（对于长字符串），以及CityHash32 > Murmur3a > Murmur3f（对于短字符串）。
安装
我们提供了几个CityHash函数的C++参考实现。构建系统基于autoconf。默认的C++编译器标志为"-g -O2"，如果你使用gcc，这可能比-O3慢。具体情况因人而异。
在使用gcc的系统上，我们通常推荐：
./configure
make all check CXXFLAGS="-g -O3"
sudo make install
或者，如果您的系统支持CRC32指令，并希望构建所有内容：
./configure --enable-sse4.2
make all check CXXFLAGS="-g -O3 -msse4.2"
sudo make install
请注意，我们的构建系统不会尝试确定启用SSE4.2所需的编译器标志。对于gcc，它是"-msse4.2"。配置脚本的--enable-sse4.2标志控制当您运行"make install"时是否安装citycrc.h。一般来说，选择正确的编译器标志可能很棘手，可能取决于您的编译器、硬件，甚至您打算如何使用库。
要获取此软件如何配置的一般信息，请尝试：
./configure --help
如果没有成功，可以使用city.cc和city*.h中的代码开始，因为它们包含了所有必要的代码。
使用方法
上述安装步骤将生成一个包含CityHash32()、CityHash64()、CityHash128()及其变体，以及可能包含CityHashCrc128()、CityHashCrc128WithSeed()和CityHashCrc256()的库。带有"Crc"名称的函数在citycrc.h中声明，其余在city.h中声明。
限制
- CityHash32适用于小端序的32位代码，而当前版本的CityHash中的其他内容则适用于小端序的64位CPU。
所有不使用CRC32指令的功能应在32位或64位的小端序代码中工作。CityHash应该也可以在大端序CPU上工作，但我们尚未进行彻底测试。
- CityHash相当复杂。由于其复杂性，它可能在一些编译器上表现出预期之外的行为。例如，初步报告表明，某些Microsoft编译器将CityHash编译为比理想情况慢10-20%的汇编代码。
哈希质量
我们喜欢通过SMHasher等工具来测试哈希函数。SMHasher并不完美，但它似乎能找到几乎所有的重大缺陷。SMHasher可在http://code.google.com/p/smhasher/ 获取。
SMHasher设计为向所测试的哈希函数传递32位种子。没有CityHash函数被设计为这样工作的，所以我们按以下方式适配：对于接受种子的函数，我们直接使用给定的种子（用零填充）；对于不接受种子的函数，我们计算给定种子和输入字符串的拼接后的哈希值。
根据SMHasher，CityHash函数有以下缺点：
(1) CityHash64：无
(2) CityHash64WithSeed：无
(3) CityHash64WithSeeds：未测试
(4) CityHash128：无
(5) CityHash128WithSeed：无
(6) CityHashCrc128：无
(7) CityHashCrc128WithSeed：无
(8) CityHashCrc256：无
(9) CityHash32：无
32位和64位函数的一些轻微缺陷在某些情况下是无害的，因为我们期望这些函数的主要用途是哈希表。我们可能在试图满足SMHasher和其他类似测试时做得有些过分，但我们不想因为质量测试报告出的一些小问题而让任何人选择不同的哈希函数。
更多信息
加入讨论组：cityhash-discuss@googlegroups.com
欢迎随时向我们发送您的反馈、问题、bug报告或补丁。