"Правильная" коллекция, чтобы использовать для получения элементов в 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) действительно достигнут.

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