Ускоряем доступ к данным в хэш-таблице | OTUS
🔥 BLACK FRIDAY!
Максимальная скидка -25% на всё. Успейте начать обучение по самой выгодной цене.
Выбрать курс

Курсы

Программирование
iOS Developer. Basic
-25%
Python Developer. Professional
-25%
Разработчик на Spring Framework
-25%
Golang Developer. Professional
-25%
Python Developer. Basic
-25%
iOS Developer. Professional
-25%
Highload Architect
-25%
JavaScript Developer. Basic
-25%
Kotlin Backend Developer
-25%
JavaScript Developer. Professional
-25%
Android Developer. Basic
-25%
Unity Game Developer. Basic
-25%
Разработчик C#
-25%
Программист С Web-разработчик на Python Алгоритмы и структуры данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Vue.js разработчик VOIP инженер Программист 1С Flutter Mobile Developer Супер - интенсив по Kubernetes Symfony Framework Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-25%
DevOps практики и инструменты
-25%
Архитектор сетей
-25%
Инфраструктурная платформа на основе Kubernetes
-25%
Супер-интенсив «IaC Ansible»
-16%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-25%
Супер-интенсив "SQL для анализа данных"
-16%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Администратор Linux. Виртуализация и кластеризация Нереляционные базы данных Супер-практикум по использованию и настройке GIT IoT-разработчик Супер-интенсив «ELK»
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться
🎁 Максимальная скидка!
Черная пятница уже в OTUS! Скидка -25% на всё!