這種方法能夠正確地散列任何通用對象嗎？

使用的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

這種方法能夠正確地散列任何通用對象嗎？

回答

相關問題