使用緩存哈希值來加速平等測試

Question

我的目標語言是C++，但這是一個關於面向對象編程的問題。

假設我有一個類，其中測試相等需要一個非常重要的時間，但我也有一個散列值，我已經計算了它。我可以依靠數據在對象的生命中保持不變。

緩存散列值並用它來測試不等式常見做法嗎？

爲了讓這個例子更具體一些，我有一個類包含一個可能很長的2D位置列表，我期望在它上面做很多很多的相等比較。我通過混合所有位置的哈希來創建哈希值。

當測試相等時，我首先檢查散列值。如果哈希值相等，我會做詳盡的逐點平等測試。否則，我稱他們不平等。

Answer 1

只要您的散列算法能夠保證爲相同的輸入數據生成相同的散列，聽起來不錯。然後，你的支票應該加速大幅度增加存儲散列值的額外內存的小額費用（以及計算哈希的1次計算成本）

Answer 2

我想你的意思是說：「如果散列是不等於，我會做詳盡的逐點平等測試。」

在任何情況下 - 是的，你有一個好主意，這是一個完全合理的設計。你正在爲大量昂貴的CPU和/或牆壁時間交易一點便宜的存儲空間。像這樣的設計可以帶來巨大的性能優勢。例如，考慮每個單獨的點測試需要數據庫查詢的情況。