Learn about the importance of java data structure and a summary of classification

One question that bothers many new java beginners is the need to learn the structure of data. A lthough you may not have specifically read some professional books on data structure, you can still use java to do a good job, but that doesn't mean you don't have access to the data structure at all, because java has done too much for you at the bottom, and you're doing more to call the API when you're dealing with the data structure. When your code accumulates to a certain extent, you want to strengthen your knowledge of data structures and algorithms.

For example, you can think of java as an automatic car, and the data structure is how the transmission works. Y ou have no idea how the gearbox works, so drive the car into the automatic gear, and it's not necessarily slower than someone you know. W riting about procedures, like driving, can make a big difference, but if you don't know how the bottom works, you'll always have to drive, neither repair nor build a car. I f you're not interested in neither, the data structure is good. But if you have a little higher pursuit in programming in your lifetime, data structure is a subject you can't get around.

In addition, it is important to know that data structure is also the cornerstone to various practical algorithms, so learning data structure is to enhance internal forces. H ere's a book, Java Data Structures and Algorithms, which teaches how to arrange and manipulate data in an easy-to-understand way, using java languages to illustrate important concepts while avoiding the complexity of the C/C language in order to focus on data structures and algorithms. E xperienced author Mr. Robert Lafore provides many straightforward examples that avoid the lengthy, locky mathematical proofs common to such examples. T here are questions and exercises after each chapter of the book, giving the reader the opportunity to test his or her understanding.

Summary of the data structure in java

Iterator it = collection.iterator(); // 获得一个迭代子  
while(it.hasNext()) {  
Object obj = it.next(); // 得到下一个元素  
} 

Key methods:

1, boolean add (Object o) to add objects to the collection

2, boolean remove (Object o) to delete the specified object

3, int size() returns the number of elements in the current collection

4, boolean contains (Object o) to find out if there are specified objects in the collection

5, boolean isEmpty() to determine whether the collection is empty

6, Iterator Iterator () returns an iterator

7, boolean contains All (Collection c) to find out if there are elements in the collection c

8, boolean add All (Collection c) adds all the elements in the collection c to the collection

9, void clear() delete all elements in the collection

10, void removeAll (Collection c) removes elements from the collection that are also in the c collection

11, void retainAll (Collection c) removes elements from the collection c that are not included in the collection

The List interface

List is an ordered Collection that uses this interface to precisely control where each element is inserted. Users can use the index (the position of elements in List, similar to the array subscript) to access elements in List, similar to an array of Javas.

List allows the same elements, as set is mentioned below.

In addition to the Iterator() method, which is required for the College interface, List also provides a listIterator() method that returns a ListIterator interface, which allows you to add, delete, set elements, and traverse forward or back compared to the standard Iterator interface.

Common classes for implementing list interfaces are LinkedList, ArrayList, Vector, and Stack.

Key methods:

1, void add (int index, Object element) to add an object at the specified location

2, boolean addAll (int index, Collection c) adds elements of collection c to the specified location

3, Object get (int index) returns the element in List that specifies the location

4, int indexOf (Object o) returns the position where the first element o appears.

5. Object removeint (int index) removes the element at the specified location

6, Object set (int index, Object element) replaces the element on the position index with the element element, returning the replaced element

LinkedList class

LinkedList implements the List interface, allowing null elements. I n addition LinkedList offers additional get, remove, insert methods in the first or tail of LinkedList. These actions enable LinkedList to be used as a stack, queue, or two-way queue.

Note that LinkedList does not have a synchronization method. I f multiple threads access a List at the same time, you must implement access synchronization yourself. One workaround is to construct a synchronized List when you create List:

List list = Collections.synchronizedList(new LinkedList(...)); 

ArrayList class

ArrayList implements an array of variable sizes. I t allows all elements, including null. ArrayList is not synchronized.

size, isEmpty, get, set method run time constant. H owever, the add method overhead is the allocated constant, and it takes O(n) time to add n elements. Other methods run linearly.

Each ArrayList instance has a capacity, which is the size of the array used to store elements. T his capacity increases automatically as new elements are added, but the growth algorithm is not defined. When you need to insert a large number of elements, you can call the ensureCapacity method to increase the capacity of ArrayList before inserting to improve insertion efficiency.

Like LinkedList, ArrayList is out of sync.

Key methods:

1, Boolean add (Object o) adds the specified element to the end of the list

2, Boolean add (int index, Object element) in the list to add the specified location

3, Boolean add All (Collection c) adds the specified collection to the end of the list

4, Boolean addAll (int index, Collection c) in the list of specified places to join the specified collection

5, Boolean clear () remove all elements from the list

6, Boolean clone() returns a copy of the list instance

7, Boolean contains (Object o) to determine whether an element is included in the list

8, Boolean ensureCapacity (int m) increases the capacity of the list, if necessary, the list can accommodate m elements

9, Object get (int index) returns the elements that are specified in the list

10, Object indexOf looks for the subsemation of the specified element in the list

11, Int size() returns the number of elements in the current list

Vector class

Vector is very similar to ArrayList, but Vector is synchronized. I terator, created by Vector, is the same interface as Iterator created by ArrayList, but because Vector is synchronized, when one Iterator is created and is in use, another thread changes Vector's state (for example, adding or removing some elements), When the Iterator method is called, the ConcurrentModificationException is thrown, so the exception must be caught.

Stack class
Stack inherits from Vector to implement a last-in, first-out stack. S tack offers five additional methods that allow Vector to be used as a stack. T he 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 has just been created as an empty stack.

Set interface
Set is a Collection that does not contain duplicate elements, i.e. any two elements, e1 and e2, have e1.equals (e2) s false, and Set has up to one null element.

Obviously, Set's constructor has a constraint that the incoming College parameter cannot contain duplicate elements.

Note: Variable objects must be handled with care. If a variable element in a Set changes its state, causing Object.equals (Object) .true will cause some problems.

Map interface
Note that Map does not inherit the College interface, and Mapkey provides a map to the value. T he same key cannot be included in a Map, and only one value can be mapped per key. The Map interface provides a view of three collections, and map content can be treated as a set of key collections, a set of value collections, or a set of key-value maps.

Key methods:

1, boolean equals (Object o) comparison object

2, boolean remove (Object o) deletes an object

3, put (Object key, Object value) to add key and value

Hashtable class

Hashtable inherits the Map interface and implements a key-value-mapped hash table. Any non-empty (non-null) object can be used as a key or a value.

Add data using put (key, value), take out data using get (key), the time cost of these two basic operations is constant.

Hashtable adjusts performance through two parameters, initial capacity and load factor. U sually the defaultload factor 0.75 achieves a better balance of time and space. Increasing the load factor saves space but the corresponding lookup time increases, which affects operations such as get and put.

A simple example of using Hashtable is to put 1,2,3 in Hashtable, and their keys are "one," "two," and "three":

Hashtable numbers = new Hashtable();  
numbers.put(“one”, new Integer(1));  
numbers.put(“two”, new Integer(2));  
numbers.put(“three”, new Integer(3)); 

Integer n = (Integer)numbers.get(“two”);  
System.out.println(“two = ” + n); 

Because an object that is key determines the location of the corresponding value by calculating its hash function, any object that is key must implement the hashCode and equals methods. T he hashCode and equals methods inherit from the root class Object, and if you use a custom class as key, be careful, as defined by the hash function, if the two objects are the same, i.e. obj1.equals (obj2) s true, then their hashCode must be the same, but if the two objects are different, their hashCode is not necessarily different, if the two different objects are the same. This behavior is called conflict, which causes the time overhead of operating the hash table to increase, so the hashCode() method, as defined as possible, can speed up the operation of the hash table.

If the same object has a different hashCode, the operation of the hash table will have unexpected results (the expected get method returns null), and to avoid this problem, just keep one thing in mind: to rewrite both the equals method and the hashCode method, not just one of them.

Hashtable is synchronized.

HashMap class
HashMap is similar to Hashtable, except that HashMap is non-synchronized and allows null, i.e. null value and null key. , however, when The Values() method is considered a Collection, its iterative sub-operational time overhead is proportional to hashMap's capacity. Therefore, if the performance of the iteration operation is important, do not set the initialization capacity of HashMap too high, or the load factor too low.

WeakHashMap class
WeakHashMap is an improved HashMap that imposes a "weak reference" to key, which can be recycled by the GC if it is no longer referenced externally.

Summarize
If stacking, queues, and other operations are involved, you should consider using List, LinkedList for elements that need to be inserted quickly, and ArrayList if you need to access elements quickly and randomly.

If the program is in a single-threaded environment, or if access is performed in only one thread, considering non-synchronized classes is more efficient, and if multiple threads may operate a class at the same time, you should use a synchronized class.

Pay special attention to the operation of hash tables, as key objects to correctly rewrite the equals and hashCode methods.

Try to return the interface instead of the actual type, such as List instead of ArrayList, so that the client code doesn't have to change if you need to replace ArrayList with LinkedList later. This is for abstract programming.