Alternative data structure for a multidimensional array

I have a quick question, I am working a project that requires an object that has an id and a x, y coordinate. This is all stored into an object and the idea is that it is placed into a 2D array. However there is a possibility of a great number of objects created and开发者_开发百科 stored as well size of the array might be large. Is there something that is more efficient in size and speed in which the data can be stored? I read about using a map might this be my best option.

---

The answer depends on what your application's primary access pattern is.

If the primary access pattern is looking up the object at a particular x,y coordinate, then you are probably best served by one of the following:

• a 2D array (as you currently have); i.e. Thing[][],
• a Map<Point, Thing>, or
• a Map<Integer, Map<Integer, Thing>>.

(I suggest the 3rd option, because the second option is liable to result in creation of a temporary Point object each time you do a lookup on the data structure. There are other ways to deal with this, but it makes the application more complicated.)

If the 2D array is sparsely populated, then the Map approaches will save space at the cost of time. If the array is densely populated then the Map approaches are liable to use more space than a 2D array.

If the primary access pattern is to look for objects near a given x,y coordinate (or in a region) then you probably need something like a quad-tree data structure.

One final thing to note is that there are unavoidable overheads in using the standard collection types, especially when one or more of the parameter types is a primitive type.
If you performance requirements are particularly "hard", then designing and implementing a custom data structure by hand will save space and time ... if you do it right. But the downsides are that you have significantly more code to write, test and maintain, and that a custom data structure won't be compatible with the standard collection APIs.

---

Map<Double, java.awt.Point>

The java.awt.Point will work, or you could make your own data type to hold the x, y co-ordinate.

This will give you fast lookups but use more memory than a straight array (not sure how much more, probably not anything too bad).

Another alternative is something tha combines the three things (ID, x, y) and stores them in an array and then uses Arrays.binarySearch to get at them. It would require that the array be sorted.

Edit:

If you want to map from the x, y to the double you would do:

Map<java.awt.Point, Double>