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