java.util.Map, best implementation considering just get(Object key)

Question

I would like to know which class to implement java.util.Map contains the get(Object key) faster.

The intention is to make a mini data cache, the volume of information will be approximately 2 to 10 thousand records.

Map<Integer, Funcionario> mapUsuarios = new ???<>();

Answer 1

Most likely HashMap, whose implementation is the simplest of the alternatives available: a simple scattering table non-synchronized, non-compete, unordered (in the sense that there is no guarantee in the order in which its iterator returns elements) and non-navigable (in the sense of NavigableMap).

The documentation suggests an optimization when instantiating the HashMap:

This implementation provides Constant-time performance for the basic Operations (get and put), assuming the hash Function disperses the Elements properly Among the Buckets. Iteration over Collection views requires time proportional to the "Capacity" of the Hashmap instance (the number of Buckets) plus its size (the number of key-value mappings). Thus, it’s very Important not to set the initial Capacity Too high (or the load factor Too low) if iteration performance is Important.

An instance of Hashmap has two Parameters that affect its performance: initial Capacity and load factor. The Capacity is the number of Buckets in the hash table, and the initial Capacity is Simply the Capacity at the time the hash table is created. The load factor is a Asure of how full the hash table is allowed to get before its Capacity is Automatically increased. When the number of Entries in the hash table Exceeds the product of the load factor and the Current Capacity, the hash table is rehashed (that is, Internal data Structures are rebuilt) so that the hash table has approximately Twice the number of Buckets.

As a general Rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but Increase the lookup cost (reflected in Most of the Operations of the Hashmap class, including get and put). The expected number of Entries in the map and its load factor should be Taken into Account when Setting its initial Capacity, so as to minimize the number of rehash Operations. If the initial Capacity is Greater than the Maximum number of Entries divided by the load factor, no rehash Operations will Ever occur.

The idea is that, if memory is available, costly processes of rehash adopting an initial capacity greater than the quotient between the expected number of entries and the load factor. In your case it is 2 to 10 thousand elements, therefore it would be good to instantiate the HashMap with an initial capacity of the order 2667 to 13334, since the load factor standard and recommended is 0.75.

Note that if you are on Android, worth knowing the class android.util.SparseArray, which is a more efficient implementation than a HashMap for use with keys of the whole type.

Answer 2

It depends on how you will popular and who will access the data the data.

If the data is preloaded before use or at least there is only one thread accessing the map, then the HashMap solves the problem and we can consider the answer of Piovezan as "canonical".

However, if the idea is popular on-demand caching, that is, it adds values only when the first access occurs, and the access is concurrent, as in a web application where more than one request can try to read and write the cache at the same time, then the scenario is completely different.

In the second scenario, it is expected that the HashMap causes problems, but may be replaced by concurrent implementations such as ConcurrentHashMap.

If the cache can be preloaded and its contents are relatively immutable over time, consider also using an immutable map. To do this, just use the static method Collections.unmodifiableMap to create a wrapper on its original map and thus avoid concurrent access problems.

Answer 3

To solve my problem I performed a test with some implementations of Map, after populated in identical way with 1400 executed objects.

speedTeste(hashMap, "hashMap");
speedTeste(treeMap, "treeMap");
speedTeste(concurrentHashMap, "concurrentHashMap");

public static void speedTeste(Map map, String type) {

System.out.println("teste velocidade mapa: " + type);
    int count = 0;
    long start = System.currentTimeMillis();
    while (count++ < 10000000) {
        map.get(1);
    }
    System.out.println("\t " + (System.currentTimeMillis() - start));

}

---

Results:

• Test Speed Map: Hashmap 144

• Test Speed Map: Treemap 559

• Speed Test Map: Concurrenthashmap 207

---

That is, even though Treemap has organized the keys in this context it is much slower than Hashmap to get the value.