Алгоритм получения уникального и одинакового хэш-кода для объекта при многократном запуске приложения

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

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

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


java hashcode
person saggy    schedule 12.11.2010    source источник
comment
Для какого объекта? Это твой собственный класс? Покажите нам код.   -  person casablanca    schedule 12.11.2010
comment
Разве уникальные и одинаковые не исключают друг друга?   -  person Gabe    schedule 12.11.2010
comment
Я не могу ничего придумать, где бы мне понадобилось это требование. Можете ли вы сказать, чего вы хотите достичь?   -  person Daniel    schedule 12.11.2010

Ответы (3)


arrow_upward
4
arrow_downward

Функция хэш-кода по умолчанию в Java может возвращать разные хэш-коды для каждого вызова JVM, потому что она может использовать адрес памяти объекта, изменять его и возвращать.

Однако это не является хорошей практикой кодирования, поскольку одинаковые объекты всегда должны возвращать один и тот же хэш-код! Прочтите о хэше код контракта, чтобы узнать больше. И в большинстве классов в Java уже реализована функция хеш-кода, которая возвращает одно и то же значение при каждом вызове JVM.

Проще говоря: все ваши объекты, содержащие данные, которые могут храниться в какой-либо коллекции, должны иметь реализацию equals и hashcode. Если вы программируете с помощью Eclipse или любой другой подходящей IDE, вы можете использовать мастер, который автоматически создает функции.

И пока мы это делаем: IMHO рекомендуется также реализовать Comparable‹T>, поэтому вы также можете использовать объекты в SortedSets и TreeMaps.

Пока мы этим занимаемся: если другим нужны ваши объекты, не забудьте Сериализуемый и Можно клонировать.

person Daniel    schedule 12.11.2010

arrow_upward
1
arrow_downward

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

Выполнение этих требований невозможно по ряду причин:

  • Невозможно гарантировать, что хэш-коды уникальны. Что бы вы ни делали в методе хэш-кода вашего класса, метод хэш-кода некоторых других классов может дать значение для некоторого экземпляра, которое совпадает с хэш-кодом одного из ваших экземпляров.

  • Невозможно гарантировать, что хэш-коды уникальны для всех запусков приложения даже только для экземпляров вашего класса.

Второе требует обоснования. Чтобы создать уникальный хэш-код, нужно сделать что-то вроде этого:

    static HashSet<Integer> usedCodes = ...
    static IdentityHashMap<YourClass, Integer> codeMap = ...

    public int hashcode() {
        Integer code = codeMap.get(this);
        if (code == null) {
            code = // generate value-based hashcode for 'this'
            while (usedCode.contains(code)) {
                code = rehash(code);
            }
            usedCodes.add(code);
            codeMap.put(this, code);
        }
        return code;
    }

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

Единственный способ заставить это работать — сохранить структуры данных usedCode и codeMap в подходящей форме. Даже (просто) сохранения уникальных хэш-кодов как части сохраняемых объектов недостаточно, поскольку существует риск того, что приложение может повторно выдать хэш-код для вновь созданного объекта, прежде чем считать существующий объект, содержащий хэш-код.

Наконец, следует отметить, что вы должны быть осторожны с использованием идентификационных хэш-кодов в любом месте решения. Хэш-коды удостоверений не уникальны для разных запусков приложения. В самом деле, если есть различия в каких-либо входных данных или если есть какая-либо недетерминированность, весьма вероятно, что данный объект будет иметь другое значение хэш-кода идентификации каждый раз, когда вы запускаете приложение.

ПОСЛЕДУЮЩИЕ

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

Вам нужно хранить хэш-коды в отдельном столбце таблицы. Но, учитывая ограничения, описанные выше, я не вижу, как это ускорит поиск. По сути, вам нужно искать в базе данных URL-адрес, чтобы определить его уникальный хэш-код.

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

person Stephen C    schedule 12.11.2010

arrow_upward
0
arrow_downward

Исходя из моего понимания вашего вопроса...

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

person Sid    schedule 12.11.2010