Во многих языках у вас есть возможность получить список ключей из хеш-таблицы. Подобно методу keySet() для хеш-карт в java. Как это можно получить из заполненной хеш-карты? Разве хэш-функция необратима? У вас тоже есть ключи в отдельном списке?
Итак, когда я использую функции для получения списка ключей, используемых в заполненной хеш-таблице, какова временная сложность этой функции?
Для моей конкретной проблемы я знаю максимальное количество записей в хеш-таблице. Это помогает?
Практически каждая хеш-таблица хранит ключи в дополнение к значениям. В любом случае это необходимо для разрешения коллизий хэшей (в некоторых случаях коллизии доказуемо невозможны, но это требует предварительного перечисления полного набора ключей, поэтому это не применимо к хеш-таблице общего назначения). То есть хеш-таблица {"foo": 1, "bar": 2} выглядит не так:
1
2
а скорее вот так
("foo", 1)
("bar", 2)
Тогда итерация по ключам — это просто итерация по базовой структуре хеш-таблицы.
В любой разумной реализации касание всех ключей в естественном порядке (не отсортированное) равно O (текущий размер таблицы, включая пустые слоты).
В реализации, которая объединяет записи (например, Java, как вы можете наблюдать в код итератора LinkedHashMap здесь), размер таблицы не имеет значения. Алгоритм проходит по связному списку.
Вам не нужно знать хеш-ключи, потому что итерации касаются структуры данных напрямую, а не с использованием ключей.
