Java: Performance Analysis of collections [change]

This article is transferred, and no verification of the correctness of the article, I have time will be carefully checked, everyone If you have time, you can also help to test, and then the process will be issued with the results look.
1.Java collections framework map
Java: Performance Analysis of collections [change]

- A collection of interface: 6 interface (short dashed line), indicating that a different collection types, is a collection framework.

- Abstract class: abstract class 5 (long dashed line), the set of interface partially achieved. Can be extended to a custom collection class.

- Implementation class: 8 implementation class (solid line), the concrete implementation of the interface.

2.Java Container Class Introduction

① Java container classes can automatically adjust their size.

② Collection interface is allowed to repeat a group of objects.

③ Set interface inheritance Collection, are not allowed to repeat, using their own internal mechanism for an arrangement.

④ List interface inheritance Collection, allowing repetition, to elements of order placement to place elements will not be re-arranged.

⑤ Map interface is a key component of the - the value target, that is held by either key-value pairs. Map can not have duplicate key. The internal layout has its own mechanism.

Java 2 collections framework simplified diagram
Java: Performance Analysis of collections [change]

3.Collection Interface

Basic Operation

- Increase the elements add (Object obj); addAll (Collection c);

- Delete Element remove (Object obj); removeAll (Collection c);

- Seeking the intersection retainAll (Collection c);

