HashMap vs two dimesional Array (loading/memory)

You can test it on your data. I've never actually done this, but I've seen it. You would create both an array and a hashmap and fill them up with your data and then run a search through them. You can get the time that it takes to do the search (this I don't particularly remember how, but it's simple) and then simply compare the two.

Also, I think that array's use a hashmap to store their data (if true, this might be dependent on what language) so I would imagine that maybe a hashmap would be faster than an array, but as you can tell I'm going off a hunch.

And to any future posters, any confirmation on this would be helpful.

To be specific I am using Java. Don't know how relevant that is, but it might be important.

Great idea btw! It slipped my mind to literally time the events and compare the two. That should solve the problem when I start getting a lot of files/objects to load/search.

Java makes it easier; look at the Java API for ArrayList and HashMap. That information should help you better understand the differences between the two. I've never tried this, but perhaps you could do something like:



Also, keep in mind that the difference between the two searches will probably be very small so you would want to make sure to have a high precision (expand to a far out decimal place) on your time variables.

I'm not sure in what capacity you are using these data structures, but Hashmaps are extremely efficient. If you need 2000x2000 variables, and can index them into the array, then fine, ... but in most cases I doubt you want this.

Can you give more informatino

I'm creating worlds in my game based on a series of map objects which load from .lvl files. Each object stores variables like tile/object locations, images for these files, etc.

The max size of the world is 2000x2000 level files and the origination level is going to be 1000x1000. When starting up the game, the code loads up all the .lvl files and enters them by coordinates (at this time via hashmap). My question, since i don't know very much about hashmaps (I haven't taken a course that explains them yet) is whether it would be more efficient to load the map objects into an array thats [2000][2000] or input them into a hashmap.

If that doesn't clarify it let me know. What information were you looking for specifically?

James

Study data structures.
The answer to your questions are "Yes."

Every (good) data structure is a trade-off of various types of performance (search & memory usage are 2 types, also consider insert & removal).
Hash tables are almost magic - they are asymptotically optimal and you can even beat the O(n log n) comparison sort best performance and sort in linear time O(n) but they are not appropriate for every scenario.

I believe the data structure you are looking for is called a "sparse array".
Assuming most/nearly-all of the 4,000,000 elements in your maps are identical (empty?) a sparse data structure will have less memory consumption and could have better (or worse) performance depending on what you're doing with it.

Why are you searching for something in the 2000x2000 field? If you know where to look you can calculate the bounding indices and nail the search in O(1) time.

If you don't know where to look, then you need to create an index (vector/list/1D array) of interesting objects in the map to perform the search on (which is effectively a sparse array).

- I almost forgot to add my canonical tidbit; even bubble-sort is optimal in a way the other sorts are not - it consumes the least amount of code.

I'm not sure I understand this correctly, but wouldn't a binary search tree be better for searching through the data?

If you don't need to search through the data, but simply access a known element, I'd think that the array would be faster than using a hash map (that is, if you go "down" from level (1000,1000), you'll access myLevels[1000,1001]).

If, however, you need to search through your data structure every time you change rooms, I'd think that something like a binary search tree would be a lot more efficient than iterating over the array (O(log n), versus O(n) for iterating over the array).

But as Shannon said, I don't see any reason (from what you have told us) to search through your set, when you can access it directly.

Quote:

If, however, you need to search through your data structure every time you change rooms, I'd think that something like a binary search tree would be a lot more efficient than iterating over the array (O(log n), versus O(n) for iterating over the array).

To add to this, remember that in order to do a binary search, your data must be sorted. Sorting your data will run in O(n), but you only need to do that once. After that, a binary search will take only O(log n). That said, if you're going to be doing more than one search, it is more efficient to sort your data to allow for these binary searches. On the other hand, if you're only going to be doing a single search, then doing a linear search through the array would be more efficient (since a linear search will take O(n), same as the sort).