Алгоритмы с нуля
Хеширование: тест на припоминание
Припоминание сильнее перечитывания. Для каждого вопроса проговорите или запишите полный ответ по памяти, прежде чем открывать образец — именно усилие припоминания закрепляет хеширование, когда оно нужно на собеседовании или в два часа ночи.
Восстановите ключевые механизмы юнита — что даёт hash function, как разрешаются collision, почему load factor управляет стоимостью, почему resize — это O(1) amortized, и какие паттерны построены сверху — не заглядывая в уроки.
- 01Что на самом деле даёт hash function и какова цена этого O(1) поиска в среднем?
- 02Что такое collision и как separate chaining её разрешает?
- 03Определите load factor и объясните, почему именно он, а не общее число элементов, управляет стоимостью поиска.
- 04Почему вставка в hash table — это O(1) amortized, хотя одна вставка может быть O(n)?
- 05Сравните seen-паттерн и паттерн дополнения и дайте задачу, которую каждый решает за один проход.
- 06Когда hash table перестаёт давать O(1) и что с этим делать?
Если вы смогли восстановить каждый ответ по памяти, вы держите стержень юнита: hash function даёт доступ O(1) в среднем ценой памяти и порядка; collision неизбежны, и chaining хранит их в списках на бакет; load factor — а не сырое число элементов — задаёт среднюю длину цепочки и тем самым стоимость; resize держит его ограниченным за O(1) amortized; а паттерны seen, дополнение, частотный подсчёт и группировка — это всё та же механика в применении. Гарантия условна, и рандомизированный хеш — то, что защищает её от недоверенного входа.