Performance comparison of several Java Map

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Java multiple comparison of Map performance(TreeMap, HashMap, ConcurrentSkipListMap)

Category: Theroy, The study notes of Tags: map, SkipList 7 Comments

The problem:

Efficiency of 3 kinds of Map Java native.
1. TreeMap
2. HashMap
3. ConcurrentSkipListMap


Simulation of 150W within the mass data insertion and lookup, through the performance test two increase and search, the results are as follows:

Map type Insert Search (100W data)
10W 50W 100W 150W 0-1W 0-25W 0-50W
62 ms 227 ms 433 ms 689ms 7 ms 80 ms 119 ms
HashMap 18 ms 93 ms 217 ms 303ms 2 ms 13 ms 45 ms
TreeMap 33 ms 228 ms 429 ms 584 ms 4ms 34 ms 61 ms

Analysis shows that the

Figure 1- 1 constant and logn function efficiency comparison diagram (transverse -n data, longitudinal -f (n) time)

TreeMapBased on a red black tree (a self balancing binary search tree two) implementation, the time complexity to achieve an average of O(log n).
HashMapIs realized based on the hash table, time complexity to achieve an average of O(1).
ConcurrentSkipListMapIs the jump table based implementation, the time complexity to achieve an average of O(log n).

As shown in Fig.:
When the amount of data increases, HashMap will cause the hash conflict, conflict resolution need to spend some time cost, the f (n) =1 upward floating.
With the increase of data quantity, HashMap of the time is spent small and stable, in a single threaded environment than TreeMap and ConcurrentSkipListMap in the insertion and lookup have great advantages.

(1) TreeMap compared with HashMap

Ø HashMap stored key / value pairs in out time is random, it is based on the key values of HashCode storage data, according to the key directly obtains its value, has fast access speed. Insert, delete and positioning elements in Map, HashMap is the best choice.

Ø TreeMap was taken after the sort key. Insert, delete the need to maintain balance will sacrifice some efficiency. But if according to the natural order or custom order traversal key, then TreeMap will be better.

This test is increased and the search function, HashMap is higher than the efficiency of TreeMap.

(2) TreeMap compared with ConcurrentSkipListMap

Ø Skip list (jump table) is a kind of can replace the balanced tree data structure, the default is in accordance with the Key values in ascending order. Skip list let the sorted data distribution in the layers list, the 0-1 random number to decide a data to rise or not, an algorithm for time "by" space, the forward pointer increase in each node can be ignored, some may not relate to the node in the insert, delete, lookup, thereby improving efficiency.
The data structure maintains the balance of the probabilistic simpler than display holding structure equilibrium data of multi. For most applications, using Skip list are relatively easier to make than tree algorithm. Because Skip list is relatively simple, it will be easier, although have the same time and balance tree complexity (O (logn)), but the constant skip list relatively small number. Skip list also more savings in space. A node average of only 1.333 pointers (or even less).

Figure 1-2 Skip list structure (7,14,21,32,37,71,85 sequences for example)

Skip listNature

(1) Composed of many layers of structure, the level is a randomly generated probability.
(2) Each layer is an ordered list, the default is ascending, can also according to create mapping provided by Comparator are sorted, depending on the method used.
(3) The bottom (Level 1) containing all of the elements of the list.
(4) If an element appears in the Level I list, it in the Level I list will appear.
(5) Each node contains two pointer, a pointer to the next element in the same list, a pointer to the lower elements.

Ø ConcurrentSkipListMapNature is Skip list, and is suitable for large-scale concurrent access to data. Multiple threads can be safely removed, concurrent execution of insertion, update and access operations. There are advantages compared with other locking data structures under great pressure.

Ø TreeMapInsert the balanced tree data by strict rotation (balance two tree like dextrorotation) to ensure balanced, so the Skip list is relatively easy to implement, and compared with the balanced tree has higher operation efficiency.
The tests to increase the function, ConcurrentSkipListMap and TreeMap efficiency difference.

The search function in the 50W data, TreeMap more efficient, because ConcurrentSkipListMap own the lock mechanism, takes some efficiency, but for the multi thread concurrent environment, the ConcurrentSkipListMap efficiency is better than Treep.

Get method of the test to find using the Map method, circulation, discrete access. For the ConcurrentSkipListMap, to obtain the order segment, available subMap () method, sub sequence extraction 50W needs only 1ms, has a huge advantage. Range query efficiency of SkipListMap than HashMap and TreeMap efficiency will be higher.

(3) The SkipList reference data


7 Responses to Map Java performance comparison(TreeMap, HashMap, ConcurrentSkipListMap)

  1. Hongtiumsays:
    2012/08/30 at 19:53 login to reply

    The jump table the internal structure of Skip List is simple, so easy to implement; at the same time, because of the lack of balance tree insertion deletion of re-balance problem, the concurrency control with very fine granularity, simple also many, very suitable for high concurrency scene. So, in the NoSQL open source tools, Google LevelDB, and Redis, are used as "jump table data structure based external sorting".

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Blanche at September 08, 2014 - 9:57 AM