Поиск структуры данных с быстрым поиском и небольшим размером

Question

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

Есть ли какая-либо структура в рамках, которая работает таким образом? Или я должен его создать?

Пример использования: У меня есть класс для пользователя, и в этом классе несколько (~ 20) списков различных данных. (доступ, привилегии, документы и т. д.). Мне нужно хранить пользовательские данные в кеше для быстрого доступа во время обратных передач - запросы к БД каждый раз очень медленные. Целые числа - это индексы в дБ,

Answer 1

Я думаю, что вы ищете HashSet http://msdn.microsoft.com/en-us/library/bb359438.aspx

Он реализован таким образом, что обеспечивает поиск O (1) (или так сказано в документации, однако я подозреваю, что это действительно амортизированный O (1), поскольку он реализован с помощью Hashtables ...) и поддерживает множество операций над множествами.

Я не уверен в его сериализованной форме, но я буду исследовать его дальше. Если вы действительно хотите сериализовать массив, вы всегда можете сделать

var mySet = new HashSet<T>(new []{ 1, 2, 3, 3, 4, 5, 4, 5 });
Serialize(mySet.ToArray());

и затем для десериализации просто создайте HashSet из сериализованного массива.