В прошлой заметке мы говорили о HashMap, hashcode() и немного equals().
Краткое содержание: записывая пару ключ-значение (запись) в HashMap, мы помещаем ее в одну из ячеек (бакет) массива. То, в какую именно ячейку будет помещена запись (индекс ячейки в массиве) определяется по значению hashcode() ключа. Поскольку в один бакет может быть помещено несколько записей, то в бакет записываются не сами записи, а содержащие их связные списки.
В HashMap могут быть помещены записи только с уникальными ключами. Уникальность определяется методом equals(). То есть если
new Integer(1).equals(new Integer(1)); - вернул true - объекты равны.
Чтобы вся эта система корректно работала, необходимо соблюдать 2 правила (и пожалуйста, дальше - читать обязательно, потому что именно этот вопрос любят задавать на собеседованиях):
1. равные объекты должны иметь один и тот же hashcode
то есть, если equals - true, hashcode() возвращает одинаковое число
2. объекты, имеющие разный hashcode - неравны
то есть если hashcode() возвращает разные числа, equals обязано вернуть false
Почему соблюдать эти правила необходимо?
Легче всего это аргументировать, представив, что будет если эти правила будут нарушены.
Представим что у нас объект А и объект В - равны по equals, но возвращают разные hashcode. Мы добавляем запись с ключом-объектом А в HashMap. Далее мы пытаемся туда же добавить запись с ключом-объектом В. Что должно произойти? Поскольку А и В равны, вторая запись не должна добавиться. А что происходит на самом деле?
При добавлении второй записи высчитывается hashcode() для В, и по нему находится бакет, в котором предположительно будет находиться новая запись, если ключ В будет уникален. Для проверки уникальности вызывается метод equals() ключей записей, которые находятся в этом бакете. По счастливой случайности в этом бакете может находиться запись с ключом А, тогда все отработает корректно и вторая запись не добавится. Но вероятнее всего запись А будет в другом бакете, поэтому проверки покажут уникальность В. В результате мы будем иметь в HashMap с равными ключами А и В, что нарушает контракт HashMap.
Проблемы возникают и при поиске объектов. Ну а представить что в этом случае происходит - это уже на самостоятельную работу
Примечание: неравные объекты могут иметь одинаковый hashcode. В этом случае они хоть и попадают в один бакет, но все равно отсекаются при проверке объектов на equals().
Примечание 2: соблюдать правила взаимосвязь equals()-hashcode() необходимо, если вы переопределяете эти функции. В реализации по умолчанию (эти функции уже определены в базовом объекте - Object) эти правила уже соблюдены.
Краткое содержание: записывая пару ключ-значение (запись) в HashMap, мы помещаем ее в одну из ячеек (бакет) массива. То, в какую именно ячейку будет помещена запись (индекс ячейки в массиве) определяется по значению hashcode() ключа. Поскольку в один бакет может быть помещено несколько записей, то в бакет записываются не сами записи, а содержащие их связные списки.
В HashMap могут быть помещены записи только с уникальными ключами. Уникальность определяется методом equals(). То есть если
new Integer(1).equals(new Integer(1)); - вернул true - объекты равны.
Чтобы вся эта система корректно работала, необходимо соблюдать 2 правила (и пожалуйста, дальше - читать обязательно, потому что именно этот вопрос любят задавать на собеседованиях):
1. равные объекты должны иметь один и тот же hashcode
то есть, если equals - true, hashcode() возвращает одинаковое число
2. объекты, имеющие разный hashcode - неравны
то есть если hashcode() возвращает разные числа, equals обязано вернуть false
Почему соблюдать эти правила необходимо?
Легче всего это аргументировать, представив, что будет если эти правила будут нарушены.
Представим что у нас объект А и объект В - равны по equals, но возвращают разные hashcode. Мы добавляем запись с ключом-объектом А в HashMap. Далее мы пытаемся туда же добавить запись с ключом-объектом В. Что должно произойти? Поскольку А и В равны, вторая запись не должна добавиться. А что происходит на самом деле?
При добавлении второй записи высчитывается hashcode() для В, и по нему находится бакет, в котором предположительно будет находиться новая запись, если ключ В будет уникален. Для проверки уникальности вызывается метод equals() ключей записей, которые находятся в этом бакете. По счастливой случайности в этом бакете может находиться запись с ключом А, тогда все отработает корректно и вторая запись не добавится. Но вероятнее всего запись А будет в другом бакете, поэтому проверки покажут уникальность В. В результате мы будем иметь в HashMap с равными ключами А и В, что нарушает контракт HashMap.
Проблемы возникают и при поиске объектов. Ну а представить что в этом случае происходит - это уже на самостоятельную работу
Примечание: неравные объекты могут иметь одинаковый hashcode. В этом случае они хоть и попадают в один бакет, но все равно отсекаются при проверке объектов на equals().
Примечание 2: соблюдать правила взаимосвязь equals()-hashcode() необходимо, если вы переопределяете эти функции. В реализации по умолчанию (эти функции уже определены в базовом объекте - Object) эти правила уже соблюдены.
Комментариев нет:
Отправить комментарий