如何在 C++ 中计算对象的 hash/checksum/fingerprint？

Question

要求：

函数必须是'injective'(*)。也就是说，不应该有两个不同的输入对象，即return相同hash/checksum/fingerprint.

背景：

我正在尝试想出一个简单的模式来检查实体对象自构造以来是否已更改。（为了知道数据库中哪些对象需要更新）。

请注意，我特别不想在我的设置器或其他任何地方将对象标记为已更改。

我正在考虑以下模式：简而言之，每个应该持久化的实体对象都有一个成员函数"bool is_changed()"。在此上下文中，更改意味着自调用对象的构造函数以来发生了更改。

注意：我做这一切的动机是为了避免将对象标记为 clean/dirty 或逐个比较成员的样板代码。换句话说，减少人为错误的风险。

（警告：前面的 psudo C++ 代码。我还没有尝试编译它）。

class Foo {
private:

    std::string my_string;

    // Assume the "fingerprint" is of type long.
    long original_fingerprint;

    long current_fingerprint()
    {
        // *** Suggestions on which algorithm to use here? ***
    }
public:
    Foo(const std::string& my_string) :
        my_string(my_string)
    {
        original_fingerprint = current_fingerprint();
    }

    bool is_changed() const 
    {
        // If new calculation of fingerprint is different from the one
        // calculated in the constructor, then the object has  
        // been changed in some way.

        return current_fingerprint() != original_fingerprint;
    }

    void set_my_string(const std::string& new_string)
    {
        my_string = new_string;
    }
}


void client_code()
{
    auto foo = Foo("Initial string");

    // should now return **false** because 
    // the object has not yet been changed:
    foo.is_changed();

    foo.set_my_string("Changed string");

    // should now return **true** because
    // the object has been changed:
    foo.is_changed();
}

(*)实际上，理论上不一定（比如uuid在理论上不是唯一的）。

Answer 1

这样的功能不存在，至少在您请求的上下文中不存在。

STL 为基本类型 (std::hash) 提供散列函数，您可以使用这些函数通过任何合理的散列算法为您的对象实现散列函数。

但是，您似乎在寻找单射函数，这会导致问题。本质上，要具有单射函数，输出的大小必须大于或等于您正在考虑的对象的大小，否则（根据鸽巢原理）将有两个输入提供相同的输出。鉴于此，最明智的选择是直接将对象与某种参考对象进行比较。

Answer 2

可以使用CRC32 algorithm from Boost。将要校验和的数据的内存位置提供给它。您可以为此使用散列，但散列是旨在防止故意数据损坏的加密函数，并且速度较慢。 CRC 性能更好。

对于这个例子，我添加了另一个数据成员到 Foo:

int my_integer;

这就是 my_string 和 my_integer 校验和的方式：

#include <boost/crc.hpp>
// ...

long current_fingerprint()
{
    boost::crc_32_type crc32;
    crc32.process_bytes(my_string.data(), my_string.length());
    crc32.process_bytes(&my_integer, sizeof(my_integer));
    return crc32.checksum();
}

但是，如果 my_string 和 my_integer 相等，现在我们剩下的问题是两个对象具有相同的指纹。要解决此问题，我们应该在 CRC 中包含对象的地址，因为 C++ 保证不同的对象将具有不同的地址。

有人会认为我们可以使用：

process_bytes(&this, sizeof(this));

这样做，但我们不能，因为 this 是一个右值，因此我们不能获取它的地址。所以我们需要将地址存储在一个变量中：

long current_fingerprint()
{
    boost::crc_32_type crc32;
    void* this_ptr = this;
    crc32.process_bytes(&this_ptr, sizeof(this_ptr));
    crc32.process_bytes(my_string.data(), my_string.length());
    crc32.process_bytes(&my_integer, sizeof(my_integer));
    return crc32.checksum();
}

如何在 C++ 中计算对象的 hash/checksum/fingerprint？

How can I calculate a hash/checksum/fingerprint of an object in c++?

c++

hash

orm

checksum