这种散列任何通用对象的方法是否正确？

Question

使用 OpenJDK 的 hashCode，我尝试在 C:

中实现通用哈希例程

U32 hashObject(void *object_generic, U32 object_length) {
    if (object_generic == NULL) return 0;

    U8 *object = (U8*)object_generic;
    U32 hash = 1;

    for (U32 i = 0; i < object_length; ++i) {
//      hash = 31 * hash + object[i]; // Original prime used in OpenJDK
        hash = 92821 * hash + object[i]; // Better constant found here: 
    }

    return hash;
}

我的想法是我可以传递一个指向任何 C 对象（原始类型、结构、数组等）的指针，并且该对象将被唯一地散列。但是，由于这是我第一次做这样的事情，我想问一下 - 这是正确的方法吗？ 是否有任何我需要注意的陷阱？

Answer 1

绝对有陷阱。下面的程序使用你的函数，例如，在 gcc -O0:

下为每个等效对象打印不同的值（并且每次编译时打印不同的值）

#include <stddef.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

struct foo {
    char c;
    int i;
};

static uint32_t hashObject(void const* object_generic, uint32_t object_length) {
    if (object_generic == NULL) return 0;

    uint8_t const* object = (uint8_t const*)object_generic;
    uint32_t hash = 1;

    for (uint32_t i = 0; i < object_length; ++i) {
        hash = 92821 * hash + object[i];
    }

    return hash;
}

int main() {
    struct foo a[2];

    a[0].c = 'A';
    a[0].i = 1;

    a[1].c = 'A';
    a[1].i = 1;

    _Static_assert(
        sizeof(struct foo) == offsetof(struct foo, i) + sizeof(int),
        "struct has no end padding"
    );

    printf("%d\n", hashObject(&a[0], sizeof *a));
    printf("%d\n", hashObject(&a[1], sizeof *a));

    return EXIT_SUCCESS;
}

发生这种情况是因为填充可以包含任何内容。

Answer 2

没有

std::vector<int> v1 = {1, 2, 3, 4};
std::vector<int> v2 = {1, 2, 3, 4};

std::cout << "hash1=" << hashobject(&v1, sizeof(v1)) 
    << "hash2=" << hashobject(&v1, sizeof(v1)) << std::endl;

会报告两个不同的哈希值，这可能不是预期的行为。

PS：问题是关于C而不是C++，但是类似的class可以在C中。

Answer 3

在评论中，您询问如果在使用之前将结构对象置零会发生什么情况。

没用。哈希仍然可能不同，因为当值存储到结构对象或结构对象¹ 的成员时，填充字节采用未指定的值。未指定的值可能会在每个商店发生变化。

其他类型还有一个问题。任何标量类型（指针、整数和浮点类型）可能具有相同值的不同表示形式。这与上面提到的结构类型与填充字节的问题类似。标量对象的位表示可能会改变，即使值没有改变，结果哈希也会不同。

（引自：ISO/IEC 9899:201x 6.2.6 类型表示 6.2.6.1 总则 6）
当值存储在结构或联合类型的对象中时，包括在成员中 object，对应于任何填充字节的对象表示的字节未指定的值。

这种散列任何通用对象的方法是否正确？

Is this approach to hashing any generic object correct?

c

hashcode

void-pointers