Компактная структура данных для хранения большого набора целочисленных значений

Я работаю над приложением, которое должно передавать большие наборы Значения Int32 . Ожидается, что наборы будут содержать ~ 1 000 000–50 000 000 элементов, где каждый элемент является ключом базы данных в диапазоне 0–50 000 000 . Я ожидаю, что распределение идентификаторов в любом заданном наборе будет эффективно случайным в этом диапазоне. Операции, которые мне нужны с набором, очень просты:

• Добавить новое значение
• Перебрать все значения.

Существует серьезное беспокойство по поводу использования памяти этими наборами, поэтому я ищу структура данных, которая может хранить идентификаторы более эффективно, чем простой List или HashSet . Я просмотрел BitArray , но это может быть расточительным, в зависимости от того, насколько редки идентификаторы. Я также рассмотрел побитовое дерево , но я не уверен, как вычислить эффективность использования пространства этого решения для ожидаемых данных. Фильтр Блума был бы великолепен, если бы я только мог терпеть ложноотрицательные результаты.

Я был бы признателен за любые предложения структур данных, подходящих для этой цели. Меня интересуют как готовые, так и нестандартные решения.

РЕДАКТИРОВАТЬ : Чтобы ответить на ваши вопросы:

• Нет, элементы не нужно сортировать
• По "пройти" вокруг "Я имею в виду, что оба метода передаются между методами и сериализуются и отправляются по сети. Я определенно должен был упомянуть об этом.
• В памяти может быть приличное количество этих наборов одновременно (~ 100).