0
Что произойдет, если вы попытаетесь вставить два одинаковых объекта с другим хэш-кодом в hashmap?Что произойдет, если вы попытаетесь вставить два одинаковых объекта с другим хэш-кодом в hashmap?
A
ответ
2
Это означает, что функция хэша сломана (по крайней мере, с точки зрения хэш-таблицы), поэтому она может вести себя непредсказуемым образом (возможно, что дубликат будет вставлен).
1
Давайте рассмотрим простую реализацию хешированной карты для хранения пар ключ-значение.
Предположим, что имеется выделенная область хранения размером alloc_size для ключей и такая же для значений.
Индекс хранения для хранения новой пары вычисляется простым модулем, например hash_index = (hash_code(key) % allocated_size).
Если слот на этом hash_index свободен, мы закончили, мы просто сохраним ключ и значение в этом индексе.
Если слот в этом hash_index уже занят, то это зависит:
- если ключ в этом слоте равно, то, что мы сделали, мы нашли
hash_index, и мы будем переписывать соответствующее значение; - Если ключ в этом слоте отличается, тогда мы должны сканировать хранилище на
hash_index+1, пока не найдем равный ключ или пустой слот.
Теперь предположим, что у нас есть hash_codes 33 и 53 для двух равных ключей.
- Если allocated_size 20, то два hash_codes равны по модулю 20, и мы будем хранить один объект (вторая вставка будет перезаписывать первый);
- Если alloc_size равно 21, то два hash_codes различаются по модулю 21, и мы можем сохранить два входа этого ключа, каждый со своим значением, в зависимости от заполнения слотов между двумя hash_index и в зависимости от порядка введение пар ...
Что вы наблюдаете здесь типично неопределенное поведение. Я уверен, что более эллаборативные реализации будут страдать от эквивалентных проблем, поэтому нет, два равных ключа НЕ ДОЛЖНЫ иметь другой хеш-код, это сломанная хеш-функция.
Если у них разные хэш-коды, то они по-разному различаются по отношению к хэшмапу. – bolov
Два объекта, для которых функция равна (или эквивалентной), используемой hashmap, дает true, но имеют разные хэш-коды: если эта ситуация разрешена или нет или как она обрабатывается, я думаю, что я зависит от языка/реализации. – bolov
Простой ответ: они будут вставлены. О да, будут дубликаты. Но то, как два одинаковых объекта получают разные хэш-коды, очень озадачивает. Разве это не означает, что хеширующая функция ошибочна? – legends2k