Хранение большого количества конфигураций в Java

Question

У меня есть тип данные (назовем его данные), который содержит 2 порции информации:

int config 
byte weight 

Этого типа данных являются преобразованием из серии 32 Булевых. Я должен выполнить изменения этих 32 булевых преобразований обратно в этот тип данных и сохранить его. Проблема заключается в том, что я хочу хранить только уникальные записи, исключающие любые дубликаты. Проблема в том, что для этого типа данных существует 2^33 возможных конфигураций.

Я пытался что-то вроде этого:

static class searchedconfigs { 
    Data[] searchedconfigs; 
    int position; 
    public searchedconfigs() { 
     searchedconfigs = new Data[150000]; 
    } 
    public void initiateposition() { 
     position = 0; 
    } 
    public boolean searchfield(Data Key, int entries) { 
     boolean exists = false; 
     for (int i = 0; i <= entries; i++) { 
      if (searchedconfigs[i] == Key) { 
       System.out.println("break"); 
       exists = true; 
       break; 
      } 
     } 
     return exists; 
    } 
    public void add(Data config, int position) { 
     searchedconfigs[position] = config; 
    } 
    public int getPosition() { 
     return position; 
    } 
    public void storePosition() { 
     position++; 
    } 
} 

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

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

Answer 1

Используйте HashSet, а также осуществлять equals и hashCode в Data, например, так:

import java.util.Objects; 

class Data { 
    int config; 
    byte weight; 

    @Override 
    public int hashCode() { 
     return Objects.hash(config, weight); 
    } 

    @Override 
    public boolean equals(Object other) { 
     if (other == null) return false; 
     if (!(other instanceof Data)) return false; 
     if (other == this) return true; 

     return this.config == other.config && this.weight == other.weight; 
    } 
} 

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

Answer 2

Какое ограничение пространства вы фактически используете? Массивы в java ограничены Integer.MAX_VALUE (2^31-1?). Вы превысили:

• Максимальное количество элементов в массиве?
• Куча, выделенная для JVM?
• Доступная оперативная память + место подкачки на машине?

Если это количество элементов, посмотрите на альтернативную структуру данных (см. Ниже). Если вы перегружаете кучу, тогда вы должны выделить больше памяти для своего приложения (-Xmx arg для JVM при запуске вашей программы). Если у вас на самом деле заканчивается память на коробке, то трюки для экономии пространства вы получите до сих пор; в конечном итоге рост данных превзойдет эти вещи. В этот момент вам нужно посмотреть либо горизонтальное масштабирование (распределенные вычисления), либо вертикальное масштабирование (получение большего размера коробки с большим объемом ОЗУ).

Если вы просто перегружаете массив, потому что он не может быть размером за пределы max int и space, это действительно проблема, которую я бы избегал использовать HashSet, поскольку это займет больше места, чем прямой список/массив или альтернативный Установите реализацию как TreeSet.

Для эффективной работы HashSets им нужна огромная хэш-таблица, чтобы уменьшить количество столкновений хэшей в пространстве. HashSet в Java имеет коэффициент загрузки по умолчанию, равный 75%, а это означает, что когда он перейдет по этой емкости, он будет больше изменять размер, чтобы оставаться под коэффициентом нагрузки.В общем, вы торгуете большим объемом пространства для более быстрого ввода/удаления/поиска времени для элементов в наборе, которые, как я считаю, являются постоянным временем (Big O of 1).

TreeSet должен требовать, чтобы ваша емкость хранилища была такой же, как количество элементов (незначительные накладные расходы), но при компромиссе увеличенного поиска & время ввода, которое является логарифмическим (Big O of Log (n)). Список имеет аналогичную характеристику хранения (зависит от используемой реализации), но имеет время поиска N, если оно неупорядочено. (Вы можете искать различные варианты вставки/удаления/поиска для различных реализаций списков &, заказанных по сравнению с неупорядоченными, они очень хорошо документированы)

Я просто хочу отметить, что при использовании HashSet вы торгуете эффективностью пространства для более быстрого просмотра время ожидания (Big O of 1). Вы должны выделить место для хэш-таблицы, которая должна быть больше, чем общее количество элементов в вашей коллекции. (Конечно, есть предостережение, что вы можете заставить размер вашего ведра в основном быть 1, имея ужасную функцию хэширования, которая эффективно вернула бы вас к характеристикам производительности неупорядоченного списка;)