Работает ли HashSet? Конечно. Но это не тот вопрос, который вы задали. Вы запросили максимально быстрый поиск.
Это самый быстрый из возможных? Нет, конечно нет, ни в коей мере.
Прежде всего, чтобы говорить о «самом быстром», нам нужно точно описать, что означает «самый быстрый». Вы имеете в виду:
- наименьший наихудший возможный случай время
- наименьшее среднее время усреднения по многим временам
- наименьшее среднее время с учетом конкретной схемы использования
- что-то еще
? Пожалуйста, уточните, что означает «максимально быстрый». Мы можем разработать для вас алгоритм, который является в теории самым быстрым из возможных , только если мы точно знаем, что самый быстрый из возможных означает для вас.
Например, предположим, что вы пишете компилятор. Что-то, что мы должны делать все время в компиляторах, это проверять, есть ли конкретная строка в списке строк. Возможно, мы проверяем, является ли строка ключевым словом, поэтому нам нужно выяснить, находится ли данная строка внутри набора {"int", "double", "for", "foreach", "class" ... }
Мы можем поместить их в хэш-набор и получить приличную производительность. Но если бы мы хотели получить наилучшую возможную производительность , мы могли бы сделать намного лучше. Мы могли бы, например, выполнить анализ нескольких миллиардов строк существующего исходного кода, чтобы выяснить, какие ключевые слова были наиболее распространенными, а какие - наименее распространенными, а затем написать собственную хеш-таблицу, оптимизированную для (1) быстрого отклонения вещей, которые были не ключевые слова вообще, и (2) быстрое распознавание наиболее распространенных ключевых слов за счет распознавания других ключевых слов.
Обратите внимание, что это требует статического анализа; хотя он хорошо работает в типичных случаях, он работает плохо в тех редких случаях, когда используется много редких ключевых слов. Другой подход, который мы могли бы использовать, - написать самонастраивающуюся хеш-таблицу, которую динамически идентифицировали при частом поиске определенных строк.
Рассмотрим, например, если вы пишете реализацию среды выполнения JScript. Мы часто должны искать строку в наборе строк:
for(i = 0; i < 10; ++i) { foo.bar(i); }
Здесь мы должны найти строку «bar» внутри объекта, обозначенного «foo» десять раз. Хеш-таблица внутри «foo», которая реализует этот поиск, замечает первый раз, когда в цикле используется «bar», поэтому она динамически настраивает структуру хеш-таблицы, так что время секунд в цикле, поиск быстрее. Это стратегия, которую мы использовали в нашей реализации JScript.
Теперь, это оптимизирует регистр для циклов, но делает этот случай потенциально медленнее, чем это могло бы быть:
for(i = 0; i < 10; ++i) { foo.bar(i); foo.blah(i); foo.abc(i); }
потому что мы больше не анализируем и не понимаем: «Эй, мы просто повторно оптимизировали эту хэш-таблицу три раза, и теперь мы собираемся сделать все это снова, возможно, нам следует просто оставить все как есть».
К счастью для нас, мы, как и вы, не искали быстрый поиск . Мы искали только достаточно быстрый поиск.
Можете ли вы тщательно и полностью описать, каков ваш вариант использования для самого быстрого поиска ? Есть много алгоритмов, которые вы можете использовать для ускорения поиска, но они становятся очень сложными.