How to represent a small map of integers as an array?

Let's say I want to build a small simple map, where the key is N integers (fixed, usually one) and the value is M integers (also fixed, usually one).

Now I would like to store the data an an integer array, for space efficiency. I am programming in the JVM, but it should not really make a difference, unless the algorithm would require storing pointers as integers.

Has anyone defined a simple data structure that can do that?

[EDIT] The answers I had so far seem to show that no one understands my question, so I'll try to clarify. Firstly, forget about the M and N; just imagine I said one int key and one int value. AFAIK, if you want to use a normal HashMap where the key is an integer and the value is an integer, then you will end up with at least 2 + 3 * N objects, where N is the number of entries.

What I want to know is, can you pack all those ints in a single array of primitive i开发者_开发百科nts, reducing your object count to two, independent of the number of keys. One for the int[], and one for the wrapper object that gives you some map-like interface. Neither my keys nor my values will ever be null. And I don't need a full standard java.util.Map implementation either. I just need, get, put, and remove, taking and returning primitive ints not Integer objects. Access does not need to be O(1), like in a normal HashMap.

As far as I know, the answer is no, at least not in Java.

But you can simply keep your keys and your values in an int array (each) with matching indexes, and if you keep the key array sorted, you can perform a binary search.

The trouble with Java arrays though is that they're fixed size structures, so if you want to store more elements than your arrays are allocated to, reallocating them is quite expensive.

So you'll have to make a trade-off between the size of the array and the number of reallocations, maybe something similar to how ArrayList does it.

The other, somewhat smaller problem is that int being a primitive type, there's no null value, but you can designate a special int value to denote null.

I think I understand the problem, I'll take a shot at a solution:

The very simple way of achieving what you want is to keep a single two dimensional array int array[NKeys][2], where array[i][0] is the key and array[i][1] is one of the M values. You could, then iterate the array and for every query of a key, return all array[i][1] such that array[i][0] == key. Of course, this works for a single int key rather than a set of int keys. Also, this is awful in complexity. I can't think of any other way of doing this without adding more Java objects/C pointers.

Since the ArrayList(actually AbstractList) class has equals method overridden appropriately, you can directly use a map like so:

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