Однократная запись для чтения строки со строкой в ​​объект

Question

Я ищу структуру данных, которая может превзойти Dictionary<string, object>.У меня есть карта, которая содержит N элементов - карта строится один раз, а затем читается много-много раз.Карта не изменяется в течение всей жизни программы (новые элементы не добавляются, никакие элементы не удаляются и элементы не переупорядочиваются).Поскольку карта не изменяется, она не должна быть поточно-ориентированной, даже если приложение, использующее ее, является многопоточным.Я ожидаю, что ~ 50% поисков произойдет для элементов, не находящихся на карте.

Dictionary<TKey, TItem> довольно быстро, и я могу в итоге использовать его, но мне интересно, есть ли другая структура данных, которая быстрее для этого сценария.Хотя остальная часть программы, очевидно, стоит дороже, чем эта карта, она используется в критичных для производительности деталях, и я хотел бы максимально ускорить ее.

Answer 1

То, что вы ищете, это Perfect Hash Function .Вы можете создать его на основе списка строк, а затем использовать его для словаря.

Неуниверсальный HashTable имеет конструктор , который принимает IHashCodeProvider, что позволяет вам указатьВаша собственная хеш-функция.Я не смог найти эквивалент для Dictionary, поэтому вам, возможно, придется вместо этого прибегнуть к использованию Hashtable.

Вы можете использовать его внутренне в своем классе PerfectStringHash, который будет выполнять все приведение типов дляyou.

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

РЕДАКТИРОВАТЬ: Очевидно, кто-то уже реализовал некоторые алгоритмы Perfect Hash в C # .

Answer 2

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

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

Answer 3

Производительность чтения универсального словаря «близка к O (1)» в соответствии с замечаниями в MSDN для большинства TKey (и вы должны получить довольно хорошую производительность, используя только строковые ключи). И вы получаете это из коробки, бесплатно, из фреймворка, не реализуя свою собственную коллекцию.

http://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.90).aspx