累积字符串集合哈希化

Question

累积字符串集合哈希化

4

有没有一种Java算法可以让我持续添加字符串对象并删除旧的字符串对象，以便如果我添加了一个String，然后稍后将其删除，整数哈希值将保持不变？

编辑：哈希中的字符串是唯一的。

一些伪代码：

h = hash
add(h, "hi!") == 51;
add(h, "hello again!") == 532;
rem(h, "hello again!") == 51;

我知道你可以使用Java集合来完成，但默认实现必须在整个集合上继续收集哈希码。对于大型集合来说，这真的很低效。如果有外部库存在，我不介意使用它。

谢谢提前， Chris

- Chris Dennett

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jason S · Accepted Answer

如果您不关心哈希算法是否具有密码学质量（密码哈希算法非常难以正确指定；如果出现错误，某人可能会在您不想要的时候造成碰撞），则以下内容应该可以使用：

考虑以下代码：

interface Accumulator<T, U>
{
    public void add(T t);
    public void subtract(T t);
    public U get();
}

class SumHasher implements Accumulator<String,Integer>
{
    @Override private int accumulator = 0;
    @Override public void add(String t) { accumulator += t.hashCode(); }
    @Override public void subtract(String t) { accumulator -= t.hashCode(); }
    @Override public Integer get() { return accumulator; }
}

class XorHasher implements Accumulator<String,Integer>
{
    @Override private int accumulator = 0;
    @Override public void add(String t) { accumulator ^= t.hashCode(); }
    @Override public void subtract(String t) { accumulator ^= t.hashCode(); }
    @Override public Integer get() { return accumulator; }
}

这些操作的共同点是加法和异或都是具有结合律和逆元的操作。您可以按任何顺序执行它们并以任何顺序撤消它们，因此如果您对Set中的每个元素执行add()，然后对集合中的每个元素执行subtract()（不一定按相同的顺序），则保证得到0。

当然，还有其他满足此属性的运算，但我不确定它们是什么。（除非您能保证累积的项目没有0的值，否则乘法行不通。这个答案曾经使用f(x,h)=((x^h)+h)^h和g(x,h)=((x^h)-h)^h作为逆元，但这些函数不是关联的：以不同的顺序累加元素会给出不同的结果。）

编辑：我想到了另一个简单的操作：基于输入值的位排列（其中位旋转是一种特殊情况）。在Java中，您可以使用(x<>>(32-k))实现位旋转，其中x是整数，k是介于0和31之间的整数（例如从另一个数字中取任意5位）。>>>不是拼写错误：您需要使用它，因为常规>>会进行符号扩展。糟糕的是，这只在按相反的顺序移除集合中的元素时有效。

编辑2：最后，您可以按以下方式更普遍地实现此方法：

abstract class AbstractHashCodeAccumulator<T> implements Accumulator<T, Integer>
{
    private int accumulator = 0;
    abstract protected int combine(int a, int h);
    abstract protected int uncombine(int a, int h);
    @Override public void add(T t) { accumulator = combine(accumulator, t.hashCode());
    @Override public void subtract(T t) { accumulator = uncombine(accumulator, t.hashCode());
    @Override public Integer get() { return accumulator; }
}

class SumHasher extends AbstractHashCodeAccumulator<String>
{
    @Override protected int combine(int a, int h)   { return a+h; }
    @Override protected int uncombine(int a, int h) { return a-h; }
}

class XorHasher extends AbstractHashCodeAccumulator<String>
{
    @Override protected int combine(int a, int h)   { return a^h; }
    @Override protected int uncombine(int a, int h) { return a^h; }
}

这种方法存在的问题在于，它在某些方面不像哈希那样，即它需要有序性，而哈希通常需要无序性/熵/不可逆性。