Если вас не волнует криптографическое качество хеш-алгоритма (алгоритмы криптографического хеширования очень трудно правильно указать; вы запутались, и кто-то может вызвать коллизию, если вы этого не хотите), следующее должно бытьработа:
Рассмотрим следующий код:
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; }
}
Их объединяет то, что сложение и XOR являются операциями, которые ассоциативны и имеют инверсии.Вы можете выполнять их в любом порядке и отменять их в любом порядке, так что если вы add() для каждого элемента в Set<T>, а затем subtract() для каждого элемента в наборе (не обязательно в том же порядке), выгарантированно получит 0.
Конечно, есть другие операции, которые удовлетворяют этому свойству, но я не уверен, что они есть.(Умножение не сработает, если вы не гарантируете, что ни один из накопленных предметов не имеет значения 0. В этом ответе использовались f (x, h) = ((x ^ h) + h) ^ h и g (x, h) = ((x ^ h) - h) ^ h как обратные, но эти функции не ассоциативны: накапливающиеся элементы в разных порядках дают разные результаты.
Редактировать : Я думал о еще одном простом: побитовая перестановка (для которой побитовое вращение является особым случаем) на основе входного значения.В Java вы можете реализовать побитовое вращение, используя (x << k) | (x >>> (32-k)), где xцелое число, а k - это целое число от 0 до 31 (например, взять любые произвольные 5 бит из другого числа). >>> - это , а не опечатка: вам нужно использовать его, потому что обычный >> делаетsign-extension. Упс, это работает, только если элементы в наборе удалены в обратном порядке.
Редактировать 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; }
}
Проблема этого подхода заключается в том, чтов некотором смысле он не похож на хэш, а именно требует упорядоченности, тогда как хеширование обычно требует беспорядка / энтропии / необратимости.