Какова лучшая структура данных для поиска, если что-то существует?

Question

Я хочу сохранить список вещей, с которыми я уже сталкивался в моем рекурсивном цикле, чтобы я мог избежать пересчета одних и тех же вещей снова и снова. Какая структура данных для этого наиболее эффективна?

Глядя на анализ сложности, Hashtables представляется наиболее эффективным для поиска. Тем не менее, кажется неэффективным хранить структуру данных пар «ключ-значение», когда все, что меня интересует, это поиск того, существует ли указанный ключ.

Я подумал, что, возможно, набор будет хорошей идеей, но егосложность, кажется, не указывает на это.

Answer 1

Набор, вероятно, является правильным абстрактным типом данных для этого, поскольку на самом деле единственная информация, которую он кодирует, - находится ли элемент внутри или нет.

Однако использование набора не определяет конкретную реализацию. В большинстве случаев вы должны быть в состоянии найти тип набора, реализованный с использованием хеширования, или некоторый тип древовидной структуры. Какой из них вы выберете, будет зависеть от того, будут ли вставляемые вами данные эффективно хэшироваться или упорядочены.

В некоторых библиотеках вы найдете наборы типов, которые реализованы с использованием типов карт библиотеки, но где значение игнорируется. ,Например, в rust тип стандартной библиотеки HashSet реализован с использованием типа HashMap.