2013-09-25 63 views
4

我想我的問題也可以這樣問:在一個雙精度變量中,單個十進制值可以表示多種方式嗎?來自double的字節散列對於相同的值是否總是相同?

我有一個哈希表的實現,雙精度浮點數將是關鍵,我使用哈希算法構建一個哈希,同時迭代每個字節的雙(至少在我的系統是64位,所以8個字節散列)。我的問題是,如果一個單一的值,比如說'1.2345'可以用二進制形式以多於一種的方式表示,那麼它可能會導致單個值的多個可能的散列值。

我不確定在哪裏研究這種可能性。如果我不得不猜測我會猜測這是不可能的,或者如果有可能使某些東西標準化以確保某個值在給定系統上始終具有相同的表示形式。我主要在尋找這方面的確認。

如果一個值可以有多個表示,那麼在對它進行哈希運算之前,我需要對這個值進行規範化處理,我很樂意提供關於如何做到這一點的建議。

編輯:

我已經找到了更多關於浮點數的信息。它們存儲爲mantessa和指數。所以我的問題是單個浮點數可以由Mantessa和指數的多個組合來表示。

+0

請改用固定點嗎? –

+0

這是「尾數」,而不是「mantessa」。除了它是一個有效數字(線性),而不是尾數(對數)。 –

回答

2

浮點數的按字節散列會產生兩個問題。

第一個令人驚訝的經常出現的情況是有兩個表示0,每個表示有一個可能的符號位。 (0和負0)。這些不僅在數學上相等,而且還需要在C/C++中進行相等的測試。負數0經常出現在計算中,儘管並非所有的printf都將其打印爲-0。 (在Intel硬件上,至少0.0/-1.0是-0.0)。

所以你需要確保兩個零散列到同一個東西。

另一個問題是NaNs。 NaN的數量非常多,但即使對自己也不具有可比性(技術上),所以他們使得糟糕的哈希鍵。可能最簡單的解決方案是忽略它們,因爲沒有人應該期望NaN可以用作散列鍵。但問題是,如果有人試圖將其放入哈希表中,然後再次放入哈希表中,那麼如果使用浮點數==檢查關鍵存在,最終可能會輸入兩次。因此,一個簡單的bug(或故意的攻擊)可能會通過擴展哈希表來快速耗盡內存。 (如果與memcmp比較字節,則不會出現此問題。)

0

這是可能的。雙精度值比浮點值更精確,但在精度方面仍然不是100%密封的。使用固定點或整數對錶示(即:值的每個部分爲整數)。

2

IEEE 754二進制浮點只有一個編碼用於每個可表示的值,除零外,其中有一個+0和一個-0。

當今大多數C實現使用IEEE 754二進制格式。但是,並非所有操作都能正確實現浮點運算(例如,從字符串中的十進制轉換爲二進制浮點運算可能會產生稍微不準確的結果),並且運算鏈的結果可能與您使用精確算術得到的值不同,即使它們在數學上是相同的,不同的鏈可能產生不同的值。 (後者包括編譯與不提供嚴格浮點評估的不同編譯器相同源代碼的結果。)

IEEE 754還指定了十進制浮點格式,並且它具有多種值的表示形式。

相關問題