Посмотрим на проблемы, которые возникают при имплементации хеш-таблицы, когда сложность добавления или удаления из нее не O(1), а линейная, и какие потенциальные атаки можно провести на эту структуру данных (и как их избегают в современных языках программирования на примере Java). Всем привет! Меня зовут Миша Рокс, я – разработчик в Яндексе, и сегодня мы глубже погрузимся в одну из основных и базовых структур данных любого языка – хеш-таблицу. Конкретно – мы посмотрим на проблемы, которые возникают...

Хеш-таблица (hashtable) — это структура данных, представляющая собой специальным образом организованный набор элементов хранимых данных. Все данные хранятся в виде пар хеш-значения. Данная структура похожа на словарь (map), но имеет особенности такие как применение хеш-функции для увеличения скорости поиска. Принцип работы данной структуры схож с каталогом книг. Все книги разложены в алфавитном порядке, но не на одном стеллаже, а для каждой буквы выделен отдельный стеллаж, поэтому нам не нужно по порядку перебирать все книги, а можно подойти к нужному стеллажу и искать уже там...