Друзья, продолжаем рассказывать про хеш-таблицу. Первая часть — в посте по ссылке. 🪣 Внутренне хеш-таблица является массивом, каждый элемент которого называется бакет (от англ.  bucket — «ведро»). Бакет может быть пустым или хранить одну или несколько пар ключ – значение. 🚩 Главный компонент хеш-таблицы — хеш-функция. Она используется во всех основных операциях: добавлении, поиске и удалении пары. Задача хеш-функции — преобразовать ключ пары в целое число и тем самым определить индекс бакета, в котором: 🌱 нужно разместить пару (при добавлении пары в хеш-таблицу) 🌱 сейчас находится пара (при поиске или удалении пары из хеш-таблицы) Результат работы хеш-функции называется хешем, а процесс преобразования в хеш — хешированием. 📌 Для одного и того же ключа хеш-функция всегда возвращает один и тот же результат — это основополагающее свойство, обеспечивающее правильную работу хеш-таблицы. 😱 Иногда хеш-функция возвращает одинаковый хеш для разных ключей. Такая ситуация называется коллизией. Для ее обработки применяются разные механизмы: 🌱метод цепочек — несколько пар с одинаковым хешем хранятся в одном бакете в виде связного списка 🌱открытая адресация — коллизия разрешается размещением пары в свободном бакете, поиск которого происходит по определенным правилам ⚠️ В хеш-таблице не могут храниться две разные пары с одинаковыми ключами. Если в таблицу добавляется пара с ключом, который уже есть в таблице, новая пара заменит старую, а не добавится как отдельный элемент. Более подробно про хеш-таблицы и механизмы разрешения коллизий мы рассказываем в нашем курсе «Алгоритмы и структуры данных для начинающих». Ставьте реакцию: 🔥 — если уже сталкивались с хеш-таблицами на практике 👀 — если знаете о них только в теории #алгоритмы #структурыданных