Java Collections Framework
The collection and map
The collection subclass:
1. The list elements are ordered and repeatable
Implementation: ArrayList is like a dynamic array, variable length, default 10
Not thread-safe, use vector instead
Linkedlist. Similar to a two-way linkedlist. Suitable for addition and deletion, not thread-safe
Arraylist, for lookups
2. The set element is unordered and non-repeatable.
Implementation: HashSet, the underlying implementation based on hashMap
Linkedhashset. Based on linkedhashMap implementation, and the difference between hashset is to increase the chain table structure
Treeset: a binary sort tree
3.queue
Queue +list – > LinkedList
map
In the form of a key-value pair, key cannot be repeated and value can be null
Implementation class: hashmap
Thread-safe map: CurrenthashMap, which is thread-safe and efficient (the underlying red-black tree query is efficient)
The difference between arrays and linked lists
1. Array fixed length, easy to waste or insufficient, linked list can be dynamically allocated
2. Arrays are allocated in stacks (except for new ones), which is convenient but has poor degrees of freedom. Linked lists are allocated in stacks, which has large degrees of freedom but is troublesome to manage
3. Array access with subscript, fast, linked list must be accessed from scratch, slow
4. Linked lists are suitable for addition and deletion
Difference between hashMap and HashTable
1. Hashmap is thread-safe, hashTable is thread-safe
2. The value of the hashMap key is allowed to be null, but that of the HashTable is not allowed
3. For threading reasons, HashMap is relatively efficient
Implementation mechanism of hashMap
1. Maintain an array where each element is a linked list, and each node in the list is an array of entry [] key-value pairs
2. Implement the array + linked list features, so add and delete check changes are very fast
3. Each newly added node is placed at the beginning of the linked list, and the newly added node points to the beginning of the original linked list
4. Int I = hash (key, hashCode) & (len-1) for each key
The difference between heap, stack, queue
The stack is used to hold local variables, parameters, or intermediate results of a calculation, and is released as soon as the scope of the variable ends
The heap is used to store arrays and new objects or member variables, all new objects are stored in the heap (new objects), not automatically recycled, users can not access
Queue linear structure, first in, first out (tree hierarchy traversal)
String, StringBuffer and StringBuild are different
String generates a new object every time it manipulates a string
Stringbuffer does not generate new objects and is thread-safe
Stringbuilder is thread unsafe
Algorithm thought
1. Greedy algorithm (local optimal solution)
2. Divide-and-conquer algorithm (divide the problem of size N into k small problems, each problem is independent and of the same nature, and the solution of the small problem is the solution of the original problem)
3. Dynamic programming algorithm (similar to divide-and-conquer method, the former problem provides information for the latter problem, retains the optimal solution according to possible solutions, and discards other local solutions)
4. Backtracking algorithm (the process of searching for attempts and returning backtracking if conditions are not met)
5. Recursive algorithm (decomposition of repeated problems into subproblems, with a recursive termination condition)
The difference between abstract classes and interfaces
1. Inheritance: A class can inherit only one class and implement multiple interfaces
2. Abstract methods: the interface is full of abstract methods, abstract class can have abstract methods, and can have method body
3. Constructor: There is no constructor in the interface. There are constructors in abstract classes
4. Instantiate aspects: Abstract classes cannot be instantiated, and interfaces cannot be inherited
5. Modifier aspect: Methods in abstract classes can use modifiers other than private, and interfaces are public by default
6. Implementation speed: Abstract analog interface speed is fast
7. When adding a new method: The abstract class does not need to change the current code, but the interface needs to change the class that implements the interface
A common method of the object class
1. Equals
2. Clone the cloned object
3.tostring
4. The hashcode method
5. Method of thread synchronization
6. Getclass gets information about the current class
Jdk1.8 new features
1. Allow the interface to add a non-abstract method implementation using the default keyword
2. Lambda expressions (which allow a function to be passed as an argument to a method)
The Date time API reinforces time and Date handling
Optinal class, used to resolve null pointer exception
How to realize the hierarchy of tree traversal -> queue
Linked list (change pointer)
Chain surface test common types
Structure: data field + pointer field to the next node
Function: Data is stored in a certain order and can be added or deleted on any node
Types: one-way linked lists, two-way linked lists, circular linked lists
Advantages: sequential structure, suitable for adding and deleting
Disadvantages: pointer domain, large space; Only know the address of the head node, search trouble
1. Linked list inversion: define three Pointers to record the current traversed node, the previous node and the next node respectively, and then traverse in turn to point the pointer of the current node to the last node
2. Print the linked list from end to end (reverse the order and think of the stack first)
3. Merge ordered lists
4. Determine whether the linked list has a ring: define two Pointers, we use two Pointers to traverse: first pointer takes one step each time, second pointer takes two steps each time, if the first pointer and second pointer meet, it indicates that there is a ring.
5. Find the penultimate KTH node of the linked list
We define two Pointers, the first pointer from the head of the list pointer traverse step forward k – 1, keeping the second pointer: starting from the first step of k, the second pointer began from the head of the list pointer traversal, due to the distance of two Pointers to keep in k – 1, when the first go ahead (of) when the tail pointer to a linked list of nodes, the second pointer (walk behind The pointer is exactly the KTH node from last to last.