Java: память эффективное хранение массивов целых чисел

Question

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

Краткая информация об ошибке: Мне нужно хранить большое количество массивов целых чисел, чтобы избежать дублирования. Я делаю следующее:

LinkedList<int[]> ArraysAlreadyUsed; 

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

Вопрос: Что является хорошим/лучшим способом сделать это, чтобы свести к минимуму объем занимаемой памяти? Есть ли способ представления таких массивов с помощью хэш-строки? И будет ли это лучше?

Answer 1

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

Извлечение элементов происходит в O (1). В списке (LinkedList или ArrayList) поиск происходит в O (n).

Связанный список также является плохим выбором в период использования памяти. Infact для каждого элемента имеет ссылку на предыдущий элемент и ссылку на следующий элемент.

С точки зрения занятости, лучшим решением является использование массива int (не ArrayList) со ссылкой на последний вставленный идентификатор.

Answer 2

Это может иметь смысл создать оболочку, которая реализует equals и hashcode, так что вы можете поместить массивы в Set для O (1) contains/add. Что-то вроде:

public class IntArray { 
    private final int[] array; 
    private final int hash; 

    public IntArray(int[] array) { 
    this.array = array; 
    this.hash = Arrays.hashCode(this.array); //cache hashcode for better performance 
    } 

    @Override 
    public int hashCode() { 
    return hash; 
    } 

    @Override 
    public boolean equals(Object obj) { 
    if (obj == null) return false; 
    if (getClass() != obj.getClass()) return false; 
    final IntArray other = (IntArray) obj; 
    return Arrays.equals(this.array, other.array); 
    } 
} 

Вы можете просто использовать набор:

Set<IntArray> arrays = new HashSet<>(); 

Это создаст небольшие накладные расходы (guestimate менее 20 байт на упаковке), но будет работать гораздо лучше, чем LinkedList.

Если память ваша единственная задача, то вы могли бы пойти на int[][], но это будет более болезненным ...

Answer 3

Использования вместо int[] в BitSet может уменьшить объем памяти.