如何生成一组哈希值以确保完整性？

也许这已被问（之前我没有找到它）...如何生成一组哈希值以确保完整性？

我有一个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

如何生成一组哈希值以确保完整性？

回答

相关问题