ХЕШ-ТАБЛИЦА это не O(1)! Пишем СВОЮ HashTable

Чтобы понять хеш-таблицу, надо написать хеш-таблицу! По-другому никак... Привычно считается, что вставка, удаление и получение значения по ключу выполняется за O(1). Так ли это на самом деле? Что такое амортизированная сложность? Зачем и когда делать resize? Проясним окончательно эти вопросы, написав хеш-таблицу своими ручками :} ___ telegram: https://t.me/AlcoRhythm Курс "Алгоритмы и структуры данных": https://t.me/AlcoRhythm/2 Поиск контактов через префиксное дерево: https://t.me/AlcoRhythm/33 ___ Что посмотреть: - LeetCode 355 - ПРИМЕР абстрактного МЫШЛЕНИЯ https://youtu.be/kgEHsx_5GYU - ЗАЧЕМ ПРОГРАММИСТУ АЛГОРИТМЫ https://youtu.be/WkNnAq8bqiY - LeetCode для начинающих: почему ты НЕ ПОНИМАЕШЬ задачи и что с этим делать https://youtu.be/BBsljS3UCms - Базовые АЛГОРИТМЫ НУЖНЫ! Доказательство https://youtu.be/7M5gha43_dY ___ TimeCode: 00:00 - Зато СВОЯ 00:38 - Пример 01:24 - Что такое ХЕШ-ФУНКЦИЯ 02:13 - Зачем нужен hashValue 04:22 - Возникновение КОЛЛИЗИЙ 07:48 - AlcoRhythm: АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ 08:18 - struct HashTable 10:19 - Получение индекса из hashValue 11:00 - Установка значения 14:06 - Получение значения по ключу 15:04 - Удаление пары по ключу 16:21 - Создание subscript 18:04 - Resize HashTable 25:04 - shrink HashTable