«Правильная» коллекция, чтобы использовать для получения элементов в O (1) времени в C # .NET?

Question

Я часто делаю что-то, если храню кучу строковых значений и хочу, чтобы через O (1) через некоторое время я смог найти их:

foreach (String value in someStringCollection)
{
    someDictionary.Add(value, String.Empty);
}

Таким образом, я могу с комфортом выполнить постоянное время поиск этих строковых значений, таких как:

if (someDictionary.containsKey(someKey))
{
    // etc
}

Однако я чувствую, что я обманываю, делая значение String.Empty . Есть ли более подходящая коллекция .NET, которую я должен использовать?

Answer 1

Если вы используете .Net 3.5, попробуйте HashSet . Если вы не используете .Net 3.5, попробуйте C5 . В противном случае ваш текущий метод в порядке (bool, как подсказывает @leppie, лучше, или нет, как подсказывает @JonSkeet, dun dun dun!).

HashSet<string> stringSet = new HashSet<string>(someStringCollection);

if (stringSet.Contains(someString))
{
    ...
}

Answer 2

Вы можете использовать HashSet<T> в .NET 3.5, иначе я бы просто придерживался текущего метода (на самом деле я бы предпочел Dictionary<string,bool>, но такой роскоши не всегда хватает).

Answer 3

вы можете добавить начальный размер к вашему хешу. Я не уверен, что C # реализован иначе, чем Java, но обычно он имеет некоторый размер по умолчанию, и если вы добавите больше, это расширит набор. Однако хэш правильного размера важен для достижения максимально близкого к O (1) значения. Цель состоит в том, чтобы получить ровно 1 запись в каждом ведре, не делая его действительно огромным. Если вы выполните поиск, я знаю, что для определения размера хеш-таблицы предложено соотношение, предполагающее, что вы заранее знаете, сколько элементов вы добавите. Например, что-то вроде «хэш должен иметь размер в 1,8 раза больше количества добавляемых элементов» (не реальное соотношение, просто пример).

Из Википедия :

С хорошей хеш-функцией, хеш таблица обычно может содержать около 70% -80% столько же элементов, сколько и настольные слоты и до сих пор хорошо работают. В зависимости от разрешения столкновения механизм, производительность может начать страдать либо постепенно, либо резко, так как больше элементов добавлено. Чтобы справиться с этим, когда коэффициент загрузки превышает некоторый порог, это необходимо выделить новый, больший таблицу, и добавьте все содержимое оригинальный стол к этому новому столу. В Класс Java HashMap, например, пороговое значение коэффициента загрузки по умолчанию равно 0,75.

Answer 4

Вероятно, мне следует задать этот вопрос, потому что я так часто вижу проблему. Что заставляет вас думать, что словари O (1)? Технически, единственное, что может быть чем-то вроде O (1), - это доступ к стандартному массиву с фиксированными границами с целочисленным индексом, использующему целочисленное значение индекса (не было поиска в массивах, реализованных таким образом).

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

Я вижу эти вопросы и даже вижу ответы, которые утверждают, что O (1) [не по этому конкретному вопросу, но я их выхожу вокруг], без каких-либо обоснований или объяснений того, что требуется, чтобы убедиться, что O (1) фактически достигнут.

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