有趣stdext ::哈希值（）實現

我試圖用stdext::hash_value()在VS2010一些散列算法，實現了這一點：有趣stdext ::哈希值（）實現

#include <iostream> 
#include <xhash> 
using namespace std; 

int main() 
{ 
#ifdef _WIN64 
    std::cout << "x64" << std::endl; 
#else 
    std::cout << "x32" << std::endl; 
#endif 

    std::cout << stdext::hash_value(345.34533) << std::endl; 
    std::cout << stdext::hash_value(345.566) << std::endl; 

    return 0; 
} 

// Output is: 
// x64 
//3735928758 
//3735928758

我想，有相同的整數，但不同的小數部分的雙變量的其他一些夫婦。像1.234 vs 1.568一樣。哈希值總是相同的。所以，我接過來一看在hash_value()源，看到

#define _HASH_SEED (size_t)0xdeadbeef 

template<class _Kty> inline 
size_t hash_value(const _Kty& _Keyval) 
{ // hash _Keyval to size_t value one-to-one 
    return ((size_t)_Keyval^_HASH_SEED); 
}

_KeyVal被轉換爲size_t不道理給我。該函數簡單地忽略了double的小數部分。這個實現背後的邏輯是什麼？它是一個錯誤或功能？

來源

2011-04-01 ali_bahoo

我覺得這個函數實際上是從Visual Studio 6開始的。這可以解釋很多。 – 2011-04-01 17:06:28

@dauphic：我不知道Visual Studio 6，但是它在''頭部的'stdext'命名空間中。那些舊的？ – 2011-04-01 17:13:45

是的，'stdext'的內容最初位於'std'命名空間，但是它們被移動到'stdext'，因爲它們不是標準庫的一部分（因此不應該在'std'命名空間中）。我不確定哪個版本移動了它們，但是它們在Visual Studio 7中是'stdext'，因此它們必須追溯到1998年或更早發佈的Visual Studio 6。 – 2011-04-01 22:55:27

stdext ::哈希值不是一個哈希函數。這是一個哈希函數的輸入，您將它專門用於您的類型，以便它可以用作stdext哈希類的關鍵字。但是似乎沒有任何文檔。實際的散列函數是stdext :: hash_compare。

但因爲HASH_VALUE的沒有默認專業化它使用轉換到INT方法，忽略小數部分。

存在用於標準STD一個幾乎相同的錯誤:: TR1 ::散列/性病::散列函數，直到VC10：

http://connect.microsoft.com/VisualStudio/feedback/details/361851/std-tr1-hash-float-or-hash-double-is-poorly-implemented

在VC10的std ::散列得到一個雙專業化那些哈希值。我猜stdext現在被認爲已經過時，所以即使在vc10中也沒有修復它。

來源

2011-04-03 07:05:16 BCoates

上述答案中指定的鏈接已死亡。你能更新它嗎？ – affan 2016-08-18 06:07:17

該函數被編寫用於處理任何類型的數據。它不會假定尺寸，因此對於某些類型是低效的。您可以覆蓋此行爲雙打，使通過模板特

template<> 
size_t hash_value<double>(const double& key) { 
    return // Some awesome double hashing algorithm 
}

把你上面的main方法這一定義將導致調用stdext::hash_value(354.566)結合，而不是標準的一個

來源

2011-04-01 16:51:36 JaredPar

一個適當的指針指針轉換會做，但爲什麼他們不提供這個非常基本的功能？ – 2011-04-01 16:57:57

@sad_man我真的不知道他們爲什麼選擇這個特定的默認設置。 – JaredPar 2011-04-01 16:58:44

這裏的問題不是大小，而是double被轉換爲整數並丟失小數部分。 – 2011-04-01 17:00:44

這個定義，它更有效

這是舊代碼 - 看起來不太好。

你應該嘗試使用std :: hash代替。

來源

2011-04-01 16:59:54

在TR1中引入了'std :: hash（）'。 VS2010是否支持它？ – Void 2011-04-01 17:55:46

這一點，顯然，企圖爲整數提供一個通用的散列函數（雖然我看不出有什麼異或增加）。很明顯，不適用於大多數其他類型。包括浮點數。

提供用於浮點值良好的散列函數是困難的; 如果我想做一個普通的哈希，我可能會通過測試爲0，楠天道酬勤，並返回預定的散列那些（或完全拒絕NaN的，因爲它不是一個有效的可哈希值）開始，然後只需在底層字節上使用標準字符串散列。這將使至少使哈希兼容==運算符。但是精度的問題意味着==本身可能不是需要的。因爲std :: map使用<來定義一個相等的關係，並且取決於浮點數或雙精度的來源，例如，所以平等關係可能不適合散列表。

在任何情況下，不要指望找到浮點類型的標準散列函數。

來源

2011-04-01 17:35:58

我認爲散列浮點值的內存表示會產生一個很好的散列，而且我甚至不願意測試具體的值。 – 2011-04-01 17:53:54

只對內存表示進行散列不會爲特定值提供有效散列;這就是爲什麼我分別對待他們。請記住，哈希函數的一個重要不變量是：a == b = hash（a）== hash（b）'。在0的情況下，+0和-0在內存中具有不同的表示，儘管它們相等。我不確定Inf，也許你不需要特別對待它，而且NaN永遠不會比較平等，因此無論如何都不能用作關鍵。 – 2011-04-01 18:29:37

std :: hash vc10引入了兩個散列值到相同的值，但散列位，所以它至少在有限值上表現良好。散列浮點數的整個想法看起來有點反常。 – BCoates 2011-04-03 07:36:41

VC10包含C++ 0x標準哈希機制，因此不需要再使用stdext，而std::hash確實包含一個機制double，它執行按位轉換和散列。您擁有stdext的代碼只是一種回退機制，並非真正用於浮點類型。我想這是一個設計監督。

template<> 
class hash<double> 
    : public unary_function<double, size_t> 
{ // hash functor 
public: 
typedef double _Kty; 
typedef _ULonglong _Inttype; // use first 2*32 bits 

size_t operator()(const _Kty& _Keyval) const 
    { // hash _Keyval to size_t value by pseudorandomizing transform 
    _Inttype _Bits = *(_Inttype *)&_Keyval; 
    return (hash<_Inttype>()(
     (_Bits & (_ULLONG_MAX >> 1)) == 0 ? 0 : _Bits)); 
    } 
};

來源

2011-04-03 10:06:19 Puppy

有趣stdext ::哈希值（）實現

回答

相關問題