HashMap на Java, 100 миллионов записей

Question

Я хочу хранить 100 миллионов терминов и их частоты (в текстовой базе данных) в HashMap <String, Double>. Это дает мне ошибку «Недостаточно памяти». Я попытался увеличить кучу пространства до -Xmx15000M. Однако он проходит полчаса, а затем снова бросает одно и то же исключение. Размер файла, с которого я пытаюсь читать слова и частоты, составляет 1,7 ГБ.

Любая помощь будет высоко оценена.

Спасибо :-)

Answer 1

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

В зависимости от ввода, дерево Патрисии может быть еще лучше.

(Кроме того, если это действительно слова с естественного языка, вы уверены, что вам действительно нужны 100 000 000 записей? Большинство часто используемых слов удивительно низки, коммерческие решения (предсказание слов, коррекция орфографии) редко используют более 100 000 слова, независимо от языка.)

Answer 2

100 миллионов терминов вы почти наверняка за пределом того, что должно быть сохранено в памяти. Сохраните свои условия в какой-либо базе данных. Либо используйте коммерческую базу данных, либо напишите что-нибудь, что позволит вам получить доступ к файлу, чтобы получить нужную вам информацию. Если формат файла, который у вас есть, не позволяет быстро получить доступ к файлу, а затем преобразовать его в тот, который делает - например, сделать каждую запись фиксированным размером, чтобы вы могли мгновенно вычислить смещение файла для любого номера записи. Сортировка записей позволит вам быстро выполнить двоичный поиск. Вы также можете написать код, чтобы значительно ускорить доступ к файлам без необходимости хранить весь файл в памяти.

Answer 3

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

Answer 4

Ваша проблема заключается в том, что необработанный текст 1,7 ГБ составляет более 1500 МБ, даже без накладных расходов, добавленных отдельными строковыми объектами. Для огромных сопоставлений вам нужно либо использовать базу данных, либо карту с поддержкой файлов, это будет использовать дисковое пространство вместо кучи.

Update

Я не думаю, что выделение 15 ГБ для кучи возможно для большинства JVM. Он не будет работать с любым 32-битным jvm, и я не думаю, что будет работать 64-битный jvm. 15 ГБ памяти должны работать на 64-битном jvm, когда доступно достаточное количество ОЗУ.

Answer 5

По какой причине это не удалось, я согласен с приведенными выше ответами.

DB - хороший выбор. Но даже коммерческий уровень БД они также предложили бы «Разделение» данных для эффективного действия.

В зависимости от вашей среды я могу предложить использовать ваши данные для нескольких узлов, подключенных через локальную сеть. На основе значения ключа

Узел 01 имеет ключевое начиная с «а» Узел 02 имеет ключевое starging с «B» ....

Так что ваша программа внезапно изменилась к сети программирования ..

Answer 6

Его плохой дизайн. Имея 1.7GB данных в памяти на HashMap, я сделал бы любой из двух:

1. Упорство все данные (файл/базу данных) и иметь верхний 1% или что-то в памяти. Используйте некоторый алгоритм для определения, какие идентификаторы будут в памяти и когда.

2. Использование memcached. Самый простой выход. Распределенная хешируемая память. Это именно то, для чего используются DHT.

Answer 7

Другие ответы уже указывали, что проблема заключается в использовании памяти. В зависимости от вашей проблемной области вы можете создать ключевой класс, который уменьшил общий объем памяти. Например, если ваш ключ состоит из фраз естественного языка, вы можете разделить и ставить слова, составляющие фразу; например

public class Phrase { 
    private final String[] interned; 

    public Phrase(String phrase) { 
    String[] tmp = phrase.split(phrase, "\\s"); 

    this.interned = new String[tmp.length]; 

    for (int i=0; i<tmp.length; ++i) { 
     this.interned[i] = tmp[i].intern(); 
    } 
    } 

    public boolean equals(Object o) { /* TODO */ } 
    public int hashCode() { /* TODO */ } 
} 

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

Answer 8

Если вам нужен только легкий магазин KeyValue (Map), я бы посмотрел на Redis. Это очень быстро и имеет возможность сохранять данные в случае необходимости. Единственным недостатком является то, что вам нужно запустить хранилище Redis на Linux-машине.

