Здравствуйте, dinama, Вы писали:

D>коллекция к которой делается запрос — неизменяема.
D>а запросы могут быть разные.
D>так-что если делать "ключ" из комбинаций атрибутов, то это могут быть десятки миллионов ключей.
D>если например, в коллекции 1000 элементов. по 10 атрибутов, которые имеют по 30 значений, то это
D>300000 тысяч ключей.

Мы оптимизируем память или время работы?

Похоже я все таки не понял задачу. Будет ли каждый запрос включать все 10 атрибутов, или в одном запросе может быть 1 атрибут, в другом например первый и третий атрибуты и тд.

Хэш таблица будет хранить не все 300000 ключей а их хеши, которых будет меньше. Но если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат. В изначальном примере было только 2 атрибута.


D>если пришел запрос, в котором для каждого атрибута задано по 10 допустимых значений, то это
D>100 запросов к хештаблице, с последующей вставкой в упорядоченый список.

Ну да, 10 атрибутов по 10 значений, в результате вы должны достать из таблицы 100 элементов, и да для этого надо 100 запросов. Если у вас хорошие хэш функции то можно считать что сложность запроса O(1)

Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?