这种方法能够正确地散列任何通用对象吗？

使用的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的对象（基本类型，结构，阵列等）和该对象将被独特地散列。但是，因为这是我第一次做这样的事情，所以我想问 - 这是正确的做法吗？我需要注意哪些缺陷？

来源

2017-03-10 Naman Dixit

C中没有通用对象，我们不是代码验证网站。 – Olaf

@Olaf通用的意思是我可以将它们的指针（隐式地作为void *）传递给这个** one **函数，而不是为我使用的每种类型（原始的和用户定义的）编写一个哈希函数。 –

@Olaf：这是一个问题。问题实际上就是我们在这里所做的。 – Ryan

有明显的缺陷。下面的程序使用功能，例如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; 
}

这是因为填充可以包含任何东西。

来源

2017-03-10 02:41:28 Ryan

填充不应该是一个问题AFAIK，因为我正在使用归零内存池（mmap'ed）分配对象。填充字节是随机的东西，它可能会失败的唯一原因？ –

@NamanDixit：是的，我非常肯定这是唯一的原因，但我肯定不会指望能够避免为符合标准的实现打开位置，以便在零内存池中的结构中更改填充字节。 – Ryan

务实地说，它是否真的发生在MSVC/GCC/Clang下的Linux/Windows/MacOS上？我做了一些快速测试，似乎零字节保持为零。（但是，是的，这是我没有听说过的问题）。 –

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++，但类似的类可以在C

来源

2017-03-10 02:51:57 user31264

问题是关于C，但它仍然是一个很好的观点：如果对象包含一个指针，即使指向的数据是等价的，哈希也可能不同。 –

请观察问题上的语言标签。这篇文章应该只有C的答案。 – 2501

在你问，如果你在使用前零出结构对象会发生什么评论。

这没有帮助。哈希值可能仍然不同，因为当值存储到结构对象或结构对象的成员中时，填充字节取未指定的值。。未指定的值可能会在每个商店中更改。

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

（：ISO/IEC 9899：引自201X 6.2.6表征的类型6.2.6.1一般6）
当值被存储在结构或联合类型的对象，其中包括在一个成员对象，对应于任何填充字节的对象表示的字节取未指定的值。

来源

2017-03-10 09:20:34 2501

这种方法能够正确地散列任何通用对象吗？

回答

相关问题