The linear table 1

1.1 an array

Simplicity: Arrays are one of the simplest data structures.
Contiguous memory: The array space is contiguous and stored in the order requested, but the array size must be specified.
Array space is inefficient: There are often free areas in an array that are underutilized.
Cumbersome: Adding and deleting arrays is cumbersome.

Table 1.2 order

Memory for

How is the size of an ArrayList automatically increased? During the add, the size of the array is 1.5 times larger than the original size.

int newCapacity = oldCapacity + (oldCapacity >> 1);
When would you use an ArrayList?

Advantages of ArrayList: High tail insertion efficiency and random access. Disadvantages: Inefficient insertion or deletion (modification). Application: so use the situation with low frequency of modification and high search efficiency.
How does an ArrayList add or remove an object from an index? Is it inefficient? Explain why?

ArrayCopy is a memory consuming, time consuming operation.
How does ArrayList sequentially remove nodes

Iterators that delete the for loop can only delete the last node
The traversal method of an arrayList
1. Iterator next hasNext
2. The for loop

1. Delete duplicates in the sorted array

2. Search for the insertion position

3. Find the first and last positions of elements in the sorted array

1.3 list

The memory is not continuous.

Add node

Add node S after point P:

    s.next = p.next;
    p.next = s;
Copy the code

Remove nodes

Delete the node after P:

p.next = p.next.next
Modify the

p.data = new data();
To find the

Loop lookup.

Write a single linked list by hand, and reverse the single linked list elements, (A0, A1, A2, A3,.. An) – > (an, the an – 1,… A1, A0), the spatial and temporal complexity of the algorithm may be low.

Handwritten bidirectional Linkedlist, the implementation of add, delete, change and check, while comparing their own LinkList and source Linkedlist similarities and differences

1. Merge two ordered lists

2. Switch nodes in the linked list in pairs

3. Copy the linked list with random Pointers

Comparison of LinkedList and ArrayList

LinkedList is implemented based on the LinkedList. The memory of the LinkedList is hashed, so it is fast to add and delete (you only need to modify the reference relation of the node to point to the new node), but slow to search (it needs to traverse the LinkedList).
ArrayList is an array-based implementation that is not thread-safe, efficient, slow to add and delete (the original data needs to be copied), and fast to find (contiguous memory, using subscripts directly to access elements).

1.4 What is memory cache

Data is written to containers (list,map,set) and other data storage units in advance, which is the software memory cache.

1.5 LRU algorithm (Least Recently Used)

Algorithm thought: love the new and hate the old

New data is inserted into the linked list header
When a cache hit (that is, cached data is accessed), the data is moved to the table header
When the list is full, discard the data at the end of the list

1.6 a HashMap

Index = hash& (length-1). Hash conflicts occur when two keys are equal. The linked list storage structure resolves hash conflicts by storing multiple Node objects on the same bucket as linked lists.

The default size of the HashMap is 16, and the default load factor is 0.75. When the size of the key-value pair in the Map is greater than the load factor *length, the HashMap is expanded.

The expansion is to avoid hash conflicts.

When the loading factor is 0.75, hash conflicts are reduced under the premise of maximizing memory space.

To avoid expansion, new HashMap needs to pass in the size of the map: the estimated size of the map /0.75 +1. In the HashMap constructor, this value is converted to the nearest power of 2, which is the size of the map.

When is the array of the HashMap initialized?

The array of the HashMap is initially empty. When the array is detected to be empty, reSize is called to initialize the array.

The PUT method is called when the HashMap is actually in use, so the array is initialized in the PUT method to save memory.

Why the HashMap size is a power of 2: A power of 2 makes full use of every bit of hashCode and reduces hash collisions when evaluating array subscripts.

Loading factor *length= threshold. The existence of threshold will waste 25% of memory space in hashMap, which is a space-for-time method adopted by hashMap to improve efficiency.

Android devices tend not to have a lot of memory, so SparseArray was introduced to reduce memory waste.

What is a HashMap? Why use it?