Collection is the most basic set of interfaces, all classes achieve the Collection interface must provide two standard constructors: no argument constructor used to create an empty Collection, a Collection argument constructor used to create a new Collection, the new Collection with the introduction of the Collection have the same type of elements.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
public class AddingGroups (
public static void main (String [] args) (
Collection <Integer> collection = new ArrayList <Integer> (Arrays.asList (
1, 2, 3, 4, 5));
Integer [] moreInts = (6,7,8,9,10);
collection.addAll (Arrays.asList (moreInts));
for (Integer i: collection)
System.out.print (i + ",");



Here shows the Collection interfaces 2 usage, first of all, Collection constructor accepts another Collection (List) as a parameter to initialize. Then, call the addAll () method to add elements, note that this method only accepts another Collection as a parameter.

In addition, we must pay attention, Collection interface does not provide random access to elements of get () method. Because the Collection, including Set, the Set itself to maintain internal order. If you want to check the Collection of the elements, it must use the iterator.

4.List Interface

4.1 List Interface

List is ordered Collection, use this interface to control the precise location of each element inserted. Users can use the index (the location of elements in the List, similar to the array subscript) to access the List of elements, similar to Java array.

And the following should be mentioned in the Set different, List to allow the same elements.

In addition to necessary Collection interface iterator () methods but, List also provides a listIterator () method returns a ListIterator interface, and standard Iterator interface in comparison, ListIterator over a number of add () method of the class, allows you to add, Remove, set elements, can traverse forward or backward.

4.2 LinkedList Class

LinkedList implements List interface that allows null elements. In addition, LinkedList provide additional get, remove, insert method in LinkedList of the first or tail. These operations could be used to make LinkedList stack (stack), Queue (queue), or double-ended queue (deque). This implementation is not synchronized.

4.3 ArrayList Class

ArrayList implements an array of variable size. It allows all the elements, including null.

size, isEmpty, get, set method of running time is a constant. But the add method for the apportionment of overhead constant, adding n elements need O (n) time. Other methods running time is linear.

Each ArrayList instance has a capacity (Capacity), which is used to store the size of the array elements. This capacity may continue to add new elements as automatically increased, but the growing algorithm, and is not defined. When you need to insert a large number of elements, can be inserted before the call ensureCapacity method to increase the capacity of ArrayList to improve the efficiency of insertion. This implementation is not synchronized.

5.Set Interface

5.1 Set Interface

Set and Collection with exactly the same interface, without any additional functionality. It is an do not contain duplicate elements Collection, that any two elements e1 and e2 are e1.equals (e2) = false, Set up to a null element.

It is clear, Set constructors are a constraint, the incoming Collection parameter can not contain duplicate elements.

Please Note: You must be careful in handling the variable object (Mutable Object). If a Set the variable element of change in their own state led to Object.equals (Object) = true will cause some problems.

5.2 HashSet

Such realization Set interface, from the hash table (actually a HashMap instance) support. It does not guarantee the order set iteration; in particular, it does not guarantee that the order of permanent change. Such allows the use of null elements. Basic operations such as providing a stable performance, this implementation is not synchronized.

5.3 LinkedHashSet

Has a predictable iteration order of the Set interface hash table and linked list implementation. The Implementation and HashSet difference is that it maintains a run on a double link list of all entries. This list of links defines the iteration sequence, that is inserted into the set in accordance with the elements in the order (insertion order) iteration. Note that insertion order is not re-inserted in the set elements of the impact. This implementation is not synchronized.

5.4 TreeSet

On TreeMap implementation of NavigableSet. The use of the natural order of elements to sort the elements, or create a set according to a Comparator provided to sort, depending on the use of the constructor. This realization of the basic operations (add, remove and contains) provided by the guaranteed log (n) time overhead. This implementation is not synchronized.

6.Map Interface

Please note, Map does not inherit Collection interface, Map provides key to value mapping. 1 Map can not contain the same key, each key can map a value. Map interface provides three kinds of collections view, Map of the content can be regarded as a group of key collection, a group of value sets, or a group of key-value mapping.

6.1 WeakHashMap

Weak bond in order to achieve the hash table based Map. The WeakHashMap, when a key is no longer normal use, it will automatically remove its entry. More precisely, for a given key, the map does not prevent the existence of garbage discarded in the keys, which makes the key as to terminate, have been terminated, and then be recycled. Drop a key, its entry from the map to effectively remove the fact that such behavior and other Map implementation is different. This implementation is not synchronized.

6.2 TreeMap

The map in accordance with its keys to sort the natural order, or create a map according to a Comparator provided to sort, depending on the use of the constructor. This implementation is not synchronized.

6.3 HashMap

Map-based hash table implementation of the interface. This implementation provides all optional map operations, and allows the use of null values and null keys. (Except the non-synchronization, and allows the use of null addition, HashMap class and Hashtable are common.) Mapping the sequence of such does not guarantee, in particular, it does not guarantee that the order of permanent change. This implementation is not synchronized.

6.4 SortedMap

Further information on the key to the overall ranking Map. The map is based on the natural order of its keys sorted, or sorted according to generally create a map to provide sort of Comparator. Collection of ordered map view (by the entrySet, keySet method returns, and values) for iteration, this order will be reflected. To use this sort, but also the need to provide a number of other operations (This interface is a SortedSet the corresponding mapping).

7. Collections performance efficiency summary

Note that this shows the class are non-thread-safe. If you need to consider thread-safe, you should use ConcurrentMap, CopyOnWriteArrayList, CopyOnWriteArraySet so.

Interface class can be repeated in order to keep insertion sort instructions

ArrayList YYN longer than the random-access element; but insert, delete elements of slow (an array of characteristics).
LinkedList YYN insert, delete elements faster, but then access is slow (list characteristics).

HashSet NNN use of hash, the fastest access to element method.
TreeSet NNY the elements stored in the red - black tree data structure. The default is ascending.
LinkedHashSet YNN use of hash while using the linked list to maintain the insertion sequence elements.

HashMap NNN use the hash to provide the fastest search technology.
TreeMap NNY default in accordance with the comparison results of the ascending Save button.
LinkedHashMap YNN accordance with the key inserted in order to save while using the hash to find the speed increase.


① if related to the stack, queue and other operations, should be considered with the List. If you want a lot of random access, you should use ArrayList; If you frequently insert and delete operations, with the use of LinkedList.

② HashMap is designed to fast access; and TreeMap maintain "key" is always in a sort state, so there is no HashMap fast. LinkedHashMap to maintain order of inserted elements, but also through a hash provides fast access capability.

③ Set does not accept duplicate elements. HashSet provide the fastest query speed, while maintaining elements in a TreeSet to sort state. LinkedHashSet to insert elements in order to save.

④ the operation of the hash table, as a key target to correctly override equals and hashCode methods.

⑤ try to return to port rather than the actual type (the abstract programming), such as return to List instead of ArrayList, so if you later need to be replaced by ArrayList when LinkedList, client-side code without changing the.

⑥ program should not use outdated VectorHashtableStack.

This article comes from "sub-larvae" blog, please be sure to keep this source

分类:Java 时间:2008-05-17 人气:322
blog comments powered by Disqus


  • On Java object serialization of 5 things you do not know 2010-05-12

    On Java object serialization of 5 things you do not know Serialized data is secure? Not necessarily right. Ted Neward , CEO, ThoughtWorks, ThoughtWorks Ted Neward is a global consulting firm ThoughtWorks consultant, is president of Neward & Associate

  • java object array of Java Array sort sort sort 2010-06-13

    Java collection object sorting test Java API for sorting the collection offers two types of support: java.util.Collections.sort (java.util.List) java.util.Collections.sort (java.util.List, java.util.Comparator) The first method requires the sort of e

  • Java ArrayList in the remove (Object obj) method of 2010-09-27

    Today, having a bug, discovered that the original programmer to write the equals method is a little problem, it is a lot of problems. By the way looked ArrayList of remove (Object obj) method, it may look, is remove the following methods: public bool

  • Java object serialization and deserialization Practice 2010-11-13

    When the two processes during the remote communication, they can send all types of data. No matter what type of data, will be in the form of binary sequences transmitted over the network. The sender need to convert the Java object is a sequence of by

  • Java Object Oriented Programming concepts 2014-08-18

    Introduction This tutorial will help you to understand about Java OOP'S concepts with examples. Let's discuss about what are the features of Object Oriented Programming. Writing object-oriented programs involves creating classes, creating objects fro

  • Ajax: Java Object Serialization 2009-11-12

    In this paper, we discuss the basics of Ajax development, but will focus on a number of Java Web developers are most concerned about the issue: In order to generate data on the client. Most Java developers have the Model - View - Controller (MVC) mod

  • Java object serialization and deserialization knowledge point summary 2010-07-26

    One or two concepts, what is serialization? What is deserialized? Serialization: the object into a stream of process is called serialization. Deserialization: the process will flow into the object is called deserialization. Second, general-purpose se

  • java object instance initialization sequence 2011-04-22

    How java object is initialized, the new file as a (including class PrintClass and A and its subclass B), compile and run one of the main methods public class PrintClass { public static void main (String [] args) { new B (); } PrintCla

  • Performance Optimization of Java 2009-05-25

    Java in the mid nineties after the impressive win at the same time, but also attracted some criticism. Won the admiration of the major Java are cross-platform interoperability, the so-called "Write Once, Run Anywhere". However, because of Java's

  • Hibernate.initialize (Object obj) 2009-09-24

    On lazy (lazy) and forced to load (Hibernate.initialize (Object proxy)), etc. Sustained in the use of hibernate when it is sometimes necessary to change the dynamic loading of objects, such as in the editorial pages inside lazy = true, the page in th

iOS 开发

Android 开发

Python 开发



PHP 开发

Ruby 开发






Javascript 开发

.NET 开发



Copyright (C), All Rights Reserved. 版权所有 闽ICP备15018612号

processed in 0.037 (s). 13 q(s)