Hash tables, Map и Set

Hash tables лежат в основе maps и sets, превращая keys в buckets. Average lookup, insert и delete имеют constant time, но memory растет с числом keys, а pathological collisions могут ухудшить поведение. В JavaScript Map предсказуемее сохраняет identity ключей, чем plain object dictionaries.

На интервью: Типовые задачи: two-sum complements, frequency counts, grouping anagrams, first seen indexes, deduplication и visited sets для traversal.

Типовые ошибки: Не игнорируйте memory cost. Явно проговаривайте equality semantics для object keys. Для ordered output помните, что hashing решает lookup, но не sorted order.

Чеклист:

• Выбирайте Map для arbitrary keys.
• Считайте memory как O(k).
• Объясните collision assumptions.
• Отделяйте lookup от ordering.