数据库相关算法 之 xxHash

原创
2017/11/13 22:25
阅读数 1K

Extremely fast non-cryptographic hash algorithm http://www.xxhash.com/

  1. Extremely fast,超快,working at speeds close to RAM limits。看了代码,作者对 memcpy 这样的 CRT 函数都要去追究性能,嫌弃它在一些平台/编译器组合下,只是次优解;而且处处可见对内存对齐的优化。总之优化功力挺深。

  2. non-cryptographic,非加密型的 Hash。如果是 cryptographic hash algorithm,则输入的数据只要改变一个 bit,输出的 bits 就应该改变 50%,这样的安全性才合格。而非加密型,没有防破解“安全性”这个要求,仅要求“唯一性”。

  3. 通过 SMHasher 测试,这是一个专门测试 non-cryptographic hash 的工具,测试包括分布、碰撞、性能。

  4. It is proposed in two flavors, 32 and 64 bits. 32 位程序用 32 位库比较快,同理,64 位程序用 64 位库比较快。

  5. 多平台支持,包括硬件平台(Big Endian/Little Endian、不同 CPU 架构等) 和操作系统。多种语言实现。RocksDB、MySQL 用它。它可以用来实现 Bloom Filter。

  6. 库只有两个文件:xxhash.c、xxhash.h,BSD 2 协议。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部