Generating values and keys to fill a map, and which type of map should I use

Question

My idea is to generate keys and values inside of a map, but I'm unsure as to what type of map I should use. This would be my very first time ever using a map, and I've heard that HashMaps aren't too good for keeping a set of values to that specific key.

So, here's what I want to accomplish. I want a map with they key "X,Y", where x and y are between 1 and 8, with the values being an arrayList of "X-1,Y-2","X-1,Y+2","X+1,Y-2","X+1,Y+2", etc. I've never done maps, so I suppose I lack a general concept of mapping, so I would like to know if this would actually be possible, and if so, could someone give me an example to base my code off of.

It's for a project that's due very soon that I waited until now to start, even though I had two weeks to do it, so I'm hoping for a quick answer. Thanks in advance.

Example of what I want:

Key -> "5,5" : Values -> ["4,7", "4,3", "6,7", "6, 3", "7,4", "7,6", "3,4", "3,6"]

On a side note, my goal is to have each value actually resemble a key in the map, so it will be easy to use one of the values to use another key with the same name.

I.E "4,7" leads to Key -> "4,7" which if impossible with mapping I can simulate outside of it with code.

Answer 1

First off, you don't need a map. There are only 64 possible values here (8x8). You could use a 2d array if you wanted. This could make things easier to work with. In this case, you would just use data[y][x] and store the List at that location.

Furthermore, you don't even need an array, since the values are entirely based on the key. You could have a function that looks like: Collection<Pair<Integer,Integer>> getData(Integer x, Integer y) which returns the set of values that you're getting back (I'm borrowing Pair from Apache Commons Lang, but its easy enough to code).

---

Alright, you really want to use a Map. And as you note, there are several versions of implementing classes that one could use. It really boils down to two, maybe three (and a fourth that I like) that you'll use in most cases.

They can be classified in two different sub interfaces - those that implement SortedMap NavigableMap (use Navigable Map, it is the replacement for SortedMap with Java 1.6) and those that don't.

If you want things to be stored and returned in order (and be able to do things with the ordering of the keys), then you want a NavigableMap. It gives you functions like higherKey(K key) which will return the next higher value stored in the map above the key passed in. However, a NavigableMap can only store sortable keys. If the key isn't sortable, it doesn't make sense to store it in a NavigableMap. The classic implementation of the NavigableMap is the TreeMap though I like the ConcurrentSkipListMap because of some particular properties (it's a tad bit faster in some cases and I can reason about it more easily).

Otherwise, you're likely looking at the speed for random access of the HashMap. The HashMap doesn't store things in a given order - it just sticks them whoever the hash function says to put them. This lets it access certain things much faster for determining if a key is in the map or not and storing it. But it also means that if you want to iterate over the keys in the map, they come out in a 'random' order.

There's a variation of the HashMap which is the subclass LinkedHashMap. Not only does it have the fast lookup of the HashMap, but it also stores a linked list along side the HashMap. When you iterate over the keys, you are working on this linked list (but its not sorted - its stored in insertion order). There are some tricks you can play with the LinkedHashMap that allow you to remove the oldest element from the list. This lets you use it for a LRU cache.

In general though, you want either a HashMap or a TreeMap depending on how you want to get the data out of the Map.

A good read is the Collections Framework Overview from Oracle. I'd also give The Power of Associative Arrays from Dr. Dobb's a read - the concept of a Map is called may things in different languages (hash, dictionary, finite maps, lookup tables, and so on). Understanding the concepts behind the Map can make things easier to decide which one to use and how to use it.