An algorithm is a series of steps to solve a problem. Complexity is used to measure the efficiency of the algorithm. Time complexity is the number of times an instruction is executed, or the time it takes to execute. Space complexity is the consumption of storage space.
Innovative thinking: 1. Get 6 litres of water in 5 and 7 litres barrels. First, fill a 7-liter bucket with water, pour into a 5-liter bucket, and leave 2 liters. 5 liters go out, 2 liters go into a 5-liter bucket. Then, fill the 7-litre bucket with water, pour 5 litres into it and fill it up, leaving 4 litres of water in the 7-litre bucket. 5 liters go out, 4 liters go into a 5-liter bucket. Finally, the 7-liter bucket is filled, 5 liters are filled, and 6 liters are left in the 7-liter bucket.
Use big O notation to estimate time complexity: ignore constants, coefficients, and low orders. The estimated constant is O(1); N +3 is estimated to be O(n); N ^2+n is estimated to be O(n^2); N ^3+n^2 is estimated to be O(n^3); The logarithm estimate is O(logn); N +nlogn is estimated to be O(nlogn); 2 to the n is estimated to be O(2 to the n). The complexity of the common comparison: O (1) < O (logn) < O (n) < O (nlogn) < O (n ^ 2) < O (n ^ 3) < O (2 ^ n) < O (n!) < O (n ^ n). N indicates the data size. Multiple data sizes O(n+ K). In general, the amortized complexity is equal to the best complexity. Common time complexity: recursive complexity is O(2^n), similar to a binary tree, 1+2+4+8+… . = 2 ^ 2 ^ 0 + 1 + 2 ^ 2 ^ 2 + 3 +… + 2 ^ n = 2 ^ (n + 1) – 1 = > O (2 ^ n); The iterative method for finding the NTH Fibonacci number is O(N), a for loop; Using the mathematical formula, the complexity is O(1); While ((n=n/2) > 0) execute log2^n;
(mathematical calculation: logn is the logarithm of base 10 of n, log2^n = log2^9 * log9^n, so log2^n, log9^n are converted to: constant *logn;) While ((n=n/2) > 0) {} =log base 2 to the n, if (n=n/2) > 0); 2 to what power is equal to n, log base 2 of n, order logn.
Recursion: to simplify the idea of solving the problem, to make the code more concise, not to find the optimal solution. Idea: break down problems, large problems break down into small problems, small problems become smaller problems. Recursion can be used for many problems related to lists and binary trees. Routine: first clear function function, clear relationship between the original problem and sub-problem,. The spatial complexity of the recursive call = the depth of the recursive call * the helper space required for each call. Binary tree traversal: the space complexity is O(h), worst case, is the list h=n, O(n).
Summation formula: 1+2+3+…… +n = n*(1+n) / 2: func sum(n int) {if n<=1 return n return n + sum(n-1)}
func sum(n int) { if n<=1 return n return (n + 1) * n >> 2 }
Find the NTH Fibonacci number 0, 1, 1, 2, 3, 5, 8, 13… .
N <=1 return n; fib(n) = fib(n-1)+ fib(n-2); return fib(n); The complexity of the 1 + 2 + 4 + 8 +… . = 2 ^ 2 ^ 0 + 1 +… .+2^n = 2^(n+1)-1=>O(2^n). Algorithm 2 uses iterative method: first := 0; second := 1; for I:=0; I
Recursion can cause a lot of double computations. How to avoid double computations: You can optimize by using arrays to store index computations, each index only evaluated once. The time complexity can be optimized to O(n), the space complexity is O(n), and the depth of recursion *O(1)=O(n).
Func fib(n int) int {// iterated if n == 0 {return 0} first := 0 second :=1 for I :=1; i
Func fib1(n int) int {if n <= 1 {return n} return fib(n-1) + fib(n-2)}
Dynamic array: will cause a lot of waste of memory space, can be used to reduce the size of the technology to solve, the size of the improper setting will lead to the complexity of the shock, but open up, destroy the number of memory space is relatively small; Expansion problem, the underlying array space is insufficient, need to expand the underlying array; Element memory will move when deleting or inserting elements. Emptying an array sets all object elements to nil; Element memory addresses are contiguous.
OldCap + (oldCap >> 1); oldCap + (oldCap >> 1); X over 2 is the same thing as X greater than or equal to 1. To see what the BTH value of a is, (a>>b)&1.
Downsizing: If memory usage is tight and dynamic arrays have more free space, consider downsizing. If the capacity expansion multiplier or capacity reduction time is not properly designed, the complexity may oscillate.
Dynamic Array interface: Clear, size, isEmpty, contains(e), add(e), get(index), set(index, e), add(index, E), Remove (index), indexOf(e), arrayList(Capacity).)
NSMutableArray underlying contains: _used count, _list buffer pointer, _size buffer size, and _offset is the index of the first element in the array of buffers. __NSArrayM uses circular buffer. Insert or delete memory at both ends without moving; Access uses index+offset to get the value; If you insert it in the middle, it will be inserted in a way that moves the least memory; Removing intermediate elements is also the way to move memory with the least movement; Removing header or tail elements does not move memory; The ring buffer is expanded when it is full. The use of a linked list to achieve the ring buffer is better, when expansion does not need to carry out a lot of memory movement, the use of array expansion when the need for a lot of memory movement.
__CFDictionary structure: there are two arrays of keys and values in _keys and _values. The arrays are of the same length. Calculate the hash value h based on the key, the empty bin array capacity n, calculate index=h%n. Hash collisions are resolved using the zipper or addressing method. To expand the hash table, rehash is required.
1. Remove duplicates from an ordered array in situ: give you an ordered array nums. Remove duplicates in situ, so that each element appears only once, and return the new length of the deleted array. Do not use extra array space. You must modify the input array in place and do so using O(1) extra space. Use double Pointers. Check whether len(nums) is 0. Initialize the pointer to the pre pre = 0, for loop through the array elements, the judgment nums [pre]! Nums [I] = nums[I], nums[I] = nums[I], nums[I] = nums[I], nums[I] Return length pre+1.
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}\
left := 0 for right:=0; right<len(nums); right++ { if nums[left] ! = nums[right] { left++ nums[left] = nums[right] } } return left+1Copy the code}
Remove duplicates from an ordered array II: in place, each element occurs at most twice.
func removeDuplicates(nums []int) int { pre := 0 for i:=0; i
2, integer array NUMs, determine whether there are duplicate elements. Returns true if it exists. Use the dictionary map. Initialize dict := make(map[int]int), traverse nums, and check whether the dict contains elements with nums[I] as key, _, ok := dict[nums[k]], if not, store nums[I] as key and I as value in dict. If it returns true, it means there are duplicates. Return false if it is not found.
func containsDuplicate(nums []int) bool {
dict := make(map[int]int)
for i:=0; i<len(nums); i++ {
_, ok := dict[nums[i]]
if ok {
return true
} dict[nums[i]] = i
}
return false
}
With the help of a set, an array element is stored in a set. If there are duplicates, they will be overwritten. Finally, compare the length of the set and the length of the NUMs. If not, there will be duplication.
There are duplicate elements: given an array of integers and an integer k, determine whether there are two different indexes I and j in the array such that nums[I] = nums[j] and the absolute value of the difference between I and j is at most k.
func containsNearbyDuplicate(nums []int, k int) bool {
dict := make(map[int]int)
for i:=0; i<len(nums); i++ {
v, ok := dict[nums[i]]
if ok {
if i – v <= k {
return true
}
}
dict[nums[i]] = i
}
return false
}
The best time to buy or sell a stock: an array of prices. Prices [I] stands for day I. Design an algorithm to maximize profits.
You can only buy and sell once. Choose a day to buy the stock and a future day to sell the stock. Calculate the maximum profit you can make.
func maxProfit(prices []int) int {
minPrice := prices[0]
profit := 0
for i:=1; i<len(prices); i++ {
if prices[i] < minPrice {
minPrice = prices[i]
} else if profit < prices[i] – minPrice {
profit = prices[i]-minPrice
}
}
return profit
}
You can make as many trades as you can, buying and selling shares multiple times, and you have to sell them before you can buy them again. Use the greedy algorithm. The process of calculating is not the process of buying and selling. Initialize profit:=0. If prices[I]>prices[i-1], then profit = profit + prices[I]-prices[i-1]. Finally return profit.
Func maxProfit(prices []int) int {// for I :=1; i
prices[i-1] { profit = profit + prices[i] – prices[i-1] } } return profit }
4. Rotate an array: Move the elements of an array right by k positions, where k is non-negative. In-situ algorithm with space complexity of O(1). Solution 1: traversal. The complexity is O(kn). By moving one bit to the right, we insert the last element at zero, and then we move the last element around, and then we assign the last element to the first element, nums[0]=last. Solution two: use the flip. We first flip the entire array, then we flip the elements 0 through K, and k through last.
func rotate(nums []int, k int) {
n := k % len(nums)
reverse(nums)
reverse(nums[:n])
reverse(nums[n:])
}
Array element reversal: traverse the array nums, end condition len(nums)>>1. / / flip
func reverse(nums []int) {
l := len(nums);
for i:=0; i<(l>>1); i++ {
nums[i],nums[l-i-1] = nums[l-i-1], nums[i]
} }
5. Numbers that only appear once. A non-empty array, NUMs, with each element appearing twice except once. Find elements that only appear once. It has linear time complexity O(n). Without external storage space. Xor ^ operation: 0^b=b; 0 ^ 0 = 0; 1 ^ 1 = 0; a^a=0; Satisfy the commutative and associative laws: A ^b^a=(a^a)^b=b. Declare value=0, iterate through the array, assign the element ^value to value. The final value is the element to look for. The same element xor is equal to 0; A non-zero element on xor is equal to itself; Xor obeys the commutative and associative laws;
func singleNumber(nums []int) int {
n := 0
for _, v := range nums {
n ^= v
}
return n
}
6. Add one. An array of integers, nums, representing a non-negative integer, to which one is added.
7. Move zero. An array of integers, nums, moves all zeros to the end while maintaining the stability of non-zero elements, i.e. relative order. Double pointer, left, right, loop condition right<length, nums[right]! = 0 Switch left, right and left++. Outer right++.
8. The sum of two numbers. Nums, target, find the two integers in nums, and return their subscripts. Use a dictionary. X =target-v, x=target-v,
The intersection of two arrays. Given two arrays, calculate their intersection. Nums1 =[12341], nums2=[2116], intersection =[112]. There can be multiple repeating elements. Use a dictionary. We iterate through nums1 with a smaller len, store the elements in a dictionary, where key is the element value, value is the number of occurrences, and dict[v]++. Then we iterate through nums2, and if the element exists in dict and the value is greater than 0, we store it in the result array result, and then on dict[v] -.
func intersect(nums1 []int, nums2 []int) []int {
if len(nums1) > len(nums2) {
return intersect(nums2, nums1)
}
dict := make(map[int]int)
for _, v := range nums1 {
dict[v]++
}
result := make([]int, 0)
for _, v := range nums2 {
i, ok := dict[v]
if ok && i>0 {
result = append(result, v)
dict[v]–
}
}
return result
}
The intersection of two arrays. The output is unique for each element. Key map delete elements: delete(dict, v). func intersection(nums1 []int, nums2 []int) []int { if len(nums1) > len(nums2) { return intersection(nums2, nums1) } dict := make(map[int]int) for i,v := range nums1 { dict[v] = i } result := make([]int,0) for _,v := range nums2 { _, ok := dict[v] if ok { result = append(result, v) delete(dict, v) } } return result }
10. Peak index of the array of mountains. Find peak elements: An array of elements in ascending order, then descending order, beyond the peak elements. Using binary search, iterating over, initializing left=0, right= Len-1, then iterating over, ending condition left<right. Mid = (left + right) >> 1. If nums[mid] > nums[mid+1] = right= mid Otherwise, left = mid + 1, finally returns left.
Func peakIndexInMountainArray(arr []int) int { O(logn) left,right := 0, len(arr)-1 for left < right { mid := (left+right) >> 1 if arr[mid] > arr[mid+1] { right = mid } else { left = mid + 1 } } return left }
Func peakIndexInMountainArray(arr []int) int {// maxIndex :=0 for I :=0; i
arr[maxIndex] { maxIndex = i } } return maxIndex }
func findPeakElement(nums []int) int { left, right := 0, len(nums)-1 for left < right { mid := (left + right) >> 1 if nums[mid] > nums[mid+1] { right = mid } else { left = mid + 1 } } return left }
BinarySearch: write a function that searches nums for a target, returning a subindex if one exists, or -1 otherwise. 12345 func search(nums []int, target int) int {// [left right] Len (nums) for left < right {mid := (right + left) >> 1 if nums[mid] == target {// Else if target < nums[mid] {right = mid} else {left = mid+1}} return-1} else if target < nums[mid] {right = mid} else {left = mid+1}
11. Find the elements in the array that are larger than the left and smaller than the right. This element is larger than all the elements to its left and smaller than all the elements to its right. Time complexity O(n). First from right to left traversal, find the smallest right of all elements, stored in an array rightMin. Then from left to right traversal to determine whether the current element is greater than the left element, if yes, and the right of the smallest rightMin element comparison, if less than the condition is stored in the result array.
func find(nums []int) []int { l := len(nums)
var rightMins = make([]int, l)
rightMin := nums[l-1]
for i:=l-1; i>=0; i-- {
if nums[i] < rightMin {
rightMin = nums[i]
}
rightMins[i] = rightMin
}
var result = make([]int, 0)
leftMax = nums[0]-1
for i:=0; i<l; i++ {
if leftMax < nums[i] && nums[i] < rightMins[i] {
leftMax = nums[i]
result := append(result, nums[i])
}
}
return result
Copy the code}
12. Most elements. Find most of the elements in an array nums of length n. Most elements are elements that occur more than [n/2] in an array. Most elements are greater than n over 2, which is more than all the other elements combined. Suppose temp is the mode, and count is the number of times it occurs. When it encounters an element different from it, count-1, and the same element counts +1. When count==0, convert count to the current element, and eventually temp will convert to most elements.
// Method 1: Func majorityElement(nums []int) int {// time majorityElement(nums []int) space majorityElement O(1) if len(nums) == 1 {return nums[0]} // Mode temp := nums[0] count := 1 for i:=1; i<len(nums); i++ { if count == 0 { temp = nums[i] } if nums[i] == temp { count++ } else { count– } } return temp }
Count ‘func majorityElement1(nums []int) int {
If len(nums) == 1 {return nums[0]} temp := nums[0] count :=1 for I :=1; i<len(nums); i++ { if nums[i] == temp { count++ if count > (len(nums)>>1) { return temp } } else { temp = nums[i] count = 1 } } return -1Copy the code}
13, product the largest subarray. Integer array nums, find the contiguous subarray whose product is the largest. The subarray contains at least one number. Returns the product of the subarray.
Input: [2,3,-2,4] output: 6, subarray [2,3] input: [-2,0,-1] output: 0
func maxProduct(nums []int) int { imax, imin, max := nums[0],nums[0],nums[0] for i:=1; i<len(nums); i++ { if nums[i] < 0 { imax,imin = imin,imax } imax = maxFunc(imax * nums[i], nums[i]) //-2 * 3 -2 = -2 8 imin = minFunc(imin * nums[i], nums[i]) // -2 * 3 -2 = -6 -4 max = maxFunc(imax, max) // -2 } return max }
func maxFunc(x, y int) int { if x > y { return x } return y }
func minFunc(x, y int) int { if x > y { return y } return x }
1, a string /a/b/.. /c/./d; The current directory. B represents the subdirectory of a. Simplify the directory. First cut into an array, array elements a, b… , c,., d, and then go through and look at the element if it’s a letter, push it directly, if it’s… , discard the current element, and off the stack, if., discard the current element. The elements in the final stack are simplified.
2, palindrome number. Verify that the integer x is a palindrome integer.
func isPalindrome(x int) bool { y := x p := 0 for y > 0 { tail := y%10 y = y/10 p = p*10 + tail } if p == x { return true } return false }
3. Longest palindrome string. Given a string containing large message letters, find the longest palindrome formed by those letters. Case sensitive, return length.
Maximum string with no duplicate characters: the hash table is used when the number is involved. Construct the substring and the hash store the subscript. When it comes to substrings, consider sliding Windows.
Unidirectional linked list is the chain storage data, how much use on the application of how much memory space, will not cause the waste of memory space. The LinkedList members size, first, and first point to the head node. Each Node contains a next pointer to the next Node (Node). The node complexity of the linked list is O(n) according to index. The node complexity is O(1) when the node is added, and it needs to be searched before the node is added. The overall complexity is O(n). Virtual head node: a node added before the head node, which does not store data. Simplify the code and unify the processing logic of all nodes.
Unidirectional linked list: To insert or delete a node, you need to find the last node of this node. If the boundary is empty: head node, tail node, and the node before the tail node; For (node! =nil) {node = node.next}; To delete a given node in a unidirectional linked list: the value stored in the next node in turn overwrites the value stored in the previous node, and the last duplicate node is removed.
Unidirectional linked list use scenario: hash table.
(Can lead to a binary tree, only the right subtree of the binary tree is a unidirectional list……)
First create newHead=nil, iterate, create temp and move to next of head, then next of head points to newHead, then newHead moves to head, then head moves to Temp. / * *
- Definition for singly-linked list.
- type ListNode struct {
-
Val int Copy the code -
Next *ListNode Copy the code - }
*/ func reverseList(head *ListNode) *ListNode { var newHead *ListNode var temp *ListNode for head ! = nil { temp = head.Next head.Next = newHead newHead = head head = temp } return newHead }
2, ring linked list, judge whether there is a ring list: create slow pointer slow, fast pointer fast, slow pointer slow step slow=slow.Next, fast pointer fast two steps fast= fast.next.Next, when the slow pointer and fast pointer meet slow==fast that there is a ring list.
func hasCycle(head *ListNode) bool { var slow *ListNode fast := head for fast ! = nil && fast.Next ! = nil { if slow == fast { return true } fast = fast.Next.Next
if slow == nil {
slow = head
} else {
slow = slow.Next
}
}
return false
Copy the code}
3, remove list element, remove node with val: If newHead is null and head is not val, initialize newHead and last to head and continue traversing head=head.Next. If head is not val, set last.Next to head. Continue the loop by moving last to next of last, and finally process the tail node.
func removeElements(head *ListNode, val int) *ListNode { newHead := &ListNode{} temp := newHead for head ! = nil { if head.Val ! = val { temp.Next = head temp = temp.Next } head = head.Next } temp.Next = nil
return newHead.Next
Copy the code}
Delete an intermediate node: a node in the list that is neither the head node nor the tail node is called an intermediate node. Given an intermediate node, remove it from the list. / * *
- Definition for singly-linked list.
- type ListNode struct {
-
Val int Copy the code -
Next *ListNode Copy the code - }
*/ func deleteNode(node *ListNode) { for node.Next ! = nil { node.Val = node.Next.Val
if node.Next.Next == nil {
node.Next = nil
break
}
node = node.Next
}
Copy the code}
func deleteNode(node *ListNode) { *node = *node.Next }
4, delete the repeated elements in the list, so that each element appears only once: the same as delete the list element difference judgment condition, judge the value of head is not equal to the value of last, set last.
func deleteDuplicates(head *ListNode) *ListNode { newHead := &ListNode{} last := newHead for head ! = nil { if last == newHead { last.Next = head last = last.Next } else { if last.Val ! = head.Val { last.Next = head last = last.Next } } head = head.Next } last.Next = nil return newHead.Next }
Remove duplicate elements from the sorted list and keep only the digits that are not repeated: If the next node of last is head (last->2->3head), then the next node of last will be moved to the next node of last. If the next node of last’s next is not head (last->2->2->3head), set the next pointer of last to head. Finally move head to next of head. That is, whether the last pointer takes a step, or the last next pointer goes to head.
NewHead := &listNode {}; newHead.Next = head; last=newHead; for head ! = nil { if last.Next.Val ! = head.Next.Val { if last.Next.Next == head { last = last.Next } else { last.Next = head }} head = head.Next}
func deleteDuplicates(head *ListNode) *ListNode { newHead := &ListNode{} newHead.Next = head last := newHead for head ! = nil { // last>1>1>2 last>1>2 if last.Next.Val ! = head.Val {// If last and head are equal, //last ->2 -> 3 head //last ->2 -> 3 head if last.Next == head {//head is the last. Last > 2 > 3 head = last.Next = Next; last > 2 > 2 > 3 head last.Next = head } } head = head.Next }
// Clear the trailing element if last.next! = nil && last.Next.Next ! = nil { last.Next = nil } return newHead.NextCopy the code}
6, the list of intermediate nodes, if there are two to return the second node: use a map or array. Map takes the index of the linked list as key, node as value, and takes out the intermediate node through the middle index; The array stores the list elements in an array at once, fetching the intermediate nodes by the array index.
Without the help of other storage space: speed pointer. slow = slow.Next; fast = fast.Next.Next; Fast finished, slow just halfway.
func middleNode(head *ListNode) *ListNode { left := &ListNode{} left.Next = head right := head // 1 2 3 // 1 2 3 4 for right ! = nil && right.Next ! = nil { right = right.Next.Next left = left.Next } return left.Next }
7, the reciprocal of the list of several nodes, using the fast pointer method, or the list into an array or map to obtain directly.
Delete NTH node from list:
func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{} dummy.Next = head slow := dummy fast := head for i:=0; i<n; i++ { fast = fast.Next }
for ; fast ! = nil; Next {slow = slow.Next} // Remove slow.next slow.next = slow.next.Next return dummyCopy the code}
8. Palindrome linked list. Determine whether a linked list is a palindrome list. First find the middle node of the list, firsthalawkward, and then flip the second half of the list. Return false if two linked lists are not equal
Func isPalindrome(head *ListNode) bool {// get the intermediate node, Summy := &listnode {} summy.Next = head slow := summy fast := head // 1 > 2 > 1 2 > 2 > 1 for fast ! = nil && fast.Next ! = nil { fast = fast.Next.Next slow = slow.Next if fast ! = nil && fast.Next == nil { slow = slow.Next } }
Var newHead *ListNode var temp *ListNode halfNode := slow.Next //head for halfNode! = nil { temp = halfNode.Next halfNode.Next = newHead newHead = halfNode halfNode = temp } for newHead ! = nil { summy = summy.Next if summy.Val ! = newHead.Val { return false } newHead = newHead.Next } return trueCopy the code}
Bidirectional linked list: there is one more pre pointer than unidirectional linked list. Head’s PRE points to nil, which improves the overall performance of linked lists. Suitable scenarios: Scenarios where elements are added and removed frequently at the head, tail, or anywhere; For frequent queries, use arrays for random access.
Unidirectional circular list: next of the tail node points to head. Bidirectional circular list: head’s pre points to the tail node, and the tail node’s next points to head. You can add: current; Reset causes current to move the terminal node; Current = current.next. Joseph’s ring problem. Static linked list: using an array to simulate, array element struct, next is the index.
Stack: Operations can only be performed on one end. Push adds elements to the stack, pop removes the Top element of the stack and obtains the Top element of the stack.
Use slices or arrays to simulate a stack. The first element of the slice is the bottom element of the stack, and the last element is the top element. The last element of the slice is the top element of the stack. Push is appending an element to the end node append.
2, the browser forward and backward, back is from the first stack pop off the top element, and push the element to the second stack, forward the second stack pop off the top element, and push to the first stack;
3. Undo and restore graffiti.
Valid parentheses: the string containing only ‘{‘,’} ‘, ‘(‘,’) ‘, ‘[‘,’] ‘is valid. The open parentheses are closed in the same order as the close parentheses. Make ([]byte,0) make([]byte,0) make([]byte,0) make([]byte,0) If this character is not equal to the value taken from the map for the top stack element, fase is returned. Return true if the stack element is empty.
5. Use stack to implement queue: when entering a queue, push it to inStack. When outStack is empty, pop all inStack elements one by one and push them to outStack. If the outStack is not empty, the outStack pops the top element.
Use the heap to emulate the stack
EnQueue: adds an element from rear; deQueue: removes an element from front; deQueue: removes an element from front; Queues operate from the beginning to the end of the elements, using bidirectional lists to achieve priority. PeekFirst looks at the header elements of the queue. PeekLast looks at the end of the queue.
(Queue with two stacks…)
Elements =elements[1:]; front is always 0; size is not equal to 0.
CircleQueue: The underlying implementation uses an array. Normally, front is the index at the front of the array, and end is the element at the end of the array. Front array index, queue length size. Index is (front+size)%capacity, 0123->(3+2)%4=1; Index is front = (front +1)% capacity, 0123->(3+1)%4=0; (front + I) % capacity; To expand, put front in the new array 0; (front+index)%capacity (front+index)%capacity (front+index)
Dual-end circular queue: Both ends can be deleted or added. – Added enQueueFront, (-1 + front)+capacity if negative, (-1 + front)%capacity if positive; For deQueueRear, the index algorithm is the same as for front (size-1 + front) to judge negative numbers. Rear =(front+size-1) % capacity
The operation efficiency of multiplication, division, modulus and floating point number is low.
Optimal modulus operation: a%b, if a is less than B, then a modulo b is a; If a is greater than or equal to b, and a is not greater than twice b, a modulo b is a minus b. A -(a>=b? B: 0). Index -(capacity > index? 0: capacity), if negative, index+capacity.
Similar to dynamic array optimization.
Using queues to implement stacks:
Priority Queue: implemented using BinaryHeap. Use: thread scheduling,.
(Binary heap… .).
Tree -> binary tree (degree Max. 2) -> true binary tree (degree 0 or 2) -> full binary tree (degree 0 or 2 and leaf nodes in the last layer) -> Complete binary tree (top to bottom, left to right).
Tree: A Tree has at most one root node, it can have only one root node, or it can be an empty Tree with no nodes. The degree of a node is the number of nodes in the tree. The node whose degree is 0 is called the leaf node. Level: The root node is at layer 1, children of the root node are at layer 2, and so on. Node depth: total number of nodes on the unique path from the root node to the current node. The maximum node depth is the tree depth. Height of node: Total number of nodes on the path from the current node to the farthest leaf node. The maximum node height is the height of the tree. The depth of the tree is equal to the height of the tree. Forest: a set of m disjointed trees, m greater than or equal to zero.
Tree can greatly improve efficiency.
BinaryTree: The degree (number of subtrees) of each node is at most 2, and the left subtree and right subtree are ordered. Special binary tree: empty tree, one node tree, only right subtree is unidirectional linked list.
Proper BinaryTree: no nodes of degree 1. (degrees 0 or 2)
Full BinaryTree: There is no node whose degree is 1 and all leaf nodes are at the last layer. A full binary tree must be a complete binary tree.
Complete binary tree: From top to bottom, left to right, the nodes are fully arranged. Only the last two layers of leaf nodes can appear; The last layer leaves are aligned to the left; The node whose degree is 1 has only the left subtree; The node whose degree is 1 can only have one at most. A complete binary tree is a full binary tree from the root node to the second-to-last layer; With the same number of nodes, the height of a complete binary tree is the smallest.
Binary search tree has high efficiency: the worst time complexity of adding, deleting and searching can be optimized to O(logn). The worst time complexity of binary search for ordered dynamic arrays is O(logn); The average time complexity of adding, deleting, and traversing searches is O(n);
Binary Search Tree: the value of any node is greater than all the values of the left subtree of the node, and less than all the values of the right subtree of the node; The left and right subtrees of a binary search tree are also a binary search tree; The elements stored in the binary search tree must have comparability and specify the comparison method; Can’t be nil; There is no index, and elements are added in no order.
Interface design: Size, isEmpty, clear, add(e), remove(e), search contains(e). Node Node contains left, right, and parent.
> > < span style = “color: RGB (62, 62, 62); line-height: 20px; white-space: normal; white-space: normal;” If they are equal, they cover directly; When initializing, pass in the comparator block or closure, or pass in the object that supports the protocol method, or both.
Property 1, find the number of leaf nodes: the number of leaf nodes of all binary trees n0 is equal to the number of nodes with degree 2 n2 plus 1, i.e. N0 =n2+1. Derivation: Total number of nodes n = n0+n1+n2; The total number of edges = n – 1; The number of edges on the node whose degree is 0 is 0, the number of edges on the node whose degree is 1 is 1, and the number of edges on the node whose degree is 2 is 2. The total number of edges is n1+2*n2.
(Number of leaf nodes n0, number of nodes with degree 1 N1, number of nodes with degree 2 N2)
Property 2, complete binomial tree, find the number of leaf nodes of a complete binomial tree with summary points n: If a complete binomial tree has 768 nodes, find the number of leaf nodes: Derivation: summarize the number of points n, the number of leaf nodes is n0, the number of nodes n1 with degree 1, and the number of nodes N2 with degree 2. N = n0 + n1 + n2; N0 = n2 + 1; => n = 2 * n0 + N1-1; Because n1 = 0 or 1; When n1 = 1, then n = 2 * n0, n is even, n0=n/2, number of non-leaf nodes == n – n0= =n/2; When n1 = 0, then n = 2 * n0-1, n is odd, the number of leaf nodes n0 is (n + 1)/2, and the number of non-leaf nodes = n- n0 == (n-1)/2. The number of leaves is (n+1)/2 and if you round it down, it’s (n+1) >> 1; The number of non-leaf nodes is n/2 and we’re rounding down.
Property 3: The number of nodes at layer I of a full binary tree is 2^(I -1).
Property 4: the number of leaves in a full binary tree with height h is 2^(h-1), and the number of summary points is 2^ h-1 = 2^0+2^1+… . + 2 ^ (h – 1). In a binary tree of the same height, the full binary tree has the largest number of leaf nodes and the largest number of summary points.
2^0+2^1+… . + 2 ^ n = 2 ^ (n + 1) – 1)
Property 5, complete binomial tree, sum up the point n of the height of the complete binomial tree: height h (h >=1), then at least 2^(h-1) nodes =2^0+2^1+… + 2 ^ (h – 2) + 1. At most, it’s a full binary tree with 2 to the h minus 1 nodes. So it’s going to be between 2 to the h minus 1 and 2 to the h, 2 to the h minus 1 is less than or equal to n is less than 2 to the h, so log h minus 1 is less than log2 to the n is less than h, and log2 to the n is less than h is less than log2 to the n plus 1, so h is equal to log2 to the n plus 1.
Property 6: Find the parent node index and child node index of the ith node of the complete binary tree: there are n nodes, n>0, and the nodes are numbered from top to bottom and left to right starting from 1. For any ith node: if I =1, it is the root node; If I >1, its parent is numbered as floor(I /2) rounding down; If 2i <= n, its left children are 2i, which means 2i is the number of left children of node I if it is not greater than the number of summary points, and if it is greater than the number of summary points, it has no left children; Likewise, the number of right children is 2* I +1.
(Binary heap… ..) (Binary heap uses this property, binary heap is a complete binary tree, using an array implementation, requires a child node of two nodes, parent node)
Binary tree flip: enter root node, check root node is nil, return nil, switch left and right nodes of root node, then recursively flip left and right child nodes of root node root.left, root.right.
Linear data structure traversal is divided into positive order traversal, reverse order traversal. Two directions.
Traversal of binary trees :(not unique to binary search trees)
PreorderTraversal: traversal the root node, left subtree, and right subtree in sequence. Give you the root node of a binary tree, return the preorder traversal of its node values, recursively: New slicing the result first, determine the root node is empty, no data stored in the slice, then the recursive call, the incoming of the root node left subtree, return the data section, not empty additional biopsy elements to the result, and then continue to recursive call, the incoming of the root node right subtree, return the data section, not empty additional biopsy elements to the result, Finally, the section result is returned.
InorderTraversal: traversal the left subtree, root node and right subtree in sequence. The result of order traversal in binary search tree is in ascending order; PostorderTraversal: traversal the left subtree, right subtree and root node successively; The front traversal of the root node is the preorder, the middle traversal is the middle order, and the back traversal is the back order.
LevelOrderTraversal: Accesses each node from top to bottom and left to right. (important)
Idea: Use queues. First, the root node is enqueued, then the first element A is enqueued, and the left and right children of A are enqueued, and the loop continues until the queue is empty.
Implementation process: DeQueue, queue := []TreeNode{root} result =make([][]int, 0) level=make(int[],0) Create the number of nodes at the current layer size=1 and store the number of nodes at the next layer nextSize := 0. Then loop to determine whether the queue is empty. If the queue is empty, end the loop. If it is not empty then loop, deQueue the first element, check whether the left and right nodes are nil, if it is not nil store the left and right nodes in the queue, store the Val of the left element in the level array, level = append(level, root.val), If size==0, it means the end of the layer. Store level in the result two-dimensional slice. Empty level, size= nextSize, empty nextSize. The number of elements at the next level is the size of the queue when traversal of elements at this level is complete. You can calculate the height of a binary tree, and the number of one-dimensional arrays in a two-dimensional array is the height.
Traversal application 1, using sequential traversal to determine whether a tree is a complete binary tree: if the tree is not nil, start a sequential traversal of the binary tree (using queues). If the node left! = nil, queue node.left; If node.left==nil && Node.right! = nil, return false; If the node. Right! = nil, add node.right to the queue; If node.right==nil, then all the remaining nodes traversed are leaf nodes. Otherwise, false is returned. Four cases are combined: The left and right child nodes are null.
Traversal application 2, using sequence traversal to calculate the height of the binary tree.
Traversal application 3, using preorder traversal print binary tree: (locationStr = locationStr + prefix); (locationStr = locationStr + prefix); (locationStr = locationStr + prefix);
Traversal application 4, using the order traversal of binary search tree elements in ascending order.
Traversal application 5, using the sequential traversal to some of the children after the parent operations.
Precursor node predecessor: The previous node in sequence traversal. Succeeded node: Contrary to the precursor, the middle order traverses the last node. Binary search tree deletion uses precursors and successors.
For a binary search tree: the precursor node is the previous smaller node, that is, the largest node of the left subtree; If the node left! = nil, then prodecessor = node.left.right… Right == nil; If node.left == nil && Node.parent! = nil, prodecessor = node. The parent. The parent, the parent… If there is no right subtree, there is no precursor node; if there is no right subtree, there is no precursor node. If node.left == nil && Node.parent == nil, then there is no precursor node;
Binary search tree delete node: delete leaf node, judge is the left and right child node of the parent node, delete node.parent. Left =nil; Parent =node.parent, node.parent =node.parent, node.parent =node.parent, node.parent =node.parent, node.parent =node.parent Right =child; root=child, child.parent=nil; Delete the node whose degree is 2;
The complexity of a binary search tree is O(h) == O(logn). The complexity of binary search tree after degradation to linked list: O(h)==O(n). When n is relatively large, the performance difference between these two cases is relatively large. For example, n equals a million times is about 2^20, and the binary search tree has a minimum of 20 searches and a maximum of a million searches. When nodes are added or removed, the binary search tree may degenerate into a linked list. Prevent binary search tree from degrading to a linked list: keep the complexity of add, delete, and search at O(logn). Balance: When the number of nodes is fixed, the closer the left and right subtrees are to each other, the more balanced (lower) the binary tree is. Improved binary search tree: the order in which nodes are added and removed is not limited and can be considered random. Therefore, the improvement scheme is as follows: after node adding and deleting operations, moderate balance can be achieved with as few adjustment times as possible, and the binary search tree can be restored to balance (reduce the height of the tree).
Balanced Binary Search Tree, BBST: A moderately Balanced Binary Search Tree. Common balanced binary search tree: AVL tree, widely used in the Windows NT kernel. Red-black tree: C++ STL (such as map, set); JAVA TreeMap, TreeSet, HashMap, HashSet; Linux process scheduling; Nginx timer management; AVL Tree and red-black Tree are also called self-balancing Binary Search Tree.
AVL tree: Balance Factor, Balance Factor: height difference between the left and right subtrees of a node. The height difference between the left and right subtrees of the leaf node is 0, so the balance factor of the leaf node is 0. Characteristics of AVL tree: The balance factor of each node can only be 1, 0 and -1 (absolute value <=1, if more than 1, it is called imbalance); The height difference between the left and right subtrees of each node is not more than 1; Search, add, and delete time is O(logn);
AVLTree and RBTree are inherited from BST, and BST is inherited from Binary Tree.
Adding elements to AVL tree: may cause all ancestor nodes to be unbalanced; As long as the lowest height of the imbalance point is restored to balance, the whole tree is restored to balance, only O(1) adjustment. AVL tree deletion: only the parent node may be out of balance; Balancing the parent may cause the higher-level ancestor to be out of balance, requiring up to O(logn) adjustments. Average time complexity: search O(logn); Adding O(logn) requires only O(1) rotations; To delete O(logn), a maximum of O(logn) rotations are required.
Ll-right rotation (single), RR-left rotation (single), LR-RR left rotation, LL right rotation (double), RL-LL right rotation, RR left rotation (double).
Red Black Tree: a self-balancing binary search Tree. Also called a balanced Binary B-tree, Symmetric Binary B-tree. A red-black tree must meet the following five properties: 1. Nodes are Red or Black. The root node is Black. 3. Leaf nodes (external nodes, empty nodes) are Black. 4. All children of Red nodes are Black. The parent of a Red node is Black. The path from the root node to the leaf node cannot have two consecutive Red nodes. 5. All paths from any node to the leaf node contain the same number of Black nodes.
B tree: a balanced multipath search tree, mostly used for file system, database implementation. B Tree features: A node can store more than two elements and have more than two child nodes. It has the characteristics of binary search trees. Equilibrium, where all subtrees of each node are of the same height. Are short. A b-tree of order m means that each node has at most m subtrees.
BinaryHeap: provides three interfaces, add element, get maximum, remove maximum. Using dynamic arrays or bidirectional lists, the maximum complexity for fetching and deleting is O(n), and the maximum complexity for adding elements is O(1). An ordered dynamic array or a bidirectional linked list needs to be sorted from small to large. The maximum complexity is O(1) for obtaining and deleting an element, and the maximum complexity is O(n) for adding an element. BBST red-black tree, get maximum, remove maximum, add element complexity is all O(logn). Heap, get the maximum value O(1), remove the maximum value, add elements are all O(logn).
Top K problem: Find the Top K data from a large amount of data. For example, find the largest 100 integers out of a million. Solution 1: you can use the heap to solve.
Heap, “Heap,” a tree-like data structure. Not to be confused with the heap space in the memory model. Common Heap implementations include: Binary Heap, also called full Binary Heap, etc. The characteristic of the heap is that the value of any node is always greater than or equal to >= or less than or equal to the value of the child node <=. If the value of any node is always greater than or equal to the value of >= child nodes, it is called a large top heap. If the value of any node is always less than or equal to the value of the <= child node, it is called the small top heap. It has to be comparable, just like a binary search tree.
The logical structure of a binary heap is a complete binary tree, so it is also called a complete binary heap. There is one more comparison than a complete binary heap. In a large top heap, the value of the root node is greater than the child node, and in a small top heap, the value of the root node is less than the child node. The bottom layer of binary heap is generally implemented using arrays.
Binary heap implementation interface: size, Comparator, isEmpty, clear, add, get, remove, replace
Take the big top heap for example. Add element implementation: first append the element to the array, and then determine the size of the new element and the parent node, larger than the parent node and the parent node exchange position, loop. Ends the loop if it is smaller than the parent or if there is no parent. This process of comparison is called siftUp.
Bubble, select, insert, merge, fast, hill, heap Sorting.
Bubble Sort: Compare two adjacent elements from the beginning, swapping if the first is greater than the second. Optimization 1: all ordered; Optimization 2: local order; Average, worst time complexity O(n^2). The best time complexity is O(n).
Func bubbleSort(s []int) {for end := len(s)-1; end > 0; end– { for begin := 1; begin <= end; Begin ++ {if s[begin] < s[begin-1] { Temp := s[begin] s[begin] = s[begin-1] s[begin-1] = temp}}} fmt.Println(“s:”, s)}
A sorting algorithm is stable if two equal elements remain in the same relative position before and after sorting.
In-place Algorithm: does not rely on additional resources or a few additional resources, only rely on the output to override the input. The space complexity is low, the space complexity is O(1).
Select Sort: Find the maxIndex of the largest element in the sequence, and then switch positions with the last element. Best, worst, average time complexity O(n^2). Getting the maximum value can be processed using the heap, with time complexity up to O(logn).
Func selectionSort(s []int) {for end := len(s)-1; end > 0; end– { maxIndex := 0 for begin := 1; begin <= end; Begin ++ {if s[maxIndex] <= s[begin] {// Maintain stability maxIndex = begin}} temp := s[maxIndex] s[maxIndex] = s[end] s[end] = temp }
fmt.Println("s:", s)
Copy the code}
An optimization of selection Sort. 1. The options are shiftDown and shiftUp. 2. Exchange.
Insert Insertion Sort: playing card Sort Divide the data into two parts: the ordered head and the unsorted tail. Each element is scanned from the beginning, and each time an element is scanned, it is inserted into the proper place in the header to keep the header data in order. The complexity of insertion sort is proportional to Inversion. The more Inversion pairs, the more complexity. A pair of inversions is a pair of inversions when you compare two numbers that you’re swapping. The average, worst complexity is O(n^2). It’s better to have order n. Insertion sort is particularly efficient when there are very few inversions, even faster than quicksort at the O(nlogn) level. When the data volume is not very large, the insertion sort efficiency is also very high.
Func InsertionSort(nums []int) []int {for begin := 1; begin < len(nums); Begin ++ {cur := begin for cur > 0 && nums[cur] < nums[cur-1] {temp := nums[cur] nums[cur] = nums[cur-1] nums[cur-1] = temp cur– } } return nums }
Optimization 1: Change swap to shift. First, the inserted element is backed up, and then the ordered data is traversed. If the element is larger than the inserted element, the element is moved one position to the tail until the element is smaller than the inserted element. The traversal stops and the element to be inserted is placed in the final position.
func InsertionSort2(nums []int) []int { for begin := 1; begin < len(nums); begin++ { cur := begin temp := nums[cur] for cur > 0 && temp < nums[cur-1] { nums[cur] = nums[cur-1] cur– } nums[cur] = temp } return nums }
BinarySearch: write a function that searches nums for a target, returning a subindex if one exists, or -1 otherwise.
Func search(nums []int, target int) int {// [begin end) Total number of elements in the range end-begin begin, end := 0, Len (nums) for begin < end {mid := (end-begin) >> 1 if nums[mid] == target { Else if target < nums[mid] {end = mid} else {begin = mid+1}} return-1} else {begin = mid+1}
Optimization 2: Use binary search to optimize insertion sort. Use binary search to search for insertion positions. Binary search, when target < nums[mid], searches from the left, other searches from the right, and returns the subscript of the insertion position. The average time complexity of insertion sort does not change O(n^2).
Func InsertionSort3(nums []int) []int {for begin := 1; begin < len(nums); Begin ++ {temp := nums[begin] insertIndex := searchIndex(nums, begin)
For I := begin; i > insertIndex; i-- { nums[i] = nums[i-1] } nums[insertIndex] = temp } return numsCopy the code} // 时间复杂度：O(logn) func searchIndex(nums []int, index int) int { begin, end := 0, index for begin < end { mid := (begin + end) >> 1 if nums[index] < nums[mid] { end = mid } else { begin = mid + 1 } } return begin }
Merge Sort: O(nlogn). Quick Sort: fastest.
Network:
The communication between computers is based on the IP address of the other party, nic address MAC address, and the transmitted data is finally received by the nic. The transmitted data includes the source IP address, destination IP address, source MAC address, and destination MAC address. If the network card discovers that the destination MAC address is its own, it passes the data to the next layer for processing.
First, it sends an ARP broadcast protocol to obtain the MAC address of the peer and propagate it in the same network segment. A complete ARP request, divided into three times: first computer 0 sends a broadcast to get the MAC address of computer 1, then computer 0 sends it to computer 1, and computer 1 replies. ARP is cached.
Network cables, coaxial cables, hubs have conflict areas. What is a conflict domain? Bridge: There are two interfaces that can learn which side of the Bridge each computer’s MAC address is on to isolate conflicting domains. Switch: The equivalent of a bridge with more interfaces, full duplex communication, is a LAN solution. When sending ARP broadcasts, the switch records the MAC addresses of all computers on the LAN and does not transmit the data to other computers. It’s safer than a hub, which doesn’t know the MAC addresses of other computers and sends data to everyone. Global network, using the switch, ARP broadcast will be sent around the world, will cause broadcast storm, is also more wasteful, there is a router. Router: Can forward data between different network segments to isolate broadcast domains. The same network segment is the same broadcast domain.
MAC Address Media Access Control Address. The value is 6 bytes (48 bits). The first three bytes: OUI, unique identifier of the organization. The last three bytes: network interface id. If all 48 bits are 1, the broadcast MAC address FFFF.FFFF.
IP Address Internet Protocol Address: Each host on the Internet has an IP Address. IPV4 32bit: 4 bytes. One byte and eight bits count as one part. IPV6 128 bits, 16 bytes. The IP address function is divided into two parts: Network ID (network ID) and host ID (host ID).
The network segment is the IP address bit by bit and the subnet mask. Address: 193.168.1.1 Subnet mask: 255.255.255.0 1100 0000.1010 1000.0000 0001.0000 1010 IP address & 1111 1111.1111 1111.1111 1111.0000 0000 Subnet mask
1111 1111.1111 1111.1111 1111.0000 0000 Segment 192.168.1.0Copy the codeIP address: 139.168.1.1 Subnet mask: 255.255.0.0 The network segment is 139.168.0.0
Class A address: Subnet mask 255.0.0.0. The first part corresponds to the network ID and the last three parts correspond to the host ID. The first part must start with 0, so the network ID range is: 7 0s to 7 1s in binary, 0 to 127 in decimal. 127 is a reserved network segment. 127.0.0.1 is the local Loopback address, which indicates the local address. The first part of the network ID from 1 to 126 is A class A address. The values of the next three parts range from 0 to 255. In the host segment, all zeros represent the network segment and all 1s represent the broadcast address. Therefore, the number of hosts in A class A network segment is 256256256-2 =2^24-2.
Class B address: Subnet mask 255.255.0.0. The first two parts are network ids. The first part must start with 10. Each part has 8 bits. Class C address: The default subnet mask is 255.255.255.0. The first three parts are network ids. The first part must start with 110.
123.210.100.200/16 indicates that the subnet mask has 16 1s, that is, 255.255.0.0, and each part has 8 bits.
Proper subnets can solve the following problems: Avoid IP address waste.
To access the Internet from a private IP Address, NAT is performed on a public IP Address. NAT and Network Address Translation are performed by a router. Saves network IP resources and hides real internal IP addresses.
In practice, a network is generally divided into five layers: the application layer, the transport layer, the network layer, the data link layer, and the physical layer.
The hub works at the physical layer. It has no IQ and cannot determine the original MAC address or target MAC address. Nics work at the physical layer and data link layer. The switch works at the physical layer and data link layer and determines the original Mac address and destination Mac address. Routers work at the physical layer, data link layer, and network layer.
Physical layer Physical: Sends Bits of the bitstream, defines interface standards, cable standards, transmission rate, and transmission mode.
Data Link layer Data Link layer: Sends Data frames. Frame is at least 64 bytes, plus the original Mac address and destination Mac address. Head + data + tail, the data part is passed down from the previous layer. Link: A section of physical line from one node to another node, router to router or switch.
The Wireshark captures Ethernet FRAMES. The Wireshark cannot see the tail of the data link layer, but only the head.
Network layer: Sends a Packet consisting of the head and data. A data Segment is usually a data Segment passed down by the transport layer. The first 20 bytes are fixed, a total of five lines, each line occupies four bytes, each line is 0 to 31 total of 32 bits. The Ethernet frame header and the network layer header are next to each other. The variable portion of the network layer header is 40 bytes at most. If the data at the network layer is too large, it will be divided into multiple frames at the data link layer. The receiver will combine the data at the network layer. How do they merge, how do they differentiate between packets?
At the head of the network layer, the Identification occupies 16 bits and the ID of the packet. When the packet is too large to be fragmented, the Identification of all slices of the same packet is the same. A counter manages packets’ ids, which are incremented by 1 with each packet sent. If the packet is too large and exceeds the maximum ID, it will start from 1. The Wireshark uses a Fragment Offset to locate the position of the Fragment. The Fragment Offset has 13 bits. To represent more bytes, the Fragment Offset is not the actual byte Offset.
At the network layer header, the Flags indicate whether there are More fragments: More fragments: Set 1 has More fragments.
Network layer header, Protocol: 8 bits, indicating the Protocol used for the encapsulated data. ICMP: 1, IP: 4, TCP: 6, UDP: 17, IPV6:41.
Header Checksum: Used to check whether the Header has errors.
Some protocols work directly at the network layer, such as ARP, IP, and ICMP, without the application layer and transport layer above. ICMP does not have transport layer reliable control, flow control, congestion control, so it is at the network layer.
Network layer header and TTL: the TTL is 8 bits. Each router reduces the TTL by 1 before forwarding. Once the TTL is reduced to 0, the router will return an error. By observing the TTL after the ping command, you can deduce the operating system of the peer and the number of routers it passes through. TTL is set by default by the operating system: 128 for Windows, 64 for Linux 2.0.x kernel, and 64 for Mac OS.
ping /? Ping IP address -i Packet size, sudo ping ke.qq.com -L 4000 ping IP address -f Fragmentation at the network layer is not allowed
The Wireshark can view Internet Protocol Version 4, Src IP address of the sender, and Dst IP address of the receiver at the network layer.
Transport layer Transport: data Segments are sent using TCP and UDP to ensure reliable transmission. If a certain data segment fails to be transmitted, the data segment is retransmitted.
The difference between TCP and UDP, packet format:
Transmission Control Protocol: Connection oriented; Reliable transmission, no packet loss; The head occupies large space; Slow transmission rate; High consumption of resources; Application scenarios: Browser, file transfer, and email sending. The corresponding application-layer protocols are HTTP, HTTPS, FTP, SMTP, and DNS.
User Datagram Protocol: connectionless; Unreliable transmission, best effort delivery, possible packet loss; The head occupies small space; Fast transmission rate; Small resource consumption; Application scenario: Audio and video call, live broadcast, pay attention to real-time transmission; The corresponding application layer protocol is DNS.
UDP is connectionless, reducing the overhead of establishing and releasing connections; Delivery to the best of our ability, reliable delivery is not guaranteed; No need to maintain some complex parameters, the header is only 8 bytes, TCP at least 20 bytes. The UDP header contains the 16-bit source port number, 16-bit destination port number, 16-bit UDP length, 16-bit UDP check, and Checksum.
UDP header: UDP port number: Takes 2 bytes. The value ranges from 0 to 65535. The source port of the client is a random port that is enabled temporarily.
UDP length: 16 bits 2 bytes: header length + data length
Checksum: 16 bits 2 bytes: pseudo header + header + data. Pseudo-header Contains 12 bytes: source IP address, destination IP address, UDP protocol 17, and UDP length. Pseudo – headers are not passed to the network layer.
The following packets are displayed: User Datagram Protocol, SRC Port:,Dst Port.
Netstat -an Viewing occupied ports netstat -anb Viewing occupied ports and applications
TCP: Data offset: 4 bits, multiplied by 4 is the Header Length. Since there is a fixed head of 20 bytes, the data offset is at least 5 and ranges from 0x0101 to 0x1111, with a maximum of 60 bytes. Same as the head of the network layer. The length of the header is how much the data is shifted to the right.
Reserved Indicates the Reserved slot.
Use some fields in the header to ensure reliable transmission.
The TCP/UDP data length can be inferred from the header of an IP packet at the network layer: Data length at the transport layer = total length at the network layer – Header length at the network layer – header length at the transport layer. The data part of the network layer is the transport layer (transport layer head + transport layer data).
TCP header Flags: URG, Urgent. When URG=1, the Urgent pointer field is valid, indicating that there is Urgent data in the current packet segment. The number of bits before the TCP data segment is Urgent data and should be transmitted as soon as possible. ACK, Acknowledgment, When ACK=1, the Acknowledgment number field is valid; PSH, Push; RST, Reset: When RST=1, it indicates that a serious error occurs in the connection and the connection must be released and re-established. SYN, Synchronization, when SYN=1 and ACK=0, that indicates that this is a connection request and that I want to set up a connection with you. If SYN=1, ACK=1; if SYN=1, ACK=1; FIN, Finish. When FIN=1, the data has been sent and the connection needs to be released.
Seq Sequence Number: contains four bytes. Each byte is assigned a number during transmission. Sequential bytes. The number is sequential. After a connection is established, the serial number represents the number of the first byte of the TCP data section that is passed to the other party this time. It’s 0 when you set up the connection.
Acknowledgment Number: Occupies 4 bytes. After a connection is established, the Acknowledgment Number indicates the Number of the first byte of the TCP data that is expected to be transmitted next time.
Reliable transmission: Stop waiting for ARQ protocol, Automatic Repeat-reQuest: A sends data M1 to B, B waits for the completion of receiving M1, tells A to acknowledge the completion of receiving M1, then A receives the acknowledgement and continues to send M2. Case 1: If A times out when sending M1 to B, M1 will be retransmitted. B dismisses the last timeout error packet. Case 2: A successfully sends M1 to B, and B tells A to confirm that THE receipt of M1 is complete. The acknowledgement of M1 times out. A retransmits M1. Or after a long time, B receives the first late confirmation M1, B does nothing and throws it away. Timeout retransmission.
It’s less efficient.
Improvement: Continuous ARQ protocol + sliding window protocol. Continuous ARQ refers to sending several consecutive pieces of data at once. There are four groups M1, M2, M3 and M4 in the sending window of A. After the sending is complete, the sending stops and waits for B’s confirmation. B has received all data M1, M2, M3 and M4, and confirms M4. M1, M2, M3, and M4 are continuous, so only M4 can be confirmed. After A receives the acknowledgement M4, the window slides to M5, M6, M7, and M8 to send the data in the window. After the data is sent, the window stops sending and waits for B’s confirmation.
Exception: If the receiving window can receive a maximum of four packets, but the sender only sends two packets. How does the receiver confirm that there are two more packets? After a certain amount of time there is no third packet, the sender is returned to acknowledge receipt of the two packets.
Sliding window: The window size is told to you by the receiver B side, and is determined by the receiver. The size of B’s receive cache tells A how big the sliding window is and how many bytes it can send. When the receiving end B sends the acknowledgement message to the receiving end A, it will tell the data cache size that the receiving end B can receive at that time, that is, the size of the sliding window, which may be different each time.
Window: 2 bytes. This field has the flow control function and is used to inform the other party of the size of the data that can be sent next time. The unit is byte.
SACK Selective Acknowledgment: During TCP communication, a packet in the middle of the transmission sequence is lost, for example, M3 is lost in M1, M2, M3, and M4. If there is no SACK, TCP retransmits the last confirmed packet and the next confirmed packet. If the last confirmed packet is M2, TCP retransmits M3 and M4. In this case, the PROPERLY transmitted M4 is resended, which degrades TCP performance. With SACK, receiver B will tell sender A which data is lost and which data has been received in advance, so THAT TCP only resends the lost packet (M3) instead of sending the subsequent correctly transmitted packet (M4). TCP header options contain a maximum of 40 bytes. SACK uses the TCP header option: Kind (1 byte). Kind=5 indicates the SACK option. Length, 1 byte, indicates the total number of bytes consumed by the SACK option. Left Edge, 4 bytes. The Right Edge is 4 bytes. The maximum number of bytes used by SACK option is 34=4*8+1+1. The maximum number of bytes used by SACK option is 34=4*8+1+1.
The client downloads a large file from the server: The application layer files are large and are cut at the transport layer and sent to the network layer. Why split the data at the transport layer rather than shard it at the network layer? Transport layer retransmission can improve the retransmission performance. Only the transport layer has reliable transport, that is, reliable transport is controlled at the transport layer. If there is no segmentation at the transport layer, once there is a loss of data, the entire transport layer has to be retransmitted. If segments are divided at the transport layer, once data is lost, only the lost segments need to be retransmitted.
TCP flow control:
Problem: If the receiver’s cache is full and the sender continues to send data frantically, the receiver can only throw away the received packets. Solution: A large number of packet loss is a great waste of network resources, so you need to control the flow. Let the sender send speed is not too fast, so that the receiver has time to receive processing. Issues between sender and receiver, point to point.
Principle: The sending rate of the sender is controlled by acknowledging the Window field in the packet. The Window field tells the sender the size of the data that can be sent next time. The unit is byte. The size of the sending window on the sender must not exceed the size of the window given by the receiver. When the sender receives the receive window size of 0, the sender will stop sending data.
Special case: Initially, the receiver sends the segment of window 0 to the sender. Later, the receiver has some more storage space, and the segment of the non-0 window sent to the sender is lost. The sender’s send window is always 0, and the two sides are locked in an impasse. Solution: When the sender receives the 0 window notification, the sender stops sending packets. At the same time, a timer is started to send a test message to ask the receiver about the latest window size. If the received window size is still 0, the sender refreshes the start timer again.
Congestion control: prevents excessive data injection into the network. Avoid router or link overload on the network. Congestion control is a global process that involves all hosts, routers, and other factors associated with degrading network traffic performance. In contrast, flow control is the control of point-to-point communication.
Congestion control methods: Slow strart, congestion avoidance, fast retransmit, and fast recovery.
MSS, Maximum Segment Size: Indicates the Maximum Segment Size of each Segment, which is determined when the connection is established. CWND, congestion window: Congestion window. RWND, receive window: indicates the receive window. SWND, send window: indicates the sending window. It is the minimum of the congestion window and the receiving window. SWND = min(CWND, RWND).
Slow start: The initial value of the CWND is small, and then the CWND grows exponentially as the packet is acknowledged and ACK is received by the receiver.
Congestion avoidance: SSthresh, sow start threshold, slow start threshold. After CWND reaches the threshold, it increases in a linear way. The congestion window increases slowly with addition to prevent premature network congestion. When the increase reaches a certain level, the network is congested. At this time, it is necessary to use multiplication to reduce the ssthresh by half. Later, the old and new versions are treated differently. In the old version, the slow start algorithm is executed simultaneously and CWND is restored to its original value. In the new version, quick recovery will be used and the threshold will be added up instead of going back to the original value. When network congestion occurs frequently, the SSthRESH value decreases quickly.
How do I know network congestion? When the sender receives three consecutive double acknowledgments indicating network congestion, the multiplication reduction algorithm is performed to halve SSthresh. The difference from slow start is that the slow start algorithm is not executed, that is, CWND does not revert to its initial value, but instead sets the CWND value to the value after ssthresh is halved. Then the congestion avoidance algorithm is implemented, and the addition increases, making the congestion window grow slowly and linearly.
Connection management: establish connection, three handshake, release connection, four wave. Three-way handshake: The client sends SYN=1 and ACK=0 to the server. The server replies to TCP SYN=1 and ACK=1. The client replies with SYN=0 and ACK=1. In the previous two cases, SYN is 1.
The sequence number is the number of bytes of the currently sent packet. ACK is to tell the other party from which number to send. The actual value sent is the original value and the relative value is calculated.
The first step is to send seq= S1 and ACK =0 to the server. S1 is the random value generated by the client. In the second step, the server responds seq=s2 and ACK = S1 +1 to the client. S2 is a random value generated by the server. Ack confirms the previous step sent by the client and also tells the client the serial number of the next send. In the third step, the client sends seq=s1+1, ACK = S2 +1 to the server, and the data length is 0. The connection is established. In the fourth step, the client sends data seq=s1+1 and ACK =s2+1 to the server. Different from the third step, there is data length K, which is the second step of the reply, so seQ and ACK are the same. Fifth, the server sends data M1, M2, M3 to the client. Send M1 data seq=s2+1, ACK = S1 + K +1, data length b1. Send M2 data seq=s2+b1+1,ack= S1 + K +1, data length B2. Send M3 data seq= S2 + B1 + B2 +1, ACK = S1 + K +1, data length B3. Step 6: The client sends SEq =s1+ K +1, ACK = S2 + B1 + B2 + B3 +1. The client ACK acknowledges the last server transmission. The last server SEQ + data length is B3 +1.
TCP- Establish connection – Status: The Client is in the Closed state and the Server is in the Listen state, waiting for the Client to connect. The client initiates connection requests SYN=1,ACK=0, and SEq =x. Then the client enters the SYN-sent state. The server receives the connection request from the client and enters the syn-RCVD state. The server sends a connection request to the client acknowledging SYN=1, relative ACK=1, SEq =y, and real ACK= x+1. The client receives the acknowledgement from the server and sends ACK=1, SEq =x+1, ACK= y+1 to the server. The client enters the established state. The server receives the acknowledgement and enters the established state.
The first two handshakes to establish a connection: THE SYN is 1, and the TCP header is typically 32 bytes long. The length of the data section is 0 the first three times. The TCP header is fixed at 20 bytes and the options section at 12 bytes. The first two handshakes are exchanged to confirm information such as MSS, whether SACK is supported, Window scale, etc. This data is placed in the options section of the TCP header in 12 bytes.
Why three handshakes? Why not two? The three main purposes are to prevent the server from waiting and wasting resources. If only two handshakes are needed to establish a connection, the following situation may occur: If the client does not receive a reply to the connection request segment 1 sent by the client due to network delay, request 1 is invalid and a new connection request is sent. The connection is established, data is sent, and connection 2 is released. Connection request 1 does not reach the server until some time after the connection is released. The server receives invalid connection 1 and mistakenly thinks that the client resends a new connection request. Therefore, the server sends an acknowledgement packet to the client to agree to establish a connection. If the three-way handshake is not used, a new connection is established as soon as the server sends an acknowledgement. Since the client does not want to connect to the server, it does not respond to the server’s acknowledgement and does not send data to the server. However, the server thinks that a new connection has been established and waits for the client to send data, thus wasting the server’s resources.
By using a three-way handshake, you can prevent this from happening. The client does not send an acknowledgement to the server, and the server does not receive an acknowledgement, so it knows that the client did not ask for a connection.
If the third handshake fails, what happens: The state of the server is SYN-RCvd. If the SERVER cannot wait for the ACK of the client, the server resends SYN=1 and ACK=1 packets. If the server sends SYN=1 and ACK=1 packets multiple times without waiting for an ACK from the client, it sends an RST packet, forcing the connection to close.
TCP releases the connection with four waves:
The difference between a long connection and a short connection is as follows: For example, a socket is closed immediately after a connection is established. A long link is a close after a certain period of time.
Application layer: FTP, HTTP, and DNS. Packets, user data.
Domain Name: The IP address is not easy to remember and cannot express the Name and nature of the organization. Ultimately, you need to know the IP address of the destination host. Why not directly use the domain name instead of the IP address? The IP address is fixed with 4 bytes. The domain name occupies a lot of data, wastes traffic, and increases the burden of the router. By Domain level: Specifies top-level domains (TLD) and top-level domains. Secondary domain name.
General top-level Domain, gTLD:.com companies,.net network organizations,.org organizations,.edu education,.gov government departments,.int international organizations, etc. Country Code Top-level Domain, ccTLD:.cn China,.jp Japan,.uk New Generic top-level Domain, New gTLD:.vip,.xyz,.top,.club,.shop Second level Domain: Domain name under the top-level Domain. Under a GENERIC top-level domain name, it refers to the name of the domain name registrant, for example, Google or Baidu. The domain name Baidu.com is composed of the top-level domain name and the secondary domain name. Baidu is a second-level domain name, and.com is a top-level domain name. From right to left, the first is the top-level domain, the second. Is the second level domain name, in turn three levels four.
DNS, Domain Name System: Uses the DNS protocol to resolve Domain names into corresponding IP addresses. DNS can be based on UDP or TCP. The DNS server occupies port 53.
Ipconfig/displayDNS: View DNS cache records ipconfig/flushDNS: clear DNS cache records ping domain name nslookup domain name
DNS server: Access www.baidu.com. The client accesses the nearest DNS server (the DNS server configured by the client). Then the DNS server requests the root DNS server, which returns the IP address of the DNS server corresponding to the top-level domain name, including the IP address of.com. Then the nearest DNS server sends a request to the root DNS server and returns the IP address of the DNS server where baidu.com resides and the IP address of the secondary DNS server. The latest DNS server sends a request to the secondary DNS server to obtain the IP address corresponding to Baidu.com.
The IP address of the ROOT DNS server is recorded on all DNS servers. The upper-level DNS server records the IP address of the lower-level DNS server. There are 13 IPv4 DNS root servers and 25 IPv6 DNS root servers in the world.
IP addresses can be assigned in static or dynamic modes. Dynamic IP address: Automatically obtains an IP address from the DHCP server. Mobile devices, infinite devices, etc.
Dynamic Host Configuration Protocol Dynamic Host Configuration Protocol Based on UDP, the client port is 68 and the server port is 67. The DHCP server selects an IP address from the IP address pool and gives it to the client for a period of time. Your home’s Internet router acts as a DHCP server.
DHCP allocates IP addresses in four stages: Discover, discover the server. To send a broadcast packet, the source IP address is 0.0.0.0, the target IP address is 255.255.255.255, and the target MAC address is FF:FF:FF:FF:FF. Offer a lease. The server returns the leased IP address, subnet mask, gateway, and DNS information. There may be multiple servers that provide leases; Request: Select an IP address. The client selects an offer and sends a broadcast packet in response. A. ackNowledge B. ackNowledge The selected server sends ACK packets to the client, and the IP address assignment is complete.
Can the DHCP server assign IP addresses across network segments? If the DHCP server and client are on different network segments, the DHCP Relay Agent can be used to assign IP addresses across network segments.
Automatic renewal: When the lease expires, the client automatically sends a Request message to the DHCP server to renew the lease. Ipconfig /all: displays detailed DHCP information, such as lease expiration time and DHCP server address. Ipconfig /release: releases the lease. Ipconfig /renew: apply for a new IP address or renew the lease.
HTTP, Hyper Text Transfer Protocol. Originally used to publish and receive HTML, using URIs to identify specific resources. HTML, Hyper Text Markup Language
HTTP/0.9 in 1991 only supported GET to GET HTML text data. 1996 HTTP/1.0 support POST, HEAD and other requests, support request headers, response headers, support more types of data, no longer limited to text data, and each request browser needs to establish a TCP connection with the server, request processing immediately disconnect the TCP connection. 1997 HTTP/1.1, the most classic, the most widely used version, support PUT, DELETE and other request modes, using a persistent Connection Connection: keep-alive, multiple requests can share the same TCP Connection. HTTP/2.0 in 2015 HTTP/3.0 in 2018
HTTP standard RFC. Request For Comments. Use the ABNF language to describe the HTTP request format. Message format: 0A line feed CR, 0D Carriage return LF, 20 Spaces.
Request line -> Request header -> Request body.
GET: Usually used for reading operations. Request parameters are directly concatenated after the URL. The browser or server will limit the length of the URL. POST: Is used to add, modify, and delete operations. Request parameters can be placed in the body of the request. There is no size limit. HEAD: The request gets the same response as the GET request, but no body. Usage scenario: Before downloading a large file, obtain its size and decide whether to download it. This can save bandwidth resources. OPTIONS: Used to get the communication OPTIONS supported by the server (destination resource), such as the request methods supported by the server. The OPTIONS * HTTP / 1.1.
PUT: Covers all existing resources. PATCH: Partially modifies the resource. If the resource does not exist, a new resource is created. DELETE: Deletes the specified resource. TRACE: The request server echoes the received request information. It is used for TESTING or diagnosing HTTP requests. CONNECT: enables a bidirectional communication channel between the client and the requested resource. The tunnel can be used to create a tunnel. The tunnel can be used to access sites that use SSL or HTTPS.
There are four types of Header fields: Request Header Fields, Response Header Fields, Entity Header Fields, and General Header Fields. The entity header field and the generic header field are included in the request header and response header fields.
Request Header Fields: user-agent The identity string of the browser. Host Specifies the domain name and port number of the server. Date Indicates the Date and time when the message was sent. Content-type Specifies the Type of the request body. Content-length Specifies the Length of the request body, in bytes. Referer: Represents the previous page visited by the browser. That is, this page from which page click jump over, can be used to prevent the chain, to prevent the picture chain; Content-types, Accept: text/plain; Accept-charset Specifies the accepted character set. Accept-charset: GB2312, UTF-8; Q = 0.7 *; Q =0.7 is separated by commas (,). Q is the weight priority. If no value is set, it is 1.0. Accept-encoding Specifies the list of Encoding modes that can be accepted. Accept-encoding: gzip, deflate; Accept-language A list of natural Language responses that can be accepted, accept-language: en-us; Range: bytes=500-900, multithreaded breakpoint download; Connection The type of Connection the browser wants to use preferentially. Connection: keep-alive;
Response Header Fields: Date Date and time when the message was sent. Server Specifies the name of the Server. Content-type Specifies the Type of the response body. Content-type: text/ HTML; Charset = utf-8; Content-encoding Specifies the Encoding type of the Content. Content-encoding: gzip; content-encoding: gzip; Content-length Specifies the Length of the response body, in bytes. Content-length: 348. Content-disposition: Attachment; content-disposition: attachment; content-disposition: attachment; content-disposition: attachment; content-disposition: attachment; content-disposition: attachment; Filename = “fname. JPG”; Connection The option expected for the Connection. Connection: close;
Status codes are classified into five categories: message response 100 199, successful response 200 299, redirection 300 399, client error 400 499, and server error 500 to 599.
100 Continue: The server determines whether to accept the request based on the request header. The client sends the request header first. The server determines whether to receive the request and returns 100 Continue. 200 OK: The request succeeds. 302 Found: Redirect. The requested resource was temporarily moved to the URL specified by the Location header. 304 Not Modified: Content that does Not need to be transferred again, i.e. content that can be cached. 400 Bad Request: The server cannot understand this Request because the syntax is invalid. 401 Unauthorized: There is no authentication credentials required by the target resource. 403 Forbidden: The server has the capability to process the request, but denies access authorization. 404 Not Found: The server could Not find the requested resource. 405 Method Not Allowed: The server disables requests that use the current HTTP Method. 406 Not Acceptable: The server cannot provide responses that match the values specified in accept-charset and accept-language.
500 Internal Server Error: The requested Server encountered an unexpected condition and prevented it from executing the request. 501 Not Implemented: The requested method is Not supported by the server and therefore cannot be processed. The server must support only the GET and HEAD methods. Only the GET and HEAD methods do Not return the status code. Bad Gateway: The server acting as a Gateway or proxy receives an invalid response from the upstream server. 503 Service Unavailable: The server is not yet in a state to accept requests because the server is down for maintenance or is overloaded.
Form submission, common attributes: action, request URI; Method, request method, GET, POST; Enctype, the encoding method of request body in POST request, there are application/ X-www-form-urlencoded default values, & will be used to separate parameters, = will be used to separate keys and values, characters will be used to encode urlencoded. Content-type :multipart/form-data; content-type :multipart/form-data; Boundary =, request becomes complicated;
The emergence of cross-domain issues solves the problem of not allowing any request source to access server resources for security purposes.
The Origin in the request header and the access-control-allow-Origin in the response header are used across domains: The browser has the same-origin Policy. By default, AJAX asynchronous requests can only send urls of the Same Origin. The Same Origin indicates the Same protocol, domain name /IP address, and port. Tags such as img, script, link, iframe, video, and audio are not affected by the same origin policy.
Common methods to solve AJAX cross-domain requests: CORS, cross-origin Resource Sharing, cross-domain Resource Sharing. The implementation of CORS requires both client and server support. Client all browsers are supported, IE10 above. The server needs to return the response header access-control-allow-Origin to tell the browser that the request allows cross-domain Access. That is, specify which source websites can Access the resource across domains. Access-control-allow-origin: *. The request header Origin: tells the server what the source of the request I initiated is, Origin:www.baidu.com. The backend can further determine whether the request can cross domains.
Cookie in request header and set-cookie in response header: HTTP is stateless. Each request is independent and there is no way to tell if each request is from the same browser. The Cookie and the session are used together, the Cookie is stored in the browser, the session is stored on the server. Set-Cookie: JSESSIONID=; Cookies are cleared when the browser is closed or time is up. If there is no JSESSIONID in the request, the server will create a new Session object. If there is a JSESSIONID, the server will obtain the Session object directly. If the requested cookie data server determines that there is a problem, it can return 302 and redirect the Location to the login page.
Proxy Server: forwards requests and responses from the downstream Server and the upstream client. Forward proxy: The proxy object is the client. Reverse proxy: The proxy object is the server. The forward proxy function: hides the client identity, bypasses the firewall, controls the access permission, and filters data. Packet capture tools such as Fiddler and Charles enable the forward proxy service on the client. Reverse proxy: hides server identity, protects security, and balances load.
Wireshark works as follows: The Wireshark uses the underlying driver to intercept data flowing through network adapters.
Network security: intercept, interrupt, tamper, forge. ARP spoofing at the network layer, including DoS attacks and denial-of-service attacks Denial-of-service attacks: Network or system resources of the target computer are exhausted, and services are interrupted or stopped temporarily. As a result, other normal users cannot access the device. DDoS attack, Distributed denial-of-service attack, or Distributed denial-of-service attack: Hackers use two or more compromised computers on a network as zombies or broilers to launch DoS attacks against specific targets.
DoS attacks are classified into two types: bandwidth-consuming: UDP flood attacks and ICMP flood attacks. Resource wasting: SYN flood attack and LAND attack. SYN flood attack: The attacker sends a series of SYN requests to the target, and then makes the target wait and consume resources because the third ACK handshake cannot be received. LAND attack:.
Defense Mode Firewall: Set rules to deny specific communication protocols, ports, or IP addresses. The communication from the attack source IP address is denied. The firewall is in the back, so the malicious attack traffic is attacked before it reaches the firewall.
Application-layer DNS hijacking: Tampering with domain name resolution results. Use the reliable DNS server 114.114.114.114. HTTP hijacking: Interception of HTTP packets, such as inserting JS code and inexplicably appearing pop-up ads.
Security problems of THE HTTP protocol: The plaintext transmission has great security risks. Method to improve security: Encrypt the communication before transmission.
Encrypt encrypts, decrypt decrypts, plainText Plaintext, and cipherText ciphertext. One-way hash function: Calculates the hash value based on the message content. The length of the hash value is independent of the length of the message, no matter how big the message is 10M or 100G, the fixed length hash value can be calculated. One way irreversible. Also known as message Digest function, hash function. The output hash value is also called message digest, or fingerprint.
Application of one-way hash function: prevent data from being tampered; The password is encrypted.
AES, Advanced Encryption Standard: indicates the symmetric Encryption algorithm that replaces DES. The value can be 128 bits, 192 bits, or 256 bits.
How to solve the symmetric secret key distribution problem: share the secret key in advance; Key distribution center; Asymmetric Cryptography;
Asymmetric Cryptography Asymmetric Cryptography: Public key, private key. Encryption and decryption speed is slow. Are: the RSA.
A and B send messages. A sends its public key to B, and B sends its public key to A. When A sends A message to B, it encrypts the message with its own private key. After RECEIVING the message, B uses the public key delivered by A to decrypt it. The message may be obtained by others, but cannot be tampered with. B sends A message to A using B’s own private key.
Hybrid cryptosystem: a combination of symmetric and asymmetric encryption. Why to use the combination: Asymmetric encryption efficiency is not high, relatively slow, but secure, symmetric encryption is fast, but not secure, so use the combination.
Session key: a temporary symmetric secret key randomly generated for a communication. It is used to encrypt messages. The symmetric secret key increases speed.
Asymmetric encryption steps: First, the message sender gets the message receiver’s public key. Then the session key is generated, the symmetric key is generated, and the message is encrypted. Encrypts the session key with the message receiver’s public key. Send the previously generated encrypted message along with the public key encrypted session key to the message receiver. Decryption procedure: The message receiver uses the public key to decrypt the session key, and then uses the session key to decrypt the encrypted message.
Question: How does the message receiver determine the authenticity of the message and identify tampering, masquerading, and denial? Solution: Digital signature.
Since it’s encrypted, I don’t want anyone to know my message, so only I can decrypt it. The public key is responsible for encryption and the private key for decryption.
Digital signature process: Generate the signature: The message sender generates the signature using the signature key/private key. Verification signature: The message receiver is authenticated by authentication key/Public key. How do I ensure that this signature is signed by the message sender? Sign with the message sender’s private key.
The process of digital signature: Message sender A uses its private key to encrypt the message digest, the encrypted content is the signature, and sends the message, signature, and public key to message receiver B. Message receiver B obtains the message, obtains the message digest, uses A’s public key to decrypt the signature, and then compares the digest to check whether it is the same. Signing addresses the issues of confirming the integrity of the message, identifying whether the message has been tampered with, and preventing denial by the message sender. In digital signature, anyone can use the public key to verify the signature.
Asymmetrically encrypt the message digest rather than directly encrypt the message.
Since it’s a signature, I don’t want anyone to impersonate me to send messages, so only I can sign. The private key signs and the public key checks.
The legitimacy of public key in asymmetric encryption: the public key may be forged due to man-in-the-middle attack. Solution: Certificate Certificate. Public-key Certificate, PKC, similar to a driver’s license. Contains personal information such as name, email address, and public key. The Certificate Authority and CA add the digital signature and use the CA’s private key to add the digital signature.
A CA is a person or organization that can determine that the public key really belongs to this person and can generate a digital signature.
The process of using a certificate is as follows: message receiver B generates a secret key pair, registers its public key with the CA, and then the CA uses its private key to digitally sign B’s public key and generates a certificate. Message sender A obtains A certificate from the CA, with A digital signature and B’s public key. User A uses the CA’s public key to verify the digital signature and verify the validity of user B’s public key. Then A uses B’s public key to encrypt the message and sends it to B. B receives the message and uses its own private key to decrypt it to get A’s message.
Certificate registration and download process: message receiver B, also known as the public key registrar, takes his public key to the CA to register. The CA uses its private key to authenticate B’s public key and generates a certificate. The certificate contains B’s public key, a digital signature generated by the CA, and B’s information. The certificate is stored in the keystore, and message sender A, the certificate user, goes to the keystore to download the certificate.
The CA public key is built into browsers and operating systems by default.
HTTPS, HyperText Transfer Protocol Secure: The default port is 443. SSL/TLS secure sockets layer is added on the basis of HTTP to prevent eavesdropping and man-in-betweenattacks.
TLS, Transport Layer Security, formerly SSL, Secure Sockets Layer. SSL/TLS can also be used for other protocols, such as FTPS and SMTPS. SSL/TLS works between the application layer and transport layer. SSL/TLS is divided into Handshake Layer and Record Layer.
OpenSSL is an open source implementation of the SSL/TLS protocol. You can use OpenSSL to build your own CA, issue your own certificates, and self-sign your own certificates.
To generate a public key, run the openssl rsa -in my.key -pubout -out my.pem command
The HTTPS communication process is divided into three stages: 1, TCP three-way handshake 2, TLS connection 3, HTTP request and response
HTTP is a plaintext transmission. HTTP->TLS/SSL->TCP->IP HTTPS can prevent information eavesdropping, tampering, and hijacking, and can encrypt, verify integrity, and authenticate information. HTTPS Standard port 443. HTTPS is the basic transport layer. HTTP is based on the application layer.
HTTPS encrypts data and establishes an information security channel to ensure data security during transmission. Real identity authentication for the website server;
TCP: Is a connection-oriented, reliable byte stream service. Establishing a TCP connection requires a three-way handshake. Reliable basis is to provide: timeout resend, discarded duplicate data, check data, flow control, ensure that data can be from one end to the other. UDP: User datagram Protocol (UDP), a transport layer protocol for datagrams. Connectionless protocol that sends packets directly without establishing a connection with the other party. There is no need to establish a connection, little data transfer, no timeout resend mechanism, so the transmission speed is very fast.
TCP three-way handshake: For the first time, the client sends a SYN packet to the server, enters the SYN_SEND state, and waits for the server to confirm. The second time, when the server receives a SYN packet, it must acknowledge the client’s SYN, and ack= J +1. At the same time, it must send a SYN packet, syn=k, that is, A SYN+ACK packet. Then the server enters the SYN_RECV state. On the third attempt, the client receives the SYN+ACK packet from the server and sends an ACK packet (ACK = K +1) to the server. After this packet is sent, the client and server enter the established state and complete the three-way handshake.
Both the client and server can initiate a request to disconnect the TCP connection. Disconnected four waves.
Socket: a set of interfaces that implement TCP and UDP. HTTP is based on sockets. The HTTP protocol is based on TCP links. TCP protocol: corresponds to the transport layer. IP protocol: corresponds to the network layer. TCP/IP mainly solve the data transmission in the network; HTTP is an application-layer protocol that deals with how to wrap data. Socket: is the encapsulation of TCP/IP protocol, Socket is not a protocol, but a call interface, through Socket, we can use TCP/IP protocol.
HTTP connection: a short connection. The client sends a request to the server. The server responds and releases the connection. Socket connection: long connection. After the connection is established between the client and the server, the connection is not broken unless an exception occurs. The network is faulty. No data is transmitted for a long time. The network firewall may be disconnected to release network resources. Therefore, when there is no data transmission in a socket long connection, heartbeat messages need to be sent to maintain the connection.
Socket establishing a network connection: establishing a Socket connection requires a pair of sockets, one running on a ClientSocket and one running on a ServerSocket. First, the server listens. The ServerSocket is in the state of waiting for connection. It monitors the network status in real time and waits for the connection request from the client. Second, the client sends a request and the ClientSocket connects to the ServerSocket. The client must describe the ServerSocket to be connected, including the address and port number. Third, connection confirmation. When the ServerSocket listens for a connection request from the ClientSocket, it responds to the client request by creating a new thread that sends the description of the ServerSocket to the ClientSocket. Once the description is confirmed, the connection is established. The ServerSocket continues to be in the listening state and continues to receive connection requests from other ClientSockets.
Problem: IM software can be online for a long time, or a short time dropped, the best can be user unaware. Keep IM software online. It uses a disconnection reconnection mechanism. Socket programming disconnection reconnection mechanism, GCDAsyncSocket, implementation: IM software can always keep the link with the server as far as possible, the client has logged in to maintain the state, in order to disconnection. From the logical level, the logic of disconnection is based on login logic. After the first successful login, there may be disconnection and reconnection. Step: first, make the client disconnect; Second, reconnect the client to the server.
The client is disconnected and reconnected to the server: The network connection fails, the network is unavailable, and the “Network is available” notification is received from the iOS system. Wifit ->4G/5G; If the heartbeat fails or the heartbeat times out, the connection between the client and the server is damaged or the identity of the current user is changed. After a heartbeat failure, disconnect the client and reconnect the client. This prevents the heartbeat failure and network error events from occurring at the same time, causing two login attempts. The client restarts, and the latest session data cached by the user is loaded in advance. If the background operation of IM software is terminated by the system, switch to the foreground; To avoid repeated login, do not reconnect the client when the network is available or the client is switched to the foreground, and the IM is in the login, connection, or logout state.
Heartbeat: The client periodically sends a signaling packet to the Server to indicate that the client is still alive. Heartbeat termination: 1. The Server disconnects the socket. The Server only receives heartbeat messages from the client. If the Server does not receive the heartbeat message from the client for a long time, the Server considers the client dead and disconnects the Server. In this case, the client may be fake online. 2. If the client disconnects the socket, how often does the client send a heartbeat? If the client sends a heartbeat, the server does not respond for a long time.
The process of remote APNS push is as follows: 1. The client sends the user UUID and app bundleID to the APNS server for registration. ANPS returns the encrypted Device Token to the APP. 2. Upload the app to the company server after obtaining the Device Token; 3. When a push notification is required, the company server will send the pushed content and device Token together to the APNS server; 4. APNS pushes the pushed content to the corresponding client app;
GET generates a TCP packet. POST generates two TCP packets. The browser sends the HTTP header and data together. The server responds with 200(return data). POST: The browser sends a header, the server responds with 100 continue, the browser sends data, and the server responds with 200 OK (return data).