Overview of common basic data structures in Java

Java data structure is a subject that studies the computer operation objects, their relationships and operations in non numerical programming problems. The most commonly used types in Java data structures are as follows:

Map interface

Please note that map does not inherit the collection interface, and map provides the mapping from key to value. A map cannot contain the same key, and each key can only map one value.

The map interface provides views of three sets. The contents of the map can be regarded as a set of key sets, a set of value sets, or a set of key value mappings.

List interface

List is an ordered collection. Users can access the elements in the list using an index (the position of elements in the list, similar to array subscripts), which is similar to Java arrays.

Unlike the set mentioned below, list allows the same elements.

Collection interface

Two standard constructors: the parameterless constructor is used to create an empty collection; A constructor with a collection parameter is used to create a new collection

How to traverse:

The two interfaces derived from the collection interface are list and set.

ArrayList class

ArrayList implements variable size arrays. It allows all elements, including null. ArrayList is not synchronized.

Hashtable class

Hashtable inherits the map interface and implements a hash table of key value mapping. Any non null object can be used as a key or value.

Put (key, value) is used for adding data and get (key) is used for fetching data. The time cost of these two basic operations is constant. Hashtable adjusts the performance through two parameters, initialCapacity and loadactor. The default is usually loadfactor0 75 better balance of time and space. Increasing the load actor can save space, but the corresponding lookup time will increase, which will affect operations such as get and put.

A simple example of using a hashtable is as follows. Put 1, 2 and 3 into the hashtable, and their keys are "one", "two" and "three":

To take out a number, such as 2, use the corresponding key:

Since an object as a key will determine the position of its corresponding value by calculating its hash function, any object as a key must implement hashcode and equals methods. Hashcode and equals methods inherit from the root class object. If you use a custom class as a key, be careful. According to the definition of hash function, if the two objects are the same, that is, obj1 Equals (obj2) = = true, their hashcodes must be the same, but if two objects are different, their hashcodes are not necessarily different. If the hashcodes of two different objects are the same, this phenomenon is called conflict. The conflict will increase the time cost of operating the hash table. Therefore, try to define a well-defined hashcode () method to speed up the operation of the hash table.

If the same object has different hashcodes, the operation on the hash table will produce unexpected results (the expected get method returns null). To avoid this problem, just remember one thing: duplicate the equals method and hashcode method at the same time, not just one of them.

Hashtable is synchronized.

Stack class

Stack inherits from vector and implements a last in first out stack. Stack provides five additional methods to enable vector to be used as a stack. The basic push and pop methods, as well as the peek method, get the elements at the top of the stack. The empty method tests whether the stack is empty, and the search method detects the position of an element in the stack. Stack is empty just after it is created.

Set interface

Set is a collection that does not contain duplicate elements, that is, any two elements E1 and E2 have E1 Equals (E2) = = false, set has at most one null element.

Obviously, the constructor of set has a constraint that the incoming collection parameter cannot contain duplicate elements.

Please note: mutable objects must be handled with care. If a variable element in a set changes its state, object Equals (object) = = true will cause some problems.

Weakhashmap class

Weakhashmap is an improved HashMap. It implements "weak reference" for keys. If a key is no longer referenced externally, the key can be recycled by GC.

Vector class

Vector is very similar to ArrayList, but vector is synchronous.

HashMap class

HashMap is similar to hashtable, except that HashMap is asynchronous and allows nulls, that is, nullvalue and nullkey. However, when a HashMap is regarded as a collection (the values () method can return a collection), the iterative sub operation time overhead is proportional to the capacity of the HashMap. Therefore, if the performance of iterative operations is very important, do not set the initialization capacity of HashMap too high or the load actor too low.

LinkedList class

Null elements are allowed.

In addition, LinkedList provides additional get, remove and insert methods at the head or tail of LinkedList. These operations enable the LinkedList to be used as a stack, queue, or deque.

Note that LinkedList has no synchronization method. If multiple threads access a list at the same time, they must implement access synchronization themselves. One solution is to construct a synchronized list when creating a list:

summary

The above is the whole content of this article. This site has more detailed and specific introduction to data structure. I hope it will help you.