Каков максимальный размер объекта карты в c ++ и java?

Question

Каков максимальный размер объекта hashmap / map в c ++ и java? Я хочу использовать hashmap, но я работаю с огромными данными. Я беспокоюсь, если я использую это на больших данных, это может привести к сбою из-за ограничения емкости. Это так? Если это так, что может быть альтернативным способом?

Answer 1

В Java size() для HashMap имеет тип int, поэтому на карте есть верхняя граница 2 ^ 31-1 элементов.

В C ++ map::max_size возвращает макс. количество элементов. В ванили map есть верхняя граница не более SIZE_T_MAX элементов, что составляет 2 ^ 64-1 на современном оборудовании.

Answer 2

Некоторая информация, которую нужно иметь в виду (общая картина):

Если ваши данные огромны, вы не можете хранить их в памяти.Вам нужно перейти на вторичное хранилище: HDD.Когда вы переходите на жесткий диск, вы теряете оптимизацию скорости хэш-карты.Каждый раз, когда вы идете на жесткий диск, вы сталкиваетесь с задержкой (время поиска и тому подобное).Поиск по хеш-карте, хранящейся на диске, становится линейным временем.

Я пытаюсь сказать, что карта бесполезна, если ваши данные не помещаются в памяти.

Лучшее решение - проиндексировать ваши данные.Сохраните индексы в памяти и укажите, где на диске находятся данные, которые вы ищете.Получить данные с диска.

Усовершенствуйте эту модель, используя RAID для хранения.Кроме того, переход к базе данных приводит к той же задержке, что и переход к жесткому диску.

Я предлагаю вам сохранить все значения в БД и сохранить словарь в памяти с хешами в качестве ключей.

Answer 3

Для Java:

HashMap имеет базовое хранилище - массив, который всегда имеет степень 2.Наибольшее это может быть 2 ^ 30.С коэффициентом загрузки по умолчанию 0,75 он будет пытаться расти и потерпеть неудачу на уровне около 750 миллионов записей.

TreeMap не ограничен и может иметь более 2 ^ 31 записей (однако size () вернет MAX_VALUE) Аналогичнодля ConcurrentSkipList и ConcurrentHashMap.

Answer 4

std :: map и hashmap являются динамическими структурами.Они растут по мере добавления элементов, пока система не сможет выделить для них память.

Функция-член max_size () дает верхний предел, который может поддерживать реализация класса (в коде), но этот предел равенкак правило, шире, чем емкость системы, на которую запускается сам код.

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

Вы можете эмпирически прийти к разумномуподсчитать, запрашивая у ОС объем свободной памяти, которую она может предоставить вашему процессу, и разделить ее на размер элемента как «ключ плюс значение плюс некоторые накладные расходы (обычно 20/24 байта)».

Answer 5

В C ++ std::map имеет функцию-член max_size() (соответствует количеству данных, которые он может содержать).

sizeof(std::map<...>) даст вам размер фактического объекта (соответствующийразмер фактического объекта, а не данных, которые он содержит).

Answer 6

Сама Java или C ++ не является пределом.На практике вы ограничены только ресурсами.

В зависимости от ваших требований подходы могут быть:

• более компактные структуры, такие как Patricia Trie
• решения для баз данных или карт на основе файлов
• распределенные решения на основе DHT

Попробуйте поискать здесь для некоторых советов.

Answer 7

Вы фактически будете ограничены объемом памяти вашей системы.

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

Answer 8

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

В качестве альтернативы, если небольшие блоки выделяются при расширении контейнера в реализации, ваш предел памяти представляет собой комбинацию памяти, которую имеет ваш компьютер, и ограничений, которые вы установили в вашей ОС (если ulimit случайно установлен в Linux или любой другой вариант Windows)

У класса есть функция-член max_size (), но если вы не установили это, это не должно влиять на вас. Итак, простой ответ - нет ограничений, кроме тех, которые зависят от вашего компьютера и ОС.

Answer 9

В Java размер Hashmap ограничен памятью JVM. Он может расти в размерах. Насколько я знаю, жесткого ограничения нет.

Не знаю о C ++.