Ускоряем доступ к данным в хэш-таблице
Сначала разберёмся, что же такое хэш-таблица?
Это сложное слово состоит из двух слов: хэш и таблица. И слово «хэш», и слово «таблица» знакомы среднестатистическому пользователю компьютера по хэштегам в Твиттере и по электронным таблицам Excel и Google Spreadsheets.
Что же такое «хэш»? Это «отпечаток» каких-то данных, предполагающий, что данные однозначно идентифицируются этим отпечатком. Тэг же — это метка. Хэштег — это и хэш, и тэг. Хэш, который является тэгом. По нему можно быстро найти релевантную цепочку сообщений в Твиттере. Теперь вернёмся к нашим хэш-таблицам.
Зададимся двумя целями
Сделаем некую специальную табличку для экономии места и для быстрого доступа к данным. Как это можно сделать? Идентификатором строчки сделаем хэш. Хэш — это отпечаток наших входных данных для поиска в таблице, чтобы не тянуть в таблицу все исходные данные.
Пример — хотим сделать список столиц всех стран:
Для каждой страны сделаем некий идентификатор, рассчитываемый через некую функцию. Назовем его хэш. При заполнении этой хэш-таблицы для каждой страны считаем хэш через функцию от страны, записываем его в первую колонку таблицы, во вторую пишем её столицу. При поиске столицы по стране сначала для заданной страны считаем хэш, ищем его в первой колонке и находим страну во второй колонке.
Всё вроде бы хорошо, место мы сэкономили (числа получились короче, чем потенциальные страны), найти столицу можем для любой страны, но поиск работает чуть лучше, чем если бы мы поместили название страны в таблицу полностью, потому что для поиска не нужно сравнивать всю строку, а только число, но в худшем случае нужно перебрать все страны, пока мы найдём нужный хэш.
Как ускорить процесс?
Для ускорения доступа усовершенствуем нашу хэш-функцию, дополнительно взяв остаток от деления на число записей в таблице. Тогда она будет выглядеть так:
Великолепно! Теперь мы считаем хэш-функцию и по результату отсчитываем смещение от начала хэш-таблицы за одну операцию! Задача решена?
Не тут-то было… оставляйте комментарии о возможных проблемах!
