Философия Java


Понимание hashCode( ) - часть 2


Метод put( ) просто помещает ключ и значение в соответствующий ArrayList. В main( ) загружается SlowMap, а затем печатается так же медленно, как и работает.

Это показывает, что не так сложно произвести новый тип Map. Но как подсказывает имя, SlowMap не является быстрым, так что вы, вероятно, не будите использовать его, если вы имеете альтернативные варианты. Проблема заключается в поиске ключа: здесь нет упорядочивания, поэтому используется простой линейный поиск, являющийся самым медленным способом поиска.

Главное преимущество хеширования - скорость: хеширование позволяет искать исключительно быстро. Так как узкое место в скорости поиска ключа, одно из решений проблемы может быть в хранении ключей в отсортированном порядке и использование Collections.binarySearch( ) для выполнения поиска (упражнения в конце этой главы проведут вас по этому процессу).

Хеширование идет дальше, говоря, что все, что вы хотите делать - это хранить ключи где угодно так, чтобы они могли быть быстро найдены. Как вы увидите в этой главе, самая быстрая структура, в которой хранится группа элементов - это массив, который будет использован для представления информации о ключах (обратите особое внимание, что я сказал “ключевой информации”, а не самих ключей). Также вы увидите в этой главе, что однажды выделенный массив не может изменить размер, так что мы имеем проблему: мы хотим быть способны хранить любое число значений в Map, но если число ключей фиксировано размером массива, как мы это можем сделать?

Ответ заключается в том, что массив не хранит ключи. Из объекта ключа получается число, которое будет индексироваться в массиве. Это число является хеш кодом, производимым методом hashCode( ) (на научном компьютерном языке - это хеш-функция), определенном в Object и, предположительно, перегруженная вашим классом. Для решения проблемы фиксированного размера массива: один и тот же индекс может производиться разными ключами. То есть, здесь могут быть коллизии. Поэтому, не имеет значения, насколько велик массив, потому что каждый объект ключа будет пребывать где-то в этом массиве.




Начало  Назад  Вперед