如何生成一組哈希值以確保完整性？

也許這已被問（之前我沒有找到它）...如何生成一組哈希值以確保完整性？

我有一個java.util.Set aprox。 50000字符串。我想生成一些哈希來檢查它是否已經改變（比較兩個版本的哈希值）？

如果設置更改，則散列必須不同。

這怎麼能實現？謝謝！

編輯：
對不起，誤導性的措辭。我不想檢查「它」是否已被更改（同一個實例）。相反，我想檢查兩個數據庫查詢是否生成兩個 - 也許是相同的 - 一組字符串的實例是相等的。

來源

2012-01-04 Zeemee

此基礎上聲明：

If the Set changes, the hash has to be different

這真的是無法實現的，除非你有更多的約束。一般來說，散列是一些固定空間中的值。例如，你的散列可能是一個32位整數，所以有2^32個可能的散列值。一般來說，b位可以獲得2^b個可能的散列值。爲了達到你想要的，你必須確保每個可能的集合（即 - 所有集合的集合！）小於或等於2^b。但我的猜測是，你可以有任意的字符串，所以這是不可能的。即使有可能，你也必須想出一個方法來映射到散列空間，這可能很具挑戰性。

但是，使用良好的散列函數，更改集合最終不會產生相同的散列值。因此，您可以使用散列來確定不等式，但是如果散列相同，則仍然需要檢查相等性。（這與散列集或散列映射背後的想法是一樣的，其中元素根據散列碼映射到存儲區，但必須檢查是否相等）。

類似於Paul提到的但不同：您可以改爲創建一個具有版本號的集合實現，並確保在集合發生變化時始終生成新的版本號。那麼你可以比較版本號？我不確定您是否關心不可變集合或者可變集合是否變回您已經看到的版本（即 - 如果它應該始終獲得相同的版本）。

希望這會有所幫助。

來源

2012-01-04 08:05:49 Tom

是的，這有幫助，因爲它表明我的方法並不正確。謝謝！ – Zeemee 2012-01-04 08:22:20

@穆爾穆特 - 太棒了！請記住，雖然哈希值仍然很高，並且它們也可以緩存。您可能會看到性能提高。爲了提出任何其他方法，我需要更好地瞭解您的訪問模式，以瞭解如何優化事情，但這是一個好的開始。 – Tom 2012-01-04 08:27:20

我會嘗試使用java.util.AbstractSet的hashCode方法，如文檔中表示：

返回的哈希碼值的這一套。集合的哈希碼是，其被定義爲集合中的元素的哈希碼的總和，其中空元素的哈希碼被定義爲零。這確保s1.equals（s2）隱含任何兩個集合s1和s2的s1.hashCode（）== s2.hashCode（），如通用合約 Object.hashCode（）所要求的。

當然，這只是工作，如果你Set實現從AbstractSet延伸，我想你使用例如java.util.HashSet。 一如既往存在散列衝突的可能性。

或者，你可以擴展現有Set實施和覆蓋狀態改變的方法，這可能會使意義，如果每個對象的哈希計算變得過於昂貴，如：

class ChangeSet<E> extends java.util.HashSet<E> { 
    private boolean changed = false; 

    @Override 
    public boolean add(E e) { 
     changed = true; 
     super.add(e); 
    } 

    public void commit() { 
     changed = false; 
    } 

    public boolean isChanged() { 
     return changed; 
    } 

    /* and all the other methods (addAll, remove, removeAll, etc.) */ 

}

來源

2012-01-04 07:48:37 home

這是錯誤的。該集合可以改變並且仍然具有相同的hashCode。含義是單向的。當它們相等時，散列碼必須相同。但僅僅因爲hashcode是相同的並不意味着它們是平等的。 – Tom 2012-01-04 07:52:27

@Tom：當然，就像我寫的那樣，仍然存在散列衝突的可能性。如果在任何情況下都必須避免這種情況，那麼哈希是錯誤的方法（我強調了這個句子）。 – home 2012-01-04 07:56:43

@Tom它沒有錯; OP特別要求提供散列表，所以你必須假設他們意識到誤報的可能性，並且對此感到滿意。 – 2012-01-04 08:02:21

有時候，越簡單越好。我建議編寫自己的Set實現。在其中，覆蓋add和remove方法，以便在修改Set時設置標誌。爲該標誌添加一個吸氣劑，isModified，並且您不必擔心散列開銷或衝突。請致電MyCustomSet.isModified。

或者，您可以撥打Collections.unmodifiableSet以獲得無法修改的Set的包裝。如果代碼嘗試修改集合，則會引發異常。

來源

2012-01-04 07:59:37 Paul

也許「集合的兩個版本」是誤導性的。我喜歡比較兩個不同的實例。 – Zeemee 2012-01-04 08:02:37

+1：類似的方法是使用modicationCount。當modifcationCount與上次檢查時不同時，Set已更改。 – 2012-01-04 08:04:00

@Mulmoth - 套裝開始是一樣的嗎？然後，您可以捕獲更改並對其進行比較。也許重新思考需要比較兩組50,000個字符串的設計會更好。如果你無法避免，也許嵌入式數據庫可能是更好的選擇？我想你會很難平衡性能和避免碰撞。 – Paul 2012-01-04 08:08:10

如果你需要提高hashCode的性能（因爲它對於一個大集合來說相當昂貴），你可以緩存它並隨時更新它。

class MyHashSet<E> extends LinkedHashSet<E> { 
    int hashCode = 0; 
    @Override 
    public boolean add(E e) { 
     if (super.add(e)) { 
      hashCode ^= e.hashCode(); 
      return true; 
     } 
     return false; 
    } 

    @Override 
    public boolean remove(Object o) { 
     if(super.remove(o)) { 
      hashCode ^= o.hashCode(); 
      return true; 
     } 
     return false; 
    } 

    @Override 
    public void clear() { 
     super.clear(); 
     hashCode = 0; 
    } 

    @Override 
    public int hashCode() { 
     return hashCode; 
    } 
}

來源

2012-01-04 08:18:43

+1使用XOR而不是將散列碼加在一起 – Paul 2012-01-04 08:26:35

'+'和'-'應該是相同的，即使有上溢和下溢，但'^'看起來更簡單。 – 2012-01-04 08:32:06

如何生成一組哈希值以確保完整性？

回答

相關問題