map and set - natural search and lookup semantics

Binary search tree BST: TreeSet/TreeMap

Hash table: HashSet/HashMap

One, map classification

In a hashMap, the insertion order of elements is independent of the storage order.

If you need the same insertion order and save order, use LinkedMap.

1. In the hashMap, if the key is the same, repeat the assignment, and the last time is equivalent to the update operation

In 2.hashMap, when the key value is different, the value can be different

3. Both the key and value of the hashMap can be empty.

The key of the Treemap cannot be empty, otherwise a null pointer exception will occur

Summary:

Second, set collection: deduplication

Iterate over the set collection and use the for-each loop directly

As long as it is a subclass of the Iterble interface, it can be traversed directly using the for-each loop.

When traversing the map collection, you need to convert the map to a set for for-each traversal.

for(Map.entryentry :entry.entrySet())

The difference between 1.== and equals:

==Compare the two values ​​for equality

If the comparison is between two basic types, it is whether they hold the same value.

If two reference types are being compared, the value stored by the reference type is just an address.

equals method is used to compare whether two objects want to be equal. At this time, the conditions for equality need to be defined by our users.

2. What is the difference between comparable and compator?

When a class implements the comparable interface, it means that the class has the ability to be compared, and the class itself has the ability to be compared.

compator is a method that we write to compare when a class cannot be compared, for example:

JDK's priority queue, the class passed in by PriorityQueue itself implements the comparable interface ->Freq or passes in a comparator,

PriorityQueuequ1 = new PriorityQueue<>():

PriorityQueue qu2 = new PriorityQueue<>(new FreqTwoDesc());

See only one output, generally use set

What is the difference between set and list?set cannot contain duplicate elements

Binary search tree: (generally, the value is not considered equal, the elements are not repeated)

1. is a binary tree (each node has at most two nodes)

2. For the node values ​​of the nodes in this tree, all node values ​​of the left subtree

Judgment binary search tree: In order traversal of the tree, you can get an ascending set.

The process of finding elements of a binary search tree is actually a binary search (logN) -> binary search tree BST

Seeing that logN associates with "tree".

The newly added elements in the BST must be added to the leaf nodes.

public void add(int val){root = add(root,val);}public TreeNode add(TreeNode root, int val){//Insert a new node val into the BST rooted at root//create new nodeTreeNode newNode = new TreeNode(val);if(root == null){//The current value is the root node to be insertedsize++;return newNode;}if(val < root.val){// insert in the left treeroot.left = add(root.left ,val);}else{//At this time, it is larger than the root noderoot.right = add(root.right,val);}return root;}