Сравнение Java-карт с помощью хеширования - PullRequest
Новая
       39

Сравнение Java-карт с помощью хеширования

0 голосов
/ 21 июля 2011

Я хочу сравнить два Java Map s с помощью простого хэша.

Каждый объект находится на другом компьютере, поэтому отправка хэша по сети будетдешевле, чем отправить весь объект для сравнения.

Например, у меня есть два HashMap s класса ExampleClass 

Map<String,ExampleClass> One=new ...;

Map<String,ExampleClass> Other=new ...;

Мне не нужно быть увереннымчто все элементы равны , мне достаточно доверять хешу.

Я собирался перебрать каждую сторону и создать «самодельный хэш», а затем отправить егок сети, чтобы, наконец, сравнить, например, int или что-то в этом роде.

Было бы здорово, если бы этот "хэш" вычислялся каждый раз, когда объект добавлялся или удалялся из коллекции, спасая меня от повторения всегообъект.Я должен инкапсулировать каждое добавление / удаление Map.Есть ли библиотека Java, которая делает это?

Ответы [ 2 ]

6 голосов
/ 21 июля 2011

Если все ваши классы реализуют hashCode() (не использует хэш-код адреса памяти по умолчанию ), вы можете использовать карты hashCode().

Предостережение заключается в том, что если ваш ExampleClass не реализует hashCode(), то равные элементы могут иметь разные хэши на двух разных машинах, что приведет к разным хешам для карт.

Комууточнить:

Map реализует hashCode(), который определяется как сумма его Map.Enytry * hashCode() с.

Map.Entry hashCode() определяется как xor для ключа hashCode() и значения hashCode().Ваши ключи String s - они имеют четко определенные hashCode() (две одинаковые строки всегда имеют одинаковые hashCode()).Ваши значения - ExampleClass экземпляров - им также нужен четко определенный hashCode().

В итоге, карта, содержащая { s1 -> ec1, s2 -> ec2 }, будет иметь хэш-код, равный: 

(s1.hashCode() ^ ec1.hashCode()) + (s2.hashCode() ^ ec2.hashCode())

означает, что зависит от ExampleClass hashCode().

Если ExampleClass реализовал hashCode() таким образом, что равен ExampleClasse s дают равные hashCode() s, все будет хорошо работать.Если ExampleClass не реализовал hashCode(), он будет использовать Object hashCode(), что почти всегда даст вам другие hashCodes().

1 голос
/ 21 июля 2011

Простое решение состоит в том, чтобы просто переписать хэш каждого объекта на карте или какой-нибудь простой его вывод. Поскольку a ^ a = 0 и a ^ b ^ a = b для всех a и b (xor является коммутативным, ассоциативным и его собственным обратным), а поскольку xor дешев, ваши операции добавления и удаления могут просто xor (возможно, производного) хеш-кода добавленного или удаленный элемент.

Возможно, вы захотите использовать производное хеш-значение, чтобы избежать случаев, когда ваша карта имеет все те же ключи и значения, но некоторые сопоставления между ними транспонируются. Простой производный хеш может быть key.hashCode() - value.hashCode(), что позволит избежать большинства этих случаев.

Итак, ваш код может выглядеть так: 

public class MyMap<K, V> extends HashMap<K, V>{
    private int hash = 0;
    @Override
    public int hashCode() {return hash;}
    @Override
    public V put(K key, V value) {
        V old = super.put(key, value);
        if (old != null) this.hash ^= key.hashCode() - old.hashCode();
        this.hash ^= key.hashCode() - value.hashCode();
        return ret;
    }
    @Override
    public V remove(K key) {
        V ret = super.remove(key);
        if (ret != null) this.hash ^= key.hashCode() - ret.hashCode();
        return ret;
    }
}

Обратите внимание, что некоторые из более продвинутых методов (например, добавление нескольких элементов из коллекции) могут быть или не быть безопасными в зависимости от реализации.

...