Data structure of HashMap:
- JDK1.7 and before: array + linked list
- JDK1.8: Array + linked list + red-black tree
The data structure of the nodes in the linked list/red-black tree is Node{hash, key, value, next}.

HashMap combines the advantages of arrays (quick lookup) and linked lists (quick addition and deletion) to improve storage performance.
How does HashMap work?

HashMap Stores data to the map using map.put(key,value), and obtains value using get(key).

Put process: Hash the key, calculate the array index = hash& (length-1), create Node{hash, key, value, next} nodes, and insert them into the linked list.

Get: Hash the key, calculate the index of the array index = hash& (Length-1), locate the target bucket, traverse the linked list, and return the target value when the hash and key are equal.
What happens when two objects have the same hsahCode? Hash conflict
How do I get an object when two objects have the same hsahCode?

When map.get iterates through the linked list, the value is returned only when the hash and key conditions are the same.
What if the size of the HashMap exceeds the capacity defined by the Load factor?

The default loadFactor is 0.75. When the HashMap size exceeds loadFactor*length, the HashMap size is doubled.
What are the problems with resizing the hashMap?

There is indeed a conditional race when resizing a HashMap, because if both threads find that the HashMap needs to be resized, they will try to resize it at the same time. During resizing, the order of the elements stored in the list is reversed because the HashMap does not place the elements at the end of the list when moving to the new bucket location, but at the head to avoid tail traversing. If conditional competition occurs, then the cycle is endless
Why warpper classes like String and Interger are good for keys?

Because strings are immutable, and you’ve overridden the equals() and hashCode() methods. Immutability is necessary because in order to evaluate hashCode(), the key is prevented from changing, and if the key returns a different hashCode when it is put in and when it is retrieved, the desired object cannot be found in the HashMap. Immutability has other advantages such as thread safety.
Can custom objects be used as keys?

Override the hsahCode and equels methods as keys.

1.7 SparseArray

SparseArray is a binary array structure based on the idea of HashMap + binary search. An int[] holds the key, and an Object[] establishes the mapping relationship by array subscript.

Key in ascending order,

Put: Finds the insertion location by binary search, and inserts by ArrayCopy.

Get: Use binary search method to find the target key and locate the value.

Remove: The binary search method is used to find the target location. Instead of deleting the value, the value of the corresponding location is set as DELETE. Reduce the performance cost of ArrayCopy when deleting, and simply change the value when putting data to that location again. The faster you use it, the faster you use it.

SparseArray saves memory without causing conflicts.

SparseArray gets faster the more you use it.

Disadvantages: Key is int.

According to these characteristics of SparseArray. We can analyze its usage scenarios:

Key is an integer.
The number of elements is relatively small;

1.8 ArrayMap

ArrayMap is implemented based on HashMap + SparseArray, which is the same principle as SparseArray.

ArrayMap solves the problem of SparseArraykey being int;

SparseArray solves the HashMap memory waste problem.

HashMap solves the problem of slow addition and deletion of ArrayList and slow search of LinkedList.

1.9 Container Summary

Collections rely on iterators, including lists (ordered) and sets (elements are not allowed to repeat).

The Map:

2 the tree

2.1 the tree

Finite set of N nodes.

Commonly used intraoperative terms:

Root node: There is a special node in the tree called Root.
Subtree: Other nodes can be divided into several disjoint trees, which become the “subtrees” of the original node.
Degree of node: the number of subtrees of nodes.
Degree of tree: The maximum degree of any node in the tree.
Leaf node: node with degree 0.
Parent: A node with a child tree is the parent of the root of its child tree.
Child: If A is the parent of B, B is the child of A.

Tree characteristics:

Subtrees are disjoint
In addition to the root, each node has only one and only one parent
A tree of N nodes only has N minus 1 edges

2.2 binary tree

Tree of degree 2, and the subtrees have left and right order.

2.3 Huffman tree

3 stack

4 graph

5 sorting and search algorithms

HashMap: synchronized (volatile+CAS

The data structure