K>И вообще если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат.

на самом дели три разные ситуации:

1. большинство запросов не имеют результат
2. каждый результативный запрос извлекает большинство элементов
3. каждый запрос извлекает минимальное количество элементов

в первом случае оптимизацией будет отбросить "заведомо нерезультативные запросы" (например, упомянутый тут фильтр Блума)
во-втором случае — оптимизации не требуются
в третьем случае — здорово было-бы извлекать быстро удовлетворяющие запросу элементы

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

если элемент Е имеет значения атрибута A (a1, a2) и атрибута B (b1, b2)
то в хеш этот элемент должен быть вставлен 4 раза: a1b1 a2b1 a1b2 a2b2

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