Если вы ограничены Windows, MongoDB является хорошим вариантом, если вы можете запустить его на 64-битной основе.

Answer 9

Откажитесь от HashMap и загрузите все эти данные в HBase или в один из других хранилищ данных NoSQL и напишите ваши запросы в терминах MapReduce операций. Это подход, используемый Google Search и многими другими сайтами, использующими огромные объемы данных. Он доказал, что он масштабируется до практически бесконечного размера.

Answer 10

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

Например, кот = Кошки = кошки = Cat

или

плавать = плавание = проплывает

попробовать погуглить "Портер Штеммер"

Answer 11

Рассмотрим заменив его cdb. До 4 ГБ и:

Успешный поиск в большой базе данных обычно занимает всего два диска. Неудачный поиск занимает только один.

Answer 12

Существует интересное предложение от Terracotta - BigMemory, которое, кажется, именно то, что вы хотите. Я сам не пробовал и не знаю лицензионных условий и т. Д.

Answer 13

Задняя часть конверта: 1.7GB/100M = ср 18 байт = на срок и частота

Мы можем использовать handcoded HashMap при поддержке двух логических массивов.

1. Один для хранения INT частот (значения), а другой, чтобы построить массив типа обугленного C для имитации двумерного массива гр (массив символьных массивов). поэтому мы индексируем вычисление. мы не можем использовать двумерный массив java, поскольку он имеет слишком много накладных расходов на объект. Этот массив символов может содержать массивы символов фиксированного размера для представления ключей. Поэтому мы вычисляем хэш ключа и помещаем его в этот «двумерный массив», и если у нас есть конфликт, он может быть разрешен, скажем, линейным зондированием. пары ключей и значений связаны общим индексом массивов.

2. Хешмап должен использовать открытую адресацию, так как у нас недостаточно памяти для цепочки.

3. Мы можем сказать, что 10 экземпляров этой хэш-карты основаны на длине ключей; не может быть уверенным, поскольку я не знаю характеристик данных.

4. Space используется = 2 мощности 29 для целочисленного массива + (2 питания 4 (16 байт на строку) * 2 пау 27) = 3,5 гига

5. Если мы хотим, чтобы двойные частоты вместо Интс то, возможно, потребуется чтобы уменьшить размер строк соответствующим образом.

Answer 14

1,7 ГБ файл является относительно небольшим файлом для этого и хранения в ОЗУ. Я делаю это с гораздо большими файлами и сохраняю их в памяти без проблем. База данных может быть использована, но может быть чрезмерной или может быть идеальной в зависимости от того, что вы планируете делать с данными.

Как и другие люди, с естественным языком, скорее всего, будет относительно небольшое количество уникальных значений, поэтому на самом деле карта не будет настолько большой. Я бы не использовал java.util.HashMap, поскольку это - использование very inefficient in terms of memory, особенно при сохранении примитивных значений, таких как int. java.util.HashMap хранит примитивы как объекты. Он также сохраняет каждое значение внутри объекта HashMap.Entry, который отнимает память. Из-за этих двух факторов java.util.HashMap использует гораздо больше памяти, чем такие альтернативы, как Trove, Fastutil и другие:

• An Overview of memory saving techniques in Java
• Memory consumption of popular Java data types – part 2

Как уже упоминалось есть несколько реализаций карты которые не имеют этих проблем. Поскольку вы храните цифры на карте, дополнительное преимущество в том, что вы получите повышение производительности, потому что нет необходимости постоянно переключаться между объектами и примитивами (например, бокс/распаковка), поскольку вы добавляете новые значения на карту или обновляете старые значения. Эталонный различных примитивных HashMaps, которые лучше подходят для больших объемов данных можно найти on this post at the Java Performance Tuning Guide:

Answer 15

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

1E8 элементов в хэш-карта имеет требование заниженное размер из 1E8 * 2 * 16 байт, и берет на себя ключи и значения являются числами, так что требуется несколько гигабайт кучи доступных в вашей куче и от твой компьютер.

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

Обратите внимание, что программы начинают плохо работать, когда вы приближаетесь к пределу вашего компьютера.

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