有没有一个glibc哈希函数？

Question

我想在C语言中实现一个自定义哈希表，GNU库中是否已经有MD5/SHA1哈希函数，还是我需要使用外部库?

以下是我大致要实现的功能:

int hashValue;

hashValue = MD5_HASH(valToHash);

- themaestro

Answer 1

您可以查看Bob Jenkin对许多哈希函数进行的调查和分析：

• http://www.burtleburtle.net/bob/hash/doobs.html

或者，您可以将他放在公共领域中的lookup3例程直接加入您的项目中：

• http://www.burtleburtle.net/bob/c/lookup3.c

- Michael Burr

Answer 2

对于哈希表，你并不需要加密级别的强度，只需要拥有良好的随机化特性。破解的加密哈希函数（例如MD5）对此来说是可以接受的，但你可能想使用MD4，它更快、更简单，以至于你可以直接在代码中包含其实现。从规范中重写其并不难（而且既然你只需要一个用于哈希表的函数，如果你在某个地方出错了也不是真正的问题）。无耻的广告：在sphlib中有一个经过优化的MD4的C实现。

- Thomas Pornin

---

我很高兴你的插件没有出现任何问题；我知道这是一个旧帖子，但这仍然是一个非常好的自包含库。 - Leo

Answer 3

有一些可信的、简单的版本可供使用——在R的摘要源代码中我有几个版本。以下是我在DESCRIPTION文件中编写的内容：

描述：digest包提供了使用md5、sha-1、sha-256和crc32算法创建任意R对象的“哈希”摘要的函数，从而方便比较R语言对象。Ron Rivest的md5算法在RFC 1321中指定，SHA-1和SHA-256算法在FIPS-180-1和FIPS-180-2中指定，crc32算法在ftp://ftp.rocksoft.com/cliens/rocksoft/papers/crc_v3.txt中描述。对于md5、sha-1和sha-256，此软件包使用Christophe Devine提供的小型独立实现。对于crc32，使用zlib库中的代码。我认为Christophe的一些代码不再在cr0.net上，但搜索应该会引导您找到其他几个项目并将其合并。他的文件头非常清晰：

/*                                                   
 * FIPS-180-1 compliant SHA-1 implementation,   
 * by Christophe Devine <[e-mail]>;   
 * this program is licensed under the GPL.  
 */     

他的代码与参考输出相匹配。

- Dirk Eddelbuettel

Answer 4

gcrypt和openssl可以进行MD5、SHA和其他哈希操作，以下是使用libgcrypt的示例：

#include <gcrypt.h>
#include <stdio.h>

//  compile  gcc  md5_test.c  -lgcrypt

int main(int argc, char *argv[])
{
        unsigned char digest[16];
        char digest_ascii[32+1] = {0,};
        int digest_length = gcry_md_get_algo_dlen (GCRY_MD_MD5);
        int i;
        printf("hashing=%s len=%d\n", argv[1], digest_length);
        gcry_md_hash_buffer(GCRY_MD_MD5, digest, argv[1], strlen(argv[1]));

        for (i=0; i < digest_length; i++) {
                sprintf(digest_ascii+(i*2), "%02x", digest[i]);
        }
        printf("hash=%s\n", digest_ascii);
}

