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

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: https://stackoverflow.com/questions/1835976/what-is-a-sensible-prime-for-hashcode-calculation
    }

    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;
}

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