ArrayMap versus HashMap [closed]

HashMap uses an array underneath so it can never be faster than using an array correctly.

Random.nextInt() is many times slower than what you are testing, even using array to test an array is going to bias your results.The reason your array is so slow is due to the equals comparisons, not the array access itself.

An ArrayList implements the List interface and a HashMap implements the Map interface. So the real question is when do you want to use a List and when do you want to use a Map. This is where the Java API documentation helps a lot.

List:

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

Map:

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

The list interface (ArrayList) is an ordered collection of objects that you access using an index, much like an array (well in the case of ArrayList, as the name suggests, it is just an array in the background. You would use an ArrayList when you want to keep things in sorted order (the order they are added, or indeed the position within the list that you specify when you add the object).

The HashMap implementation uses the hash value of the key object to locate where it is stored, so there is no guarantee of the order of the values anymore. There are however other classes in the Java API that can provide this, e.g. LinkedHashMap, which as well as using a hash table to store the key/value pairs, also maintains a List (LinkedList) of the keys in the order they were added, so you can always access the items again in the order they were added (if needed).

When to use Arrays?

Never underestimate arrays. Most of the time, when we have to use a list of objects, we tend to think about using vectors or lists. However, if the size of collection is already known and is not going to change, an array can be considered as the potential data structure. It's faster to access elements of an array than a vector or a list. That's obvious, because all you need is an index. There's no overhead of an additional get method call.

Sometimes, it may be best to use a combination of the above approaches. For example, you could use a ArrayList of HashMap to suit a particular need.