Shulou(Shulou.com)06/02 Report--

This article mainly explains the comparison of arrays and collections in java. The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn the comparison of arrays and collections in java.

I. comparison of arrays and collections

The array is not object-oriented and has obvious defects. The set makes up for the shortcomings of the array and is more flexible and practical than the array, and different collection framework classes can be applied to different situations.

As follows:

1: arrays can hold basic data types and objects, while collection classes store references to objects, not objects themselves!

2: the array is easy to be fixed and cannot be changed dynamically, and the capacity of the collection class is changed dynamically.

3: the array cannot determine how many elements are actually stored in it. Length only tells the capacity of the array, and the size () of the set can know exactly the number of elements.

4: collections can be implemented in many ways and applied in different situations, unlike arrays that only use sequential tables.

5: collections exist in the form of classes, with the characteristics of encapsulation, inheritance, polymorphism and so on. Various complex operations can be realized through simple methods and attributes, which greatly improves the efficiency of software development.

Collection and Map are the root interfaces of the collection framework. Subinterfaces of Collection:

Set: interface-implementation class: HashSet, LinkedHashSet

Set subinterface SortedSet interface-implementation class: TreeSet

List: interface-implementation class: LinkedList,Vector,ArrayList

List collection

An ordered list that allows duplicate elements to be stored

Implementation class:

ArrayList: array implementation, fast query, slow growth and deletion, lightweight; (thread unsafe)

LinkedList: bidirectional linked list implementation, fast addition and deletion, slow query (thread unsafe)

Vector: array implementation, heavyweight (thread safety, low usage)

ArrayList

The bottom layer is the Object array, so ArrayList has the advantages of fast query speed of array and slow speed of adding and deleting.

At the bottom of LinkedList is a two-way cyclic linked list. Each data node on this linked list consists of three parts: the front pointer (the location of the previous node), the data, and the back pointer (the location of the subsequent node). The back pointer of the last node points to the front pointer of the first node, forming a loop.

The query efficiency of two-way circular linked list is low, but the efficiency of adding and deleting is high.

There is no difference between ArrayList and LinkedList in usage, but there are differences in function.

LinkedList

LinkedList is implemented using a two-way cyclic linked list.

LinkedList is used to realize stack (stack), queue (queue) and two-way queue (double-ended queue).

It has methods addFirst (), addLast (), getFirst (), getLast (), removeFirst (), removeLast (), and so on.

It is often used in situations where there are more add and delete operations and few query operations:

Queues and stacks.

Queue: first-in, first-out data structure.

Stack: last-in, first-out data structure.

Note: when using a stack, you must not provide a way to give an element that is not the last element a chance to get off the stack.

Vector

Similar to ArrayList, except that Vector is a heavyweight component, and its use consumes more resources. )

Conclusion: use Vector (to ensure thread safety) in the case of concurrency.

Use ArrayList without considering concurrency (thread safety is not guaranteed).

Automatic extension mechanism of ArrayList

Implementation mechanism: ArrayList.ensureCapacity (int minCapacity)

First get the length oldCapacity of the current elementData attribute.

Then determine whether to expand the capacity by judging which of the oldCapacity and minCapacity parameters are larger, if the minCapacity is greater than

OldCapacity, then we will expand the current List object.

The strategy for capacity expansion is to choose the larger one between (oldCapacity * 3) / 2 + 1 and minCapacity. Then use array copy

Bay's method to transfer previously stored data to a new array object

If the minCapacity is not greater than oldCapacity, then the capacity will not be expanded.

Implement the queue with LinkedList:

A Queue is a linear table that restricts all inserts to one end of the table and all deletions to the other end of the table.

The end of the table that allows insertion is called the end of the line (Rear), and the end that allows deletion is called the head of the line (Front).

Queues operate on a first-in, first-out (FIFO) basis.

The physical storage of queues can be either sequential or chained.

Implement the stack with LinkedList:

Stack is also a special linear table, which is a last-in, first-out (LIFO) structure.

A stack is a linear table that is limited to insert and delete operations only at the end of the table, which is called the top of the stack (top) and the header is called the bottom of the stack (bottom).

The physical storage of the stack can use either sequential storage structure or chained storage structure.

Common methods of List:

Void add (int index, Object element): add object element to location index

Boolean addAll (int index, Collection collection): add all the elements in the container collection after the index location

Object get (int index): take out the element in the location subscript index

Int indexOf (Object element): find the location where the object element first appears in List

Int lastIndexOf (Object element): find the last location of the object element in the List

Object remove (int index): delete elements in index location

ListIterator listIterator (int startIndex): returns a ListIterator drop generator, starting with startIndex

List subList (int fromIndex, int toIndex): returns a sublist List, where the element is stored as an element before fromIndex to toIndex

Set collection

Extended Collection interface

Unordered collection, duplicate elements are not allowed to be stored; null elements are allowed

