Какую структуру данных надо использовать что бы посчитать уникальные ip в огромном количестве?
================================================================================================

 Дан файл с ip адресами. ip могут повторяться. Вес файла многократно превышает объём оперативной памяти. Надо посчитать количество уникальных ip. Простое решение, не учитывающее объём задачи - загнать все ip в хештаблицу и количество элементов в ней будет ответом. Вот только проблема - такая хештаблица не влезет в оперативку. Надо какую-то другую структуру данных использовать. Какую? И вообще, что почитать на тему highload задач и алгоритмов? 

 Если вам допустима потеря точности - посмотрите на hyperloglog. Можно во много раз уменьшить потребление памяти.   

  

Такая структура реализована, например, в [redis](https://redis.io/commands/pfcount). Там она займёт 12 Кбайт при погрешности в 0,81%. 

 Все IP адреса в мире легко засунутся в 16 гигабайт. Не так уж и много.   

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

  

Делаем древовидную структуру, например по октетам.  

Если взять первые два октета, нам потребуется всего 65536 бакетов.  

  

В каждом бакете у нас будет 256 слотов, в каждом слоте - еще 256 отрезков адресов. Если нам повстречались все 256 вариантов самого младшего октета, у нас весь отрезок аккуратно схлопнется.  

  

То есть в листьях дерева мы храним не сами адреса, а пары (база, количество) 

 Для битовой таблицы достаточно 256*256*256*256/8 = 512Мб памяти. 

 Не надо меня слушать, но смеха ради это все решается работой с файловой системой) На каждый ip создаем одноименный файл, а потом просто делаем листнинг директории) 

 Как уже сказали, оно все отлично помещается в память в битмапе. Но если бы не помещалось (допустим, это не 32-битные ip адреса, а 48-ми битные MAC адреса) , то нужно было бы использовать какую-либо внешнюю сортировку и получить все адреса отсортированными. А дальше за один проход легко подсчитать уникальные.  

  

Сортировать можно разными способами. Например, читать кусками сколько помещается в память, отсортировать как угодно, записать на диск. Потом получившиеся отсортированные куски можно объединять, как в сортировке слиянием.  

  

Еще можно использовать radix sort.  

  

Если есть еще и ограничения на использование места на диске, и в память оно не помещается, то можно воспользоваться [фильтром Блума](https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D1%8C%D1%82%D1%80_%D0%91%D0%BB%D1%83%D0%BC%D0%B0). Заведите его на сколько у вас там памяти хватит. Возьмите много хеш функций. Ну и потом за один проход проверяйте, есть ли уже считанный адрес в фильтре. Если нет - добавляйте и увеличивайте счетчик. Вот только это вероятностый метод и он может недосчитать чего-то из-за ложноположительных срабатываний блум фильтра. 

> Дан файл с ip адресами. ip могут повторяться. Вес файла многократно превышает объём оперативной памяти.

  

Сколько оперативки?  

  

> Надо посчитать количество уникальных ip.  
> 
> Простое решение, не учитывающее объём задачи - загнать все ip в хештаблицу и количество элементов в ней будет ответом.

  

Есть же алгоритмы сортировки, которым не нужно все грузить в память. Работать будет долго, но рано или поздно создаст файл, где все будет отсортировано. А количество уникальных IP в отсортироавнных данных уже школьный уровень.