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

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 + ",");
)
)

Results:

1,2,3,4,5,6,7,8,9,10,

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

List
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).

Set
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.

Map
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.

Summary

① 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 http://zhangjunhd.blog.51cto.com/113473/69677
  • del.icio.us
  • StumbleUpon
  • Digg
  • TwitThis
  • Mixx
  • Technorati
  • Facebook
  • NewsVine
  • Reddit
  • Google
  • LinkedIn
  • YahooMyWeb

Related Posts of Java: Performance Analysis of collections [change]

  • log4j easy application in java

    JAVA development, frequently used the log output, in a so-called most of the software company will have its own set of configuration style, re-read the configuration file to initialize property of the log, it will be good, but sometimes may not need to fu

  • EJB

    public transient int counter; / / transient property private String firstname; / / persistent property @ Transient String getLengthInMeter () (...) / / transient property String getName () (...) / / persistent property @ Basic int getLength () (...) / / p

  • JDBC example of a long time do not have JDBC forgot

    A back-up here to stay. The first: The second:

  • In the servlet use Bean

    According to Sun's definition, JavaBean is a reusable software components. In fact JavaBean is a Java class, through the package into a property and methods of treatment of a function or a business object, referred to as bean. Because JavaBean is ...

  • Learn Java flow

    Related Articles: J2EE without EJB Introducing to Spring Framework (English revised edition) J2EE without EJB caused consider Recommend circles: reading space More related recommend Java Learning Path (1), tools, articles First, JDK (Java Development Kit)

  • hibernate generic generic DAO

    package org.lzpeng.dao; import java.io.Serializable; import java.util.List; import org.hibernate.Criteria; import org.hibernate.Query; import org.hibernate.criterion.Criterion; import org.springside.modules.orm.hibernate.Page; /** * * @version 2009-1-10 *

  • Servlet brief introduction

    Servlet brief introduction: Servlet is a small application server Are used to complete the B / S architecture, the client requests the response to treatment Platform independence, performance, able to run thread Servlet API for Servlet provides the s ...

  • First Hibernate Example

    Curd a simple example. Source does not contain the dependent libraries, or playing too much of the package. PO object Note: One must have the default constructor 2 non-final modified. Otherwise useless lazy loading. UserDAOImpl category code, and other co

  • Struts2 + hibernate + spring problem user log in

    dao layer services layer action jsp <tr> <td align="center"> <b> user name: </ b> </ td> <td> <s: textfield name = "czyNumber" cssClass = "textstyle" theme = "simple" size = &q

blog comments powered by Disqus
Recent
Recent Entries
Tag Cloud
Random Entries