Added restrictions to the add (), equals (), and hashCode () methods

HashSet and TreeSet are implementations of Set

Set- "hashSet linkedHashSet

SortedSet-"TreeSet

There is a HashMap; in the background of HashSet to initialize the background capacity; only if a HashSet is generated, the system only provides access to key; if there are two Key duplicates, it will overwrite the previous

Implementation class:

HashSet:equals returns true,hashCode returns the same integer; hash table; the stored data is unordered.

LinkedHashSet: this implementation differs from HashSet in that it maintains a doubly linked list that runs on all entries. The stored data is orderly.

The HashSet class HashSet class directly implements the Set interface, and its underlying layer is actually packaged with a HashMap to implement. HashSet uses HashCode algorithm to access the elements in the collection, so it has better reading and lookup performance.

The characteristics of HashSet not only cannot guarantee the order in which elements are inserted, but may also change in later order (this is determined by HashSet storing objects (elements) by HashCode, and object changes may lead to HashCode changes)

HashSet is thread-unsafe

The HashSet element value can be NULL

Common methods of HashSet:

Public boolean contains (Object o): returns true if set contains the specified element

Public Iterator iterator () returns the iterator of the element in set

Public Object [] toArray (): returns an array containing all elements in set public Object [] toArray (Object [] a): returns an array containing all elements in set. The runtime type of the returned array is the runtime type of the specified array.

Public boolean add (Object o): if the specified element does not exist in set, add it to set

Public boolean remove (Object o): if the specified element exists in set, it is deleted from set

Public boolean removeAll (Collection c): if the set contains the specified collection, all elements of the specified collection are deleted from the set

Public boolean containsAll (Collection c): returns true if set contains all the elements of the specified collection. If the specified collection is also a set, the method returns true only if it is a subset of the current set

The HashSet that implements the Set interface is realized by HashMap.

We should define hashCode () and equals () for each object to be stored in the hash table.

Equals and HashCode of HashSet

As mentioned earlier, the Set collection does not allow repeating elements, otherwise it will cause all sorts of strange problems. So how does HashSet determine element duplication?

HashSet needs to determine whether two elements are equal through both equals and HashCode. The specific rule is that if two elements are true through equals, and the hashCode of the two elements is equal, the two elements are equal (that is, repeat).

Comparison of several Set:

Members are traversed out of order outside the HashSet.

Members can be objects of any Object subclass, but if you override the equals method, be careful to modify the hashCode method at the same time.

TreeSet traverses members externally in an orderly manner

Additional implementation of SortedSet, support for subset and other operations requiring sequence

Members are required to implement the Comparable interface, or use Comparator construction

TreeSet . Members are generally of the same type.

LinkedHashSet external traverses members in the order in which they are inserted

Members are similar to HashSet members

HashSet is implemented based on Hash algorithm, and its performance is usually better than TreeSet. We should usually use HashSet, and we only use TreeSet when we need sorting capabilities.

The order in which elements are stored in HashSet has nothing to do with the order in which we added them, while LinkedHashSet maintains the order in which elements are added. TreeSet is to sort and store the elements in our Set.

In general, TreeSet implementations are useful when you want to extract elements from a collection in an orderly manner. In order to proceed smoothly, the elements added to the TreeSet must be sortable. You also need to implement the Comparable interface for class objects added to TreeSet. Generally speaking, it is faster to add elements to HashSet and then convert the collection to TreeSet for ordered traversal.

Performance Analysis of various Set sets

HashSet and TreeSet are the most frequently used I collections in the Set collection. HashSet always performs better than TreeSet collections because HashSet does not need to maintain the order of elements.

LinkedHashSet requires additional linked lists to maintain the insertion order of elements, so it has lower performance than HashSet at insert time, but higher performance at iterative access (traversal). Because when inserting, you have to calculate the hashCode and maintain the linked list, and when you traverse, you only need to press the linked list to access the elements.

The EnumSet element is the best performing of all Set elements, but it can only hold elements of type Enum

Map

The second kind of interface tree of the collection framework.

It provides a mapping of a set of key values. Each object stored in it has a corresponding keyword (key), which determines where the object is stored in Map.

Keywords should be unique, and only one value can be mapped per key.

Implementation class:

HashMap, TreeMap, LinkedHashMap, Hashtable, etc.

HashMap: key-value pair, key cannot be repeated, but value can be repeated; the implementation of key is HashSet;value corresponding to put; allow the key or value of null

Hashtable: thread safe, keys or values of null are not allowed

Properties::key and value are both String types and are used to read configuration files

TreeMap: the Map; key that sorts the key is TreeSet. Value has its own constructor for each key; key to implement the Comparable interface or TreeMap.

LinkedHashMap: this implementation differs from HashMap in that it maintains a doubly linked list that runs on all entries. Number of storage

According to is orderly.

HashMap: Map is mainly used to store key (key) value (value) pairs and get the value according to the key, so the key is not allowed to repeat, but the value is allowed to repeat.

HashMap is the most commonly used Map, it stores data according to the HashCode value of the key, and its value can be obtained directly according to the key, so it has fast access speed.

HashMap can only allow the key of one record to be Null; and the value of multiple records to be Null.

HashMap does not support thread synchronization, that is, multiple threads can write HashMap; at any one time, which may lead to data inconsistency. If you need synchronization, you can use Collections's synchronizedMap method to make HashMap have the ability to synchronize.

HashMap implementation principle-hash

The significance of Hash hash algorithm is that it provides a fast way to access data. It uses an algorithm to establish the corresponding relationship between key values and real values. Hash tables are also known as hash tables. The basic idea of the hash table algorithm is: take the keyword of the node as the independent variable, calculate the corresponding function value through a certain function relation (hash function), and use this value as the address of the node in the hash table.

When the elements in the hash table are too full, the hash must be rehashed, a new hash table will be generated, all elements will be stored in the new hash table, and the original hash table will be deleted. In the Java language, the load factor (load factor) is used to determine when to rehash the hash table. For example, if the load factor is 0.75, when 75% of the positions in the hash table are already full, then the hash will be rehashed.

The higher the load factor (closer to 1.0), the more efficient the use of memory and the longer it takes to find elements. The lower the load factor (closer to 0.0), the shorter the search time for the element, and the more memory is wasted.

When do I need to rewrite equals?

When a class has its own concept of "logical equality" (different from the concept of object identity)

The Object class only provides a comparison of references, and returns false if the two references are not the same, which cannot meet the needs of most object comparisons, so override

Use the = = operator to check whether the argument is a reference to the object. "

Use the instanceof operator to check that the argument is of the correct type

Convert arguments to the correct type

For each "critical" field in the class, check whether the field in the argument matches the corresponding field value in the current object. For fields that are neither float nor double types, you can use the = = operator to compare; for fields of object reference types, you can recursively call the equals method of the referenced object, for fields of float and double types, first convert to values of type int or long, and then use the = = operator to compare

When you have written the equals method, you should ask yourself three questions: is it symmetrical, transitive, and consistent? If the answer is no, find out why these features are not satisfied, and then modify the code of the equals method

Equals () and hashCode () are overwritten at the same time

It is particularly emphasized that these two methods should be overridden when an object is used as a key (or index).

After overriding equals, two different instances may be logically equal, but different hash codes are generated according to the Object.hashCode method, in violation of "equal objects must have equal hash codes".

As a result, when you use one of them as a key to save to hashMap, hasoTable, or hashSet, and then use "equal" to find another key to find them, you can't find them at all.

Values for different types of hashCode

If the field is Boolean, calculate (f? 0:1)

If it is char,short,byte or int, calculate (int) f

If it is a long type, calculate (int) (f ^ (f > 32))

If it is a float type, calculate Float.floatToIntBits (f)

If it is a double type, calculate Dobule.doubleToLongBits (f)

If the field is an object reference, recursively call hashCode

If the field is an array, treat each element as a separate field and calculate a hash code for each important element

Map collection comparison:

The input order of the HashMap is independent of the output order.

LinkedHashMap retains the storage order of key-value pairs.

TreeMap sorts the elements in the Map.

Because HashMap and LinkedHashMap store data faster and more efficiently than using TreeMap directly.

When we have finished storing all the elements, we sort the elements in the entire Map. This can improve the efficiency of the whole program and shorten the execution time.

Note: TreeMap is sorted by Key. If we want to use TreeMap for normal sorting, the objects stored in Key must implement the Comparable interface.

Common methods of Map:

Object put (Object key,Object value): used to store a key-value pair in Map

Object remove (Object key): according to key (key), remove the key-value pair and return the value

Void putAll (Map mapping): saves an element from another Map into the current Map

Void clear (): clears the elements in the current Map

Object get (Object key): get the corresponding value according to key (key)

Boolean containsKey (Object key): determines whether a key exists in Map (key)

Boolean containsValue (Object value): determine whether a certain value exists in Map (value)

Public Set keySet (): returns all keys (key) and stores them using the Set container

Public Collection values (): returns all values (Value) and stores them using Collection

Public Set entrySet (): returns an element Set that implements the Map.Entry interface

Set traversal

1. Enhance the for loop for (Obj ovalc) {syso (o)}

2. Use iterator, Iterator it=c.iterator

While (it.hasNext ()) {Object o = it.next ()}

3. Ordinary cycle: for (Iterator it=c.iterator (); it.hasNext ();) {it.next ()}

Thank you for reading, the above is the content of "comparison of arrays and collections in java". After the study of this article, I believe you have a deeper understanding of the comparison of arrays and collections in java, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.