Какой ключ для словаря с интернированными строками

Я хочу связать структуру данных, кэшированную в памяти, с набором интернированных строк и использовать переданный экземпляр интернированной строки для поиска связанной с ней структуры данных.

Предопределенный набор строк будет около 1000. Затраты на заполнение кеша можно игнорировать, но мне нужен высокопроизводительный поиск.

public class InternedExtras
{
  public DateTime Prop1 {get; set; }
  public Decimal Prop2 {get; set; }
}

В идеале я бы создал словарь со ссылкой на интернированную строку, но .Net не предоставляет ссылки на объекты как определенный тип.

Если я объявлю свой словарь как:

Dictionary<string, InternedExtras>

тогда я обеспокоен тем, что переопределение равенства System.String вызовет сравнение значений строки char во время поиска в словаре, что будет неэффективно.

Вариант будет:

Dictionary<int, InternedExtras> _extrasDictionary

InternedExtras GetInternedExtras( string knownToBeInterned )
{
  return _extrasDictionary[ knownToBeInterned.GetHashCode() ];
}

Однако я никогда полностью не понимал математику хэш-кода и понимаю, что уникальность не гарантируется.

Средняя длина моих интернированных строк составляет 50 символов, и я могу использовать последнюю версию .Net.


person camelCase    schedule 09.03.2017    source источник


Ответы (1)


Я действительно думаю, что это ваш самый эффективный вариант:

Dictionary<string, InternedExtras> _extrasDictionary;

Выполнение следующего вида на самом деле очень эффективно!

InternedExtras extras = _extrasDictionary[interned];

Сравнение символов, на которое вы ссылаетесь, будет вызываться только для небольшого подмножества строк. Это связано с тем, что interned.GetHashCode() будет использоваться для группировки ключей в «сегменты».

Этот вопрос содержит гораздо больше деталей по этому вопросу:

Как работает хеш-таблица?

person dana    schedule 09.03.2017
comment
@ dana - Спасибо за уверенность в производительности Dictionary/HashCode. Буду ли я прав, думая, что System.String не хранит хэш-код строки между вызовами someString.GetHashCode? - person camelCase; 09.03.2017
comment
На самом деле я так не думаю (см. ссылку на исходный код ниже). Я просто знаю, что Dictionary<K,V> — это де-факто способ быстрого поиска в памяти и часть BCL (то есть реализованная Microsoft). Если у вас есть какие-либо сомнения, вы должны запустить несколько тестов производительности. referencesource.microsoft.com/#mscorlib/system/string.cs - person dana; 09.03.2017