主页 / 问题 / 1269023
Accepted
arelive
Asked:2022-04-12 09:09:19 +0000 UTC2022-04-12 09:09:19 +0000 UTC

文件统一的最优散列算法

  • 772

底线：在我的网站上可以上传图片。这样当多次下载相同的图像到不同的相册时，不会浪费硬盘空间，所有下载都会计算 SHA1，服务器会检查目录中是否存在与接收到的哈希名称相同的文件。如果文件存在，则简单地附加一个链接，如果不存在，则将其与其哈希名称一起保存。一切都很好，但是 SHA1 结果对于地址栏来说相当长，并且计算需要很多时间。我想将名称减半，加快计算速度，但仍要消除匹配冲突的可能性。因此，md5，甚至校验和，都消失了。有一个想法是通过取散列字符串的后半部分来截断 SHA1 本身，但这并不能解决速度问题。那么，该采用什么算法呢？

хеширование

1 个回答

  1. Best Answer

    如果速度很重要，那么我建议使用xxHash，它的速度令人难以置信（大约 30 GiB / sec），有 128 位和 64 位选项。与 SHA 相比，冲突很少。唯一的缺点不是加密强度，即 逆转并不难，例如 SHA 具有加密抗性且难以逆转。

    下面是在 C++ 和 Python 中使用哈希的示例。对于 C++，下载一个xxhash.h头文件就足够了。对于 Python，安装pip install xxhash. 对于 C++，我实现了xxh3_128_hexdigest()Python 在 module 中已有的帮助函数xxhash，该函数用于获取带有哈希的十六进制字符串。

    C++：

    在线尝试代码！

    #include <iostream>
#include <string>
#include <sstream>
#include <cstdint>
#include <iomanip>
#include <algorithm>

#define XXH_INLINE_ALL
#include "xxhash.h"

inline std::string ToHex(void const * data, size_t size) {
    std::stringstream ss;
    ss << std::uppercase << std::hex;
    for (size_t i = 0; i < size; ++i)
        ss << std::setfill('0') << std::setw(2) << size_t(((uint8_t const *)data)[i]);
    return ss.str();
}

inline std::string xxh3_128_hexdigest(void const * data, size_t size) {
    auto h = XXH3_128bits(data, size);
    std::reverse(((uint8_t*)&h) + 0, ((uint8_t*)&h) + sizeof(h));
    return ToHex(&h, sizeof(h));
}

int main() {
    std::string data = "Hello, World!";
    std::cout << xxh3_128_hexdigest(data.data(), data.size()) << std::endl;
}

    Python：

    在线尝试代码！

    import xxhash
print(xxhash.xxh3_128_hexdigest('Hello, World!'.encode('ascii')).upper())

    结论：

    531DF2844447DD5077DB03842CD75395

    如果您对 xxhash 的工作原理感兴趣，那么我在下面给出 32 位第 2 版哈希的主函数（此处拍摄）的代码（第 3 版已经发布，xxh3_128_hexdigest() 使用上面的第 3 版)，下面的代码最好不要使用，如上使用xxh3_128_hexdigest()：

    static const uint32_t Prime1 = 2654435761U;
static const uint32_t Prime2 = 2246822519U;
/// rotate bits, should compile to a single CPU instruction (ROL)
static inline uint32_t rotateLeft(uint32_t x, unsigned char bits)
{
  return (x << bits) | (x >> (32 - bits));
}
/// process a block of 4x4 bytes, this is the main part of the XXHash32 algorithm
static inline void process(const void* data, uint32_t& state0, uint32_t& state1, uint32_t& state2, uint32_t& state3)
{
  const uint32_t* block = (const uint32_t*) data;
  state0 = rotateLeft(state0 + block[0] * Prime2, 13) * Prime1;
  state1 = rotateLeft(state1 + block[1] * Prime2, 13) * Prime1;
  state2 = rotateLeft(state2 + block[2] * Prime2, 13) * Prime1;
  state3 = rotateLeft(state3 + block[3] * Prime2, 13) * Prime1;
}
    • 3

相关问题