Алгоритмы с нуля
Хеширование: соберите hash map с resize
Читать про chaining, load factor и amortized resize — не то же самое, что заставить их работать. Постройте hash map от массива вверх — без встроенного Map под капотом, — затем загоните её в худший случай и посмотрите, как теория проступает в числах.
Превратите модель юнита в рабочий код и измеренные доказательства: реализуйте set/get/delete поверх массива цепочек, делайте resize по порогу load factor и докажите экспериментами, что поиски — O(1) в среднем, что resize — O(1) amortized, и что плохой хеш обрушивает её до O(n).
Реализуйте hash map с нуля поверх сырого массива, используя separate chaining и resize по порогу load factor, затем спроектируйте эксперименты, демонстрирующие её среднее, amortized и худшее поведение реальными измерениями — а не голословно.
- Набор тестов корректности: round-trip set/get/has/delete, перезапись существующего ключа возвращает новое значение (а не дубликат), удаление ключа убирает только эту запись из его цепочки, и все ключи переживают resize.
- Таблица результатов для эксперимента A, показывающая среднее число сравнений на поиск примерно плоским по N от 1k до 100k, с измеренным load factor рядом.
- Таблица или график для эксперимента B, показывающий пики стоимости на вставку в точках resize, при том что накопленное среднее на вставку остаётся ограничено малой константой.
- Таблица результатов для эксперимента C с плохим хешем, показывающая рост сравнений на поиск примерно линейно с N, плюс абзац-объяснение, связывающий это с длиной цепочки = load factor и формулой O(1 + alpha).
- Добавьте автоматический shrink-on-delete: когда load factor падает ниже 0.25, уменьшайте массив вдвое и перехешируйте. Покажите, что это держит память ограниченной при delete-heavy нагрузке, не ломая поиски.
- Добавьте рандомизированный seed в hash function (подмешайте случайное значение на экземпляр в h) и продемонстрируйте, что два экземпляра кладут одни и те же ключи в разные бакеты — защита от атакующего, подбирающего коллидирующие входы.
- Реализуйте вариант с open addressing (линейное пробирование) с тем же интерфейсом, затем сравните его сравнения на поиск и память с chained-версией при load factor 0.5, 0.75 и 0.9.
- Используйте свою HashMap (не встроенную), чтобы решить two-sum и group-anagrams, и подтвердите по своей инструментации, что оба работают за один проход O(n) по входу.
Это цикл за каждой hash map, которой вы когда-либо воспользуетесь: массив плюс hash function дают доступ O(1) в среднем, chaining поглощает неизбежные collision, load factor управляет длиной цепочки, а resize держит её ограниченной за O(1) amortized. Построив её один раз и измерив среднее, amortized и худшее поведение, вы превращаете «hash map — это O(1)» из лозунга в то, что можно доказать — и точно знать, когда это перестаёт быть правдой.