Структура данных для распознавания повторных значений

Question

Я выполняю довольно большой поиск и получаю исключение System.OutOfMemoryException.

Проблема в том, что я храню строковый ключ для каждого состояния, которое я ранее посещал, как HashSet<sting>.Как только это достигает приблизительно 7 миллионов элементов, это терпит крах.Я думаю, что мне не нужно иметь возможность извлекать строки, а только распознавать, если они существуют в наборе.

Кажется, я помню специальную структуру данных для такого рода вещей, но я могу 'Я не помню его имя на всю жизнь.Если я правильно помню, у него были довольно постоянные требования к памяти, и вы добавляете в него элементы, и он может сказать вам с некоторой степенью уверенности, добавили ли вы какую-то ценность к нему.Я придумываю это, или это существует?Любые советы?

Answer 1

Возможно, вы думаете о фильтре Блума . Это дает вам вероятностный результат, когда вы проверяете, есть ли строка в наборе. Если это так, вы всегда найдете это. Если это не так, вы все равно можете обнаружить, что это так, в зависимости от того, что еще в вашем наборе. Требования к памяти меняются в зависимости от количества добавляемых вами уникальных элементов, но это на далеко меньше, чем занимал бы HashSet.

Answer 2

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

• В худшем случае поиск данных в дереве выполняется быстрее (O (м)) по сравнению снесовершенный хэш-стол.Несовершенная хеш-таблица может иметь ключевые коллизии.Ключевое столкновение - это отображение хеш-функции разных ключей в одну и ту же позицию в хеш-таблице.Скорость поиска в наихудшем случае в несовершенной хэш-таблице составляет O (N), но гораздо чаще O (1), а O (м) - время, потраченное на оценку хеш-функции.
• Нет столкновенийразные ключи в дереве.
• Баки в дереве, которые аналогичны корзинам хеш-таблиц, в которых хранятся коллизии ключей, необходимы, только если один ключ связан с более чем одним значением.
• нет необходимости предоставлять хеш-функцию или изменять хеш-функции, поскольку в дерево добавляется больше ключей.
• Три могут обеспечивать алфавитное упорядочение записей по ключу.

Answer 3

Для этого нет стандартной коллекции в .NET, но вы можете хранить много строк в Trie , используя намного меньше места, чем, например, хеш-таблица / set

Answer 4

Фильтр Блума ?

Answer 5

Вы говорите о классе Dictionary?

http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

Выдержка из MSDN:

Каждый ключ в Словаре должен быть уникальным в соответствии ссловарь сравнения равенства.Ключ не может быть нулевым, но значение может быть, если тип значения TValue является ссылочным типом.

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