Ускоряем доступ к данным в хэш-таблице | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Team Lead Архитектура и шаблоны проектирования Разработчик IoT C# Developer. Professional PostgreSQL Подготовка к сертификации Oracle Java Programmer (OCAJP) C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Symfony Framework Unity Game Developer. Basic JavaScript Developer. Professional Android Developer. Basic JavaScript Developer. Basic Java Developer. Professional Highload Architect Reverse-Engineering. Professional Java Developer. Basic PHP Developer. Professional Алгоритмы и структуры данных Framework Laravel Cloud Solution Architecture Vue.js разработчик Интенсив «Оптимизация в Java» Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool" PHP Developer. Basic
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK Дизайн сетей ЦОД Разработчик IoT PostgreSQL Экспресс-курс "Версионирование и командная работа с помощью Git"
-30%
Экспресс-курс «Введение в непрерывную поставку на базе Docker» Базы данных Reverse-Engineering. Professional Administrator Linux. Professional Network engineer Cloud Solution Architecture Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах» Супер-интенсив "Tarantool" Network engineer. Basic
Корпоративные курсы
Безопасность веб-приложений IT-Recruiter Дизайн сетей ЦОД Компьютерное зрение Разработчик IoT Вебинар CERTIPORT Machine Learning. Professional
-6%
NoSQL Пентест. Практика тестирования на проникновение Java QA Engineer. Базовый курс Руководитель поддержки пользователей в IT
-8%
SRE практики и инструменты Cloud Solution Architecture Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Infrastructure as a code Супер-практикум по использованию и настройке GIT Промышленный ML на больших данных Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» BPMN: Моделирование бизнес-процессов Основы Windows Server
Специализации Курсы в разработке Подготовительные курсы Подписка
+7 499 938-92-02

Ускоряем доступ к данным в хэш-таблице

Algo_Deep_23.11_site-5020-e50be1.png

Сначала разберёмся, что же такое хэш-таблица?

Это сложное слово состоит из двух слов: хэш и таблица. И слово «хэш», и слово «таблица» знакомы среднестатистическому пользователю компьютера по хэштегам в Твиттере и по электронным таблицам Excel и Google Spreadsheets.

Что же такое «хэш»? Это «отпечаток» каких-то данных, предполагающий, что данные однозначно идентифицируются этим отпечатком. Тэг же — это метка. Хэштег — это и хэш, и тэг. Хэш, который является тэгом. По нему можно быстро найти релевантную цепочку сообщений в Твиттере. Теперь вернёмся к нашим хэш-таблицам.

Зададимся двумя целями

Сделаем некую специальную табличку для экономии места и для быстрого доступа к данным. Как это можно сделать? Идентификатором строчки сделаем хэш. Хэш — это отпечаток наших входных данных для поиска в таблице, чтобы не тянуть в таблицу все исходные данные.

Пример — хотим сделать список столиц всех стран: hash1-20219-dae52d.jpg Для каждой страны сделаем некий идентификатор, рассчитываемый через некую функцию. Назовем его хэш. При заполнении этой хэш-таблицы для каждой страны считаем хэш через функцию от страны, записываем его в первую колонку таблицы, во вторую пишем её столицу. При поиске столицы по стране сначала для заданной страны считаем хэш, ищем его в первой колонке и находим страну во второй колонке. hash2-20219-349eea.jpgВсё вроде бы хорошо, место мы сэкономили (числа получились короче, чем потенциальные страны), найти столицу можем для любой страны, но поиск работает чуть лучше, чем если бы мы поместили название страны в таблицу полностью, потому что для поиска не нужно сравнивать всю строку, а только число, но в худшем случае нужно перебрать все страны, пока мы найдём нужный хэш.

Как ускорить процесс?

Для ускорения доступа усовершенствуем нашу хэш-функцию, дополнительно взяв остаток от деления на число записей в таблице. Тогда она будет выглядеть так: hash3-20219-89d9fb.jpgВеликолепно! Теперь мы считаем хэш-функцию и по результату отсчитываем смещение от начала хэш-таблицы за одну операцию! Задача решена?

Не тут-то было… оставляйте комментарии о возможных проблемах!

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться