Эффективная реализация «постоянного» набора ADT

Question

Мне нужно реализовать «постоянный» набор. То есть структура данных, которая поддерживает только тест на членство. Кроме того (конечно), мне нужна фабричная процедура, которая, учитывая список элементов, строит постоянный набор.

Обратите внимание, что не только мутация не разрешена для константного набора, но дополнительно мне не нужна операция «добавить», которая возвращает новый набор констант (то есть, когда инициализация происходит, меня интересует только проверка наличия элемента в наборе или нет).

Гольд-хэш-таблицы являются очевидным выбором здесь, но мне интересно, можем ли мы как-то воспользоваться тем фактом, что нам нужно поддерживать только одну операцию (и, при построении множества, мы знаем, что все его элементы будут быть)? Есть ли структура данных (специализированный тип хеш-таблицы, возможно), которая будет особенно хорошо работать здесь?

Answer 1

Как @Alexandre C., упомянутый в комментарии, это отличное место для использования идеальной хеш-таблицы. Идеальная хеш-таблица - хеш-таблица, в которой используется хеш-функция, которая не гарантирует столкновений между ее элементами. Существуют различные схемы для этого; одним из наиболее распространенных и простых вариантов является использование FKS perfect hash table, в котором используется двухслойная хеш-таблица. Он гарантирует наихудшие тесты O (1) членства и чрезвычайно эффективен на практике.

Надеюсь, это поможет!

Answer 2

С теоретической точки зрения он не получает быстрее, чем O (1) хэш-таблицы, просто потому, что O (1) является самым быстрым (кроме того, что вообще ничего не делать, что является O (0);)).

Если ваша хэш-таблица очень большая (чтобы ее можно было хранить на диске или даже распределять на нескольких машинах), то bloom filter может дать вам быстрый вероятностный тест для членства.

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