Как представить небольшую карту целых чисел в виде массива?

Question

Допустим, я хочу построить маленькую простую карту, где ключом является N целых чисел (фиксированное, обычно одно), а значением является M целых чисел (также фиксированное, обычно одно).

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

Кто-нибудь определил простую структуру данных, которая может это сделать?

[РЕДАКТИРОВАТЬ] Ответы, которые у меня были до сих пор, похоже, показывают, что никто не понимает мой вопрос, поэтому я постараюсь уточнить. Во-первых, забудьте о M и N; только представьте, что я сказал один ключ int и одно значение int. AFAIK, если вы хотите использовать обычную HashMap, где ключ является целым числом, а значение является целым числом, то в итоге вы получите не менее 2 + 3 * N объектов, где N - количество записей.

Я хочу знать, можете ли вы упаковать все эти целые числа в один массив примитивных целых чисел , сократив количество объектов до двух, независимо от количества ключей. Один для int [], а другой для объекта-обертки, который дает вам немного похожий на карту интерфейс. Ни мои ключи, ни мои значения никогда не будут нулевыми. И мне не нужна полная стандартная реализация java.util.Map. Мне просто нужно, получить, положить и удалить, брать и возвращать примитивные целые числа не целочисленные объекты. Access не должен быть O (1), как в обычном HashMap.

Answer 1

Мне кажется, я понимаю проблему, я попытаюсь найти решение:

Очень простой способ добиться того, чего вы хотите, - сохранить один двумерный массив int array[NKeys][2], где array[i][0] является ключом, а array[i][1] является одним из значений М.Затем вы можете выполнить итерацию массива и для каждого запроса key вернуть все array[i][1], например array[i][0] == key.Конечно, это работает для одного ключа int, а не для набора ключей int.Кроме того, это ужасно по сложности.Я не могу придумать какой-либо другой способ сделать это без добавления большего количества объектов Java / указателей Си.

Answer 2

Насколько я знаю, ответ - нет, по крайней мере, в Java.

Но вы можете просто хранить свои ключи и значения в массиве int (каждый) с соответствующими индексами, и если высохраняя отсортированный массив ключей, вы можете выполнять бинарный поиск.

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

Так что вам придется найти компромисс между размером массива и количеством перераспределений, возможно, что-то похожее на то, как это делает ArrayList.

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

Answer 3

Так как класс ArrayList (на самом деле AbstractList) имеет метод equals, переопределенный соответствующим образом, вы можете напрямую использовать карту следующим образом:

Map<List, List> map = new HashMap<List, List>();