Структура данных Java для матрицы?

Question

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

Я мог бы просто использовать массив n by b для матрицы, но проблема в том, чтоЯ не хочу тратить впустую память, потому что только несколько элементов находятся в матрице.

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

Answer 1

Я бы реализовал разреженную матрицу .Используйте HashMap с индексом строки в качестве ключей, а затем либо HashMap или TreeMap для фактических элементов (с индексом столбца в качестве ключа).Если вы храните примитивные типы, я бы посоветовал взглянуть на Trove Java Collections Framework.Он оптимизирован для использования с примитивными типами.В любом случае, я бы предложил использовать его, поскольку все ключи могут быть примитивными.

Answer 2

Существует также несколько таблиц реализаций из библиотек Google Guava

Answer 3

Когда матрица разрежена, лучше использовать LinkedList.LinkedList будет лучше других вариантов с точки зрения пространства (при условии, что матрица разрежена).

Но учтите, что LinkedList имеет время O (n) для доступа.