`

- karl

Answer 5

除非您已经有充分的理由使用MD5，否则您可能需要重新考虑。在哈希表中，什么样的“好”哈希函数取决于您试图实现什么目标。您可以阅读Python的dictobject.c中的评论，以了解其他人所做出的权衡。

- Hank Gay

Answer 6

如果salt以$1$开头，Glibc的crypt()使用基于MD5的算法。但是你提到你要做哈希表实现，也许Jenkins哈希更合适。

- ninjalj

Answer 7

OpenSSL库拥有您所需的所有加密例程，包括密码哈希。

- Chris

Answer 8

Murmur3是一种快速的非加密算法，您可以使用它。

在这个主题https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed中可以找到Murmur与其他算法的速度比较。

一个可能的实现：https://github.com/PeterScott/murmur3

示例：

uint32_t hash;
uint32_t seed = 42;
char* input = "HelloWorld";

MurmurHash3_x86_32(input, strlen(input), seed, &hash);
printf("x86_32:  %08x\n", hash);

- UnixShadow

Answer 9

简短回答

对于现代x86系统来说，CityHash64通常是一个不错的选择，尽管它并不总是最快的选项。对于少量数据（约16字节），FarmHash64可能是最快的选择；对于中等大小的数据（约128字节），CityHash64可能是最快的；但是随着数据变得越来越大（约4KB），xxHash64会逐渐占据优势，最终主导其他两种算法。大多数哈希表的键值通常较小，但如果您知道键值始终很大，您也可以考虑使用xxHash64。

如果您还针对非x86系统（ARM、RISC-V、PowerPC）或旧的x86 CPU（尤其是AMD的CPU），您应该明确选择CityHash64，因为在这些条件下，上述三种算法都表现较差，而CityHash64证明比其他两种算法更稳定。有时候FarmHash64在非x86 CPU上可能是最快的，但即使它击败了CityHash64，差距也相对较小，所以CityHash64仍然是一个不错的选择。

当针对32位系统时，请使用xxHash32，即使32位哈希值足够，因为对于32位来说，xxHash32总是在哈希数据变大时快速占据主导地位，并且始终产生良好的结果，尤其是在中等大小范围内。

完整答案

以下是一些适用于哈希表实现的良好候选的哈希函数：

clhash: 这个哈希函数速度非常快。如果哈希值小于64字节，比CityHash快60%，否则同样快。然而，它需要一条特殊的x86指令，只有较新的x86 CPU支持。因此，它不能在旧的CPU上使用，也不能在非x86系统（如ARM、RISC-V或PowerPC）上使用。

xxHash: 非常快速且可移植的哈希算法，可以利用各种CPU特性，有时比使用memcpy()复制原始字节更快（当要哈希的数据当前在CPU缓存中时）。与大多数其他哈希算法不同，它主要基于乘法运算，现代CPU可以非常快速地执行，但在旧的CPU上，CityHash可能提供更好的性能。

CityHash: 快速且可移植的算法。它将使用一些SSE指令，在现代x86 CPU上速度更快，但在所有CPU上都提供良好的性能。请注意，CityHash是用C++编写的，但很容易移植到纯C。

MurmurHash3: 良好的哈希函数，针对不同的x86 CPU进行了优化，并假设小端整数。它可以在非x86 CPU上编译，但速度会受到影响，如果这些CPU是大端的，你需要在两个地方实现位交换（源代码中指出了这些地方），进一步降低性能。如果不进行位交换，混合过程会被破坏，无法得到良好的哈希值。

FarmHash: 是CityHash的继任者，基本上是CityHash和Murmur系列中的几个概念的混合。它可能比CityHash表现更好，也可能不如CityHash。Google表示它在他们的数据中心中表现更好，但在其他情况下可能会有所不同。 lookup3: 非常可移植的哈希函数，只依赖于标准C，我认为它是基准。原始的MurmurHash实际上是作为更快的lookup3替代而创建的。什么是基准？如果你选择的哈希算法无法在速度上击败lookup3或生成同样好的哈希值，立即放弃它。任何连lookup3都无法击败的哈希函数都不值得考虑。你为什么要浪费时间呢？只需将公共领域的lookup3实现复制到你的项目中，然后继续前进。

SpookyHash: lookup3的作者还编写了另一个可移植的哈希函数，它在没有SSE的机器上可能比CityHash更快，但参考实现是针对x86和小端进行优化的，与MurMur3类似，使用C++编写，但将该代码移植到传统的C语言中应该没有问题。

xxHash在首页上有一个基准比较，但它遗漏了clhash，并且只包含了三个MurMur3变体中的一个（只有32位的那个）。此外，它声称SpookHash只有64位，而实际上它是128位（在生成32/64位哈希时，它只是相应地缩短了128位的值）。我真的不相信那个表，我认为它已经被篡改过，以使xxHash看起来更加优越。

归根结底，没有明确的答案来确定使用哪个最好的哈希函数。例如，在一台Core i7-5820K系统上，使用64位构建，对于较大（0.5KB以上）的数据大小，xxHash64在性能上胜出，紧随其后的是64位的FarmHash和CityHash；对于较小的数据，这三个哈希函数始终非常接近，有时一个胜出，有时另一个胜出。在一台Phone SE（A9 CPU）上，使用64位进程，xxHash从未胜出，CityHash和FarmHash占据主导地位。然而，在同一系统的32位进程中，xxHash32击败了其他哈希函数。在一台Xbox One（AMD Jaguar 1.75GHz CPU）上，尽管它是x86架构并且支持SSE，但CityHash和FarmHash仍然优于xxHash。

问题在于大多数现代哈希函数是针对特定的CPU编写的，对架构做出了假设，或者是为某个特定数据中心运营商（如Google或Facebook）的需求进行了优化。当按照设计使用时，它们会胜过其他所有哈希函数，但在其他场景或平台上使用时，结果可能完全不同。它们都具有出色的哈希质量，在实践中产生的冲突非常少，所以这并不是它们的区别所在。

请查看2016年的这篇博客文章，了解详细结果： https://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests 但有一件事是肯定的：它们都能轻松地击败MD5，后者比上述任何一种方法都慢100倍，因为MD5被设计成具有密码安全性，这要求比仅仅避免碰撞所需的混合更加困难。当然，MD5也希望避免碰撞（即两个不相关的数据片段巧合地产生相同的哈希值），但对于密码哈希函数来说，比这更重要的是无法逆转哈希，也就是说，给定一个特定的哈希值，不可能产生一个数据，当对其进行哈希时会得到完全相同的值。如果你能够产生碰撞，那就非常糟糕，会导致各种攻击，这就是为什么MD5不再安全（已知有一种方法可以快速产生碰撞），但就目前而言，还没有一种方法可以产生将哈希为给定值的数据，因为如果你能够做到这一点，那么所有的门都将敞开，任何你能想到的攻击都可以实施。

- Mecki