На этом шаге рассмотрим понятие коллизии.
В большинстве языков существуют свои хеш-таблицы. Вам не нужно знать, как написать собственную реализацию. Но быстродействие-то важно всегда! Чтобы понять быстродействие хештаблиц, необходимо сначала понять, что такое коллизии.
Нам нужно, чтобы хешфункция всегда отображала разные ключи на разные позиции в массиве.
На самом деле написать такую хеш-функцию почти невозможно. Рассмотрим простой пример: допустим, массив состоит всего из 33 ячеек.
И хеш-функция очень простая: элемент массива просто назначается по алфавитному признаку.
Вы хотите поместить цену апельсинов в хеш. Для этого выделяется первая ячейка.
После апельсинов в хеш заносится цена бананов. Для бананов выделяется вторая ячейка.
Пока все прекрасно! Но теперь в хеш нужно включить цену авокадо. И для авокадо снова выделяется первая ячейка.
Элемент уже занят апельсинами! Что же делать? Такая ситуация называется коллизией: двум ключам назначается один элемент массива. Возникает проблема: если сохранить в этом элементе цену авокадо, то она запишется на место цены апельсинов. И когда кто-нибудь спросит, сколько стоят апельсины, вы вместо этого сообщите цену авокадо! Коллизии - неприятная штука, и вам придется как-то разбираться с ними. Существует много разных стратегий обработки коллизий. Простейшая из них выглядит так: если несколько ключей отображаются на один элемент, в этом элементе создается связанный список.
В этом примере и "апельсины", и "авокадо" отображаются на один элемент массива, поэтому в элементе создается связанный список. Если вам потребуется узнать цену бананов, эта операция по-прежнему выполнится быстро. Если потребуется узнать цену апельсинов, работа пойдет чуть медленнее. Вам придется провести поиск по связанному списку, чтобы найти в нем "апельсины". Если связанный список мал, это не так страшно - поиск будет ограничен тремя или четырьмя элементами. Но предположим, что вы работаете в специализированной лавке, в которой продаются только продукты на букву "а".
Вся хеш-таблица полностью пуста, кроме одной ячейки. И эта ячейка содержит огромный связанный список! Каждый элемент этой хеш-таблицы хранится в связанном списке. Ситуация ничуть не лучше той, когда все данные сразу хранятся в связанном списке. Работа с данными замедляется.
Из этого примера следуют два важных урока:
- выбор хеш-функции действительно важен. Хеш-функция, отображающая все ключи на один элемент массива, никуда не годится. В идеале хеш-функция должна распределять ключи равномерно по всему хешу;
- если связанные списки становятся слишком длинными, работа с хеш- таблицей сильно замедляется. Но они не станут слишком длинными при использовании хорошей хеш-функции!
Хеш-функции играют важную роль. Хорошая хеш-функция создает минимальное число коллизий. Как же выбрать хорошую хеш-функцию?
На следующем шаге рассмотрим понятие быстродействия хеш-функции.
