短文件名的最佳字符串散列函數

對於像文件名字符串那樣，最好的字符串散列函數是什麼？該字符串將類似於：短文件名的最佳字符串散列函數

pics/test.pic 
maps/test.map 
materials/metal.mtl

來源

2012-07-10 Tom Tetlaw

哈希的目的是什麼？沒有通用的「最佳」散列函數，而與散列的使用方式無關。 – 2012-07-10 13:02:48

STL有一個內置的字符串哈希函數：http://en.cppreference.com/w/cpp/string/basic_string/hash – 2012-07-10 13:24:53

如果數據的性質被散列不需要任何花哨的哈希算法，如文本字符串的性質，你可能會想嘗試FNV hashing function。 FNV哈希是Fowler/Noll/Vo爲創作者所用的簡稱，是一種非常快速的算法，已在許多應用中用於精彩的結果，並且爲了簡單起見，FNV哈希應該是首次嘗試的哈希值之一一個應用程序。

unsigned int fnv_hash (void* key, int len) 
{ 
    unsigned char* p = key; 
    unsigned int h = 2166136261; 
    int i; 

    for (i = 0; i < len; i++) 
     h = (h*16777619)^p[i]; 

    return h; 
}

或滾動與MD5 algorithm代替，這是通用的，因此涵蓋您的需求相當不錯。

來源

2012-07-10 13:14:42

-1對於不必要的'void *'。 – Puppy 2012-07-10 13:42:19

@DeadMG爲什麼應該只爲文本專門設計一個散列函數呢？就其本質而言，它可以處理任何類型的數據，並且可以在沒有爲每個目的調整實現的情況下被重用。 – 2012-07-10 13:53:32

@DeadMG具有諷刺意味的是，就在你給我這個答案-1之前，我把你的答案upvoted在這裏http://stackoverflow.com/questions/3694899/c-template-and-inline-question它曾經有-1票在那之前。 – 2012-07-10 13:59:35

沒有通用的「最佳」哈希函數獨立於如何使用哈希。

讓我們假設你想要一個32位的int以便在內存中使用一個小的散列表。

然後你可以使用FNV-1a algorithm：

hash = offset_basis 
for each octet_of_data to be hashed 
hash = hash xor octet_of_data 
hash = hash * FNV_prime 
return hash

如果你的目的是有信心的事實，兩個路徑給出不同的哈希值，那麼你可以使用SHA1 algorithm。

如果你想確保它很難惡意創建衝突，那麼你可以使用SHA256。

請注意，那些最後2個算法會生成長哈希（比您的典型路徑更長）。

來源

2012-07-10 13:15:11

加密哈希很可能會過度殺傷。 OP可以在C++ 11中使用boost :: hash或std :: hash代替。 – pg1989 2012-07-10 13:17:20

矯枉過正？你知道如何以及爲什麼使用這個散列嗎？ – 2012-07-10 13:17:53

是的，我做密碼研究，所以我非常熟悉密碼哈希。 SHA1的速度比最慢的非加密哈希慢一個數量級，所以他會犧牲速度來達到他最不可能需要的抗碰撞假設。 – pg1989 2012-07-10 13:19:49

只需使用std::hash<std::string>。這是您的圖書館實施者關於「最佳」通用非加密散列函數的想法。

來源

2012-07-10 13:30:51

短文件名的最佳字符串散列函數

回答

相關問題