发表于 | 分类于

算法分类

算法分类

算法总结

排序算法 时间复杂度（最好） 时间复杂度（最坏） 时间复杂度（平均） 空间复杂度 稳定性
冒泡排序 O(n) O(n^2) O(n^2) O(1) ✔️
选择排序 O(n^2) O(n^2) O(n^2) O(1) ✘
插入排序 O(n) O(n^2) O(n^2) O(1) ✔️
希尔排序 O(nlogn) O(nlog^2 n) O(nlog^2 n) O(1) ✘
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) ✔️
快速排序 O(nlogn) O(n^2) O(nlogn) O(logn) ✘
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) ✘
桶排序 O(n) O(n^2) O(n) O(n*k) ✔️
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) ✔️
基数排序 O(n*k) O(n*k) O(n*k) O(n+k) ✔️

算法实现

冒泡排序

  • 动图：

    BubbleSort

  • 代码：

    public static void bubbleSort(int [] a) {
    if(a.length <= 1) {
        return;
    }
    for(int i = 0; i < a.length; i++) {
        boolean flag = true; // 提前结束循环标志位
        for(int j = 0; j < a.length-1-i; j++) {
            if(a[j] > a[j+1]) {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = false; // 此次冒泡有数据交换
            }
        }
        if(flag) {
            break;
        }
    }
}

选择排序

  • 动图：

    SelectionSort

  • 代码：

    public static void selectionSort(int [] a) {
    if(a.length <= 1) {
        return;
    }
    for(int i=0; i<n-1; i++) {
        // 查找最小值
        int minIndex = i;
        for(int j = i+1; j < n; j++) {
            if(a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        // 交换
        if(minIndex != i) {
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

插入排序

  • 动图：

    InsertionSort

  • 代码：

    public static void insertionSort(int [] a) {
    if(a.length <= 1) {
        return;
    }

    for (int i = 1; i < arr.length; i++) {
      int value = a[i];
        int j = i - 1;
        // 查找要插入的位置并移动数据
        for (; j >= 0; j--) {
           if (a[j] > value) {
              a[j+1] = a[j];
               } else {
                  break;
            }
      }

      if(j+1 != i) {
              a[j+1] = value;
      }
}

希尔排序

  • 动图：

    ShellSort

  • 代码：

    public static void shellSort(int [] arr) {
    if(arr.length <= 1) {
        return;
    }

    int gap = 1;
    while (gap < arr.length) {
        gap = gap * 3 + 1;
    }

    while (gap > 0) {
        for (int i = gap; i < arr.length; i++) {
           int tmp = arr[i];
           int j = i - gap;
           while (j >= 0 && arr[j] > tmp) {
                arr[j + gap] = arr[j];
                j -= gap;
           }
           arr[j + gap] = tmp;
        }
        gap = (int) Math.floor(gap / 3);
    }
}

归并排序

  • 动图：

    MergeSort

  • 代码：

    // 归并排序算法, a是数组，n表示数组大小
public static void mergeSort(int[] a, int n) {
    mergeSortInternally(a, 0, n-1);
}

// 递归调用函数
private static void mergeSortInternally(int[] a, int p, int r) {
    // 递归终止条件
    if (p >= r) return;

    // 取p到r之间的中间位置q,防止（p+r）的和超过int类型最大值
    int q = p + (r - p)/2;
    // 分治递归
    mergeSortInternally(a, p, q);
    mergeSortInternally(a, q+1, r);

    // 将A[p...q]和A[q+1...r]合并为A[p...r]
    merge(a, p, q, r);
}

private static void merge(int[] a, int p, int q, int r) {
    int i = p;
    int j = q+1;
    int k = 0; // 初始化变量i, j, k
    int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
    while (i<=q && j<=r) {
        if (a[i] <= a[j]) {
        tmp[k++] = a[i++]; // i++等于i:=i+1
        } else {
            tmp[k++] = a[j++];
        }
    }

    // 判断哪个子数组中有剩余的数据
    int start = i;
    int end = q;
    if (j <= r) {
        start = j;
        end = r;
    }

    // 将剩余的数据拷贝到临时数组tmp
    while (start <= end) {
        tmp[k++] = a[start++];
    }

    // 将tmp中的数组拷贝回a[p...r]
    for (i = 0; i <= r-p; ++i) {
        a[p+i] = tmp[i];
    }
}

快速排序

  • 动图：

    QuickSort

  • 代码：

    // 快速排序，a是数组，n表示数组的大小
public static void quickSort(int[] a, int n) {
    quickSortInternally(a, 0, n-1);
}

// 快速排序递归函数，p,r为下标
private static void quickSortInternally(int[] a, int p, int r) {
    if (p >= r) return;

    int q = partition(a, p, r); // 获取分区点
    quickSortInternally(a, p, q-1);
    quickSortInternally(a, q+1, r);
}

private static int partition(int[] a, int p, int r) {
    int pivot = a[r];
    int i = p;
    for(int j = p; j < r; ++j) {
        if (a[j] < pivot) {
            if (i == j) {
                ++i;
            } else {
                int tmp = a[i];
                a[i++] = a[j];
                a[j] = tmp;
            }
        }
    }

    int tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;

    System.out.println("i=" + i);
    return i;
}

堆排序

  • 动图：

    HeapSort

  • 代码：

    public class HeapSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        buildMaxHeap(arr, len);

        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

桶排序

  • 动图：

    BucketSort

  • 代码：

     public class BucketSort implements IArraySort {

     private static final InsertSort insertSort = new InsertSort();

     @Override
     public int[] sort(int[] sourceArray) throws Exception {
         // 对 arr 进行拷贝，不改变参数内容
         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

       // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    // 自动扩容，并保存数据
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

计数排序

  • 动图：

    CountingSort

  • 代码：

    public class CountingSort {

  // 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
  public static void countingSort(int[] a, int n) {
    if (n <= 1) return;

    // 查找数组中数据的范围
    int max = a[0];
    for (int i = 1; i < n; ++i) {
      if (max < a[i]) {
        max = a[i];
      }
    }

    // 申请一个计数数组c，下标大小[0,max]
    int[] c = new int[max + 1];
    for (int i = 0; i < max + 1; ++i) {
      c[i] = 0;
    }

    // 计算每个元素的个数，放入c中
    for (int i = 0; i < n; ++i) {
      c[a[i]]++;
    }

    // 依次累加
    for (int i = 1; i < max + 1; ++i) {
      c[i] = c[i-1] + c[i];
    }

    // 临时数组r，存储排序之后的结果
    int[] r = new int[n];
    // 计算排序的关键步骤了，有点难理解
    for (int i = n - 1; i >= 0; --i) {
      int index = c[a[i]]-1;
      r[index] = a[i];
      c[a[i]]--;
    }

    // 将结果拷贝会a数组
    for (int i = 0; i < n; ++i) {
      a[i] = r[i];
    }
  }

}

基数排序

  • 动图：

    Radix

  • 代码：

     public class RadixSort implements IArraySort {

     @Override
     public int[] sort(int[] sourceArray) throws Exception {
         // 对 arr 进行拷贝，不改变参数内容
         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

         int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    // 获取最高位数
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

   protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

发表于 | 分类于

单链表反转

来源：

迭代版：

class solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;

        while(cur != null) {
            next = cur.next;
            cur.next = pre; // 从前往后
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

递归版：

class solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head; // 从后往前
        head.next = null;
        return newHead;
    }
}

链表中环的检测

来源：

哈希表：

class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodesSeen = new HashSet<ListNode> ();
        while(head != null) {
            if(nodesSeen.contains(head)) {
                retrun true;
            } else {
                nodesSeen.add(head);
            }
            head = head.next;
        }
        return false;
    }
}

双指针：

class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;

        while(slow != fast) {
            if(fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        retrun true;
    }
}

两个有序的链表合并

来源：

一般写法：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(-1);
        ListNode current = result;

        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = (l1 != null) ? l1 : l2;
        return result.next;
    }
}

递归版本（一）：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

递归版本（二）：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode head = (l1.val < l2.val) ? l1 : l2;
        ListNode nonhead = (l1.val < l2.val) ? l2 : l1;
        head.next = mergeTwoLists(head.next, nonhead);
        return head;
    }
}

删除链表倒数第 n 个结点

来源：

双指针：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode left = dummy;
        ListNode right = dummy;

        for(int i=1; i<=n+1; i++) {
            right = right.next;
        }

        while(right != null) {
            right = right.next;
            left = left.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }
}

求链表的中间结点

来源：

快慢指针：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

发表于 | 分类于

1. 常见的缓存淘汰策略有？

答：

  • 先进先出策略 FIFO (First in, First out)。
  • 最少使用策略 LFU (Least Frequently Used)。
  • 最近最少使用策略 LRU (Least Recently Used)。

2. 怎样实现 LRU 缓存淘汰策略？

答：

思路：

  • 维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表。
  • 如果此数据之前已经被缓存在链表中，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
  • 如果此数据没有缓存在链表中，又可以分为两种情况：
    • 如果此时缓存未满，则将此结点直接插入到链表头部。
    • 如果此时缓存已满，则删除链表尾结点，将新的数据结点插入链表的头部。

基于 Array：

import java.util.HashMap;
import java.util.Map;

/**
* 基于数组的 LRU 缓存淘汰算法
* 1. 空间复杂度为 O(n)
* 2. 时间复杂度为 O(n)
* 3. 不支持 null 的缓存
*/
public class LRUBaesArray<T> {
    private static final int DEFAULT_CAPACITY = (1 << 3); // TODO
    private int capacity;
    private int length;
    private T[] elements;

    private Map<T, Integer> holder;

    public LRUBaseArray() {
        this(DEFAULT_CAPACITY);
    }

    public LRUBaseArray(int capacity) {
        this.capacity = capacity;
        elements = (T[]) new Object[capacity];
        length = 0;
        holder = new HashMap<T, Integer> (capacity);
    }

    // 模拟访问某个值
    public void offer(T object) {
        if(object == null) {
            throw new IllegalArgumentException("该缓存容器暂不支持 null");
        }
        Integer index = holder.get(objcet);
        if(index == null) {
            if(isFull()) {
                removeAndCache(object);
            } else {
                cache(object, length);
            }
        } else {
            update(index);
        }
    }

    // 若缓存中有指定的值，则更新位置
    public void update(int end) {
        T target = elements[end];
        rightShift(end);
        elements[0] = target;
        holder.put(target, 0);
    }

    // 先右移，然后缓存数据到头部
    public void cache(T object, int end) {
        rightShift(end);
        elements[0] = object;
        holder.put(object, 0);
        length++;
    }

    // 缓存满的情况，先删除，再缓存到数组头部
    public void removeAndCache(T object) {
        T key = elements[--length];
        holder.remove(key);
        cache(object, length);
    }

    // end 左边的数据统一右移一位
    private void rightShift(int end) {
        for(int i = end - 1; i >= 0; i--) {
            elements[i + 1] = elements[i];
            holder.put(value[i], i + 1);
        }
    }

    public boolean isContain(T object) {
        return holder.containsKey(object);
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public boolean isFull() {
        return length == capacity;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int i=0; i < length; i++) {
            sb.append(elements[i]);
            sb.append(" ");
        }
        return sb.toString();
    }

    static class TestLRUBaseArray {
        public static void main(String[] args) {
            testDefaultConstructor();
            testSpecifiedConstructor(4);
            // testWithException();
        }

        private static void testWithException() {
            LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> ();
            lru.offer(null);
        }

        public static void testDefaultConstructor() {
            System.out.println("======无参测试======");
            LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> ();
            for(int i=1; i  <= 5; i++) {
                lru.offer(i);
            }
            System.out.println(lru);
            for(int i=6; i  <= 9; i++) {
                lru.offer(i);
            }
            System.out.println(lru);
        }

        public static void testSpecifiedConstructor(int capacity) {
            System.out.println("======有参测试======");
            LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> (capacity);
            for(int i=1; i <= 9; i++) {
                lru.offer(i);
            System.out.println(lru);
            }

        }
    }
}

基于 LinkedList：

import java.util.Scanner;

/**
* 基于单链表的 LRU 缓存淘汰算法
*/
public class LRUBaseLinkedList<T> {
    private static final Integer DEFAULT_CAPACITY = 10; // 默认链表容量
    private Node<T> headNode; // 头结点
    private Integer length; // 链表长度
    private Integer capacity; // 链表容量

    public LRUBaseLinkedList() {
        this.headNode = new Node<> ();
        this.capacity = DEFAULT_CAPACITY;
        this.length = 0;
    }

    public LRUBaseLinkedList(Integer capacity) {
        this.headNode = new Node<> ();
        this.capacity = capacity;
        this.length = 0;
    }

    public void add(T element) {
        Node preNode = findPreNode(element);

        if(preNode != null) { // 链表中存在，删除原数据，再插入到链表的头部
            deleteNextElemAt(preNode);
            insertElemAtBegin(element);
        } else {
            if(length >= this.capacity) {
                deleteElemAtEnd(); // 删除尾结点
            }
            insertElemAtBegin(element);
        }
    }

    // 删除 preNode 的下一个结点
    private void deleteNextElemAt(Node preNode) {
        Node temp = preNode.getNext();
        preNode.setNext(temp.getNext());
        temp = null;
        length--;
    }

    // 在链表头部插入结点
    private void insertElemAtBegin(T element) {
        Node next = head.getNext();
        headNode.setNext(new Node(element, next));
        length++;
    }

    // 获取参数结点的前一个结点
    private Node findPreNode(T element) {
        Node node = headNode;
        while(node.getNext() != null) {
            if(element.equals(node.getNext().getElement())) {
                return node;
            }
            node = node.getNext();
        }
        return null;
    }

    // 删除尾结点
    private void deleteElemAtEnd() {
        Node node = headNode;
        // 空链表直接返回
        if(node.getNext() == null) {
            return;
        }

        // 定位到倒数第二个结点
        while(node.getNext().getNext() != null) {
            node = node.getNext();
        }

        Node temp = node.getNext();
        node.setNext(null);
        temp = null;
        length--;
    }

    private void printAll() {
        Node node = headNode.getNext();
        while(node != null) {
            System.out.print(node.getElement() + ", ");
            node = node.getNext();
        }
        System.out.println();
    }

    public class Node<T> {
        private T element;
        private Node next;

        public Node() {
            this.next = null;
        }

        public Node(T element) {
            this.element = element;
        }

        public Node(T element, Node next) {
            this.element = element;
            this.next = next;
        }

        public T getElement() {
            return element;
        }

        public void setElement(T element) {
            this.element = element;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LRUBaseLinkedList list = new LRUBaseLinkedList();
        Scanner in = new Scanner(System.in);
        while(true) {
            list.add(in.nextInt());
            list.printAll();
        }
    }
}

基于 LinkedHashMap：

// 参考站内博客：《Java Map 和 Set （六）：剖析 LinkedHashMap》之问题 11
public class LRUBaseLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    private int maxEntries;

    // 在构造方法中传递一个容量限制
    public LRUBaseLinkedHashMap(int maxEntries) {
        super(16, 0.75f, true);
        this.maxEntryies = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return size() > maxEntries;
    }
}

// 使用这个缓存容器
LRUBaseLinkedHashMap<String, Object> cache = new LRUBaseLinkedHashMap<> (3);
cache.put("a", "abstract");
cache.put("b", "basic");
cache.put("c", "call");
cache.put("a");
cache.put("d", "call");
System.out.print(cache);

// 因为限定缓存容量为 3， 这里先后添加了 4 个键值对
// 最久没被访问（最近最少使用）的键是 b，会被删除。所以，输出为：{c=call a=abstract, d=call}

3. 如果字符串是通过单链表存储的，怎样判断给定字符串是不是回文字符串？

答：

// TODO: confirmed it by Zheng
// 1）单链表的插入、删除、查找操作；
// 2）链表中存储的是int类型的数据；
public class SinglyLinkedList {
    private Node head = null;

    public Node findByValue(int value) {
        Node p = head;
        while (p != null && p.data != value) {
            p = p.next;
        }
        return p;
    }

    public Node findByIndex(int index) {
        Node p = head;
        int pos = 0;
        while (p != null && pos != index) {
            p = p.next;
            ++pos;
        }
        return p;
    }

    //无头结点
    //表头部插入
    //这种操作将于输入的顺序相反，逆序
    public void insertToHead(int value) {
        Node newNode = new Node(value, null);
        insertToHead(newNode);
    }

    public void insertToHead(Node newNode) {
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    //顺序插入
    //链表尾部插入
    public void insertTail(int value){
        Node newNode = new Node(value, null);
        //空链表，可以插入新节点作为head，也可以不操作
        if (head == null){
            head = newNode;

        }else{
            Node q = head;
            while(q.next != null){
                q = q.next;
            }
            newNode.next = q.next;
            q.next = newNode;
        }
    }

    public void insertAfter(Node p, int value) {
        Node newNode = new Node(value, null);
        insertAfter(p, newNode);
    }

    public void insertAfter(Node p, Node newNode) {
        if (p == null) return;

        newNode.next = p.next;
        p.next = newNode;
    }

    public void insertBefore(Node p, int value) {
        Node newNode = new Node(value, null);
        insertBefore(p, newNode);
    }

    public void insertBefore(Node p, Node newNode) {
        if (p == null) return;
        if (head == p) {
            insertToHead(newNode);
            return;
        }

        Node q = head;
        while (q != null && q.next != p) {
            q = q.next;
        }

        if (q == null) {
            return;
        }

        newNode.next = p;
        q.next = newNode;
    }

    public void deleteByNode(Node p) {
        if (p == null || head == null) return;

        if (p == head) {
            head = head.next;
            return;
        }

        Node q = head;
        while (q != null && q.next != p) {
            q = q.next;
        }

        if (q == null) {
            return;
        }

        q.next = q.next.next;
    }

    public void deleteByValue(int value) {
        if (head == null) return;

        Node p = head;
        Node q = null;
        while (p != null && p.data != value) {
            q = p;
            p = p.next;
        }

        if (p == null) return;

        if (q == null) {
            head = head.next;
        } else {
            q.next = q.next.next;
        }

        // 可重复删除指定value的代码
        /*
           if (head != null && head.data == value) {
               head = head.next;
           }
           Node pNode = head;
           while (pNode != null) {
               if (pNode.next.data == data) {
               pNode.next = pNode.next.next;
               continue;
           }
           pNode = pNode.next;
           }
         */
    }

    public void printAll() {
        Node p = head;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    //判断true or false
    public boolean TFResult(Node left, Node right){
        Node l = left;
        Node r = right;

        System.out.println("left_:"+l.data);
        System.out.println("right_:"+r.data);
        while(l != null && r != null){
           if (l.data == r.data){
               l = l.next;
               r = r.next;
               continue;
           }else{
               break;
           }
        }

        System.out.println("什么结果");
        if (l==null && r==null){
           System.out.println("什么结果");
           return true;
        }else{
           return false;
        }
    }

    //判断是否为回文 
    public boolean palindrome(){
       if (head == null){
           return false;
       } else {
           System.out.println("开始执行找到中间节点");
           Node p = head;
           Node q = head;
           if (p.next == null){
               System.out.println("只有一个元素");
               return true;
           }
           while( q.next != null && q.next.next != null){
               p = p.next;
               q = q.next.next;

           }

           System.out.println("中间节点" + p.data);
           System.out.println("开始执行奇数节点的回文判断");
           Node leftLink = null;
           Node rightLink = null;
           if(q.next == null) {
               // p一定为整个链表的中点，且节点数目为奇数
               rightLink = p.next;
               leftLink = inverseLinkList(p).next;
               System.out.println("左边第一个节点"+leftLink.data);
               System.out.println("右边第一个节点"+rightLink.data);
           } else {
               //p、q均为中点
               rightLink = p.next;
               leftLink = inverseLinkList(p);
           }
           return TFResult(leftLink, rightLink);
        }
    }

    //带结点的链表翻转
    public Node inverseLinkList_head(Node p){
        //　Head　为新建的一个头结点
        Node Head = new Node(9999,null);
        // p　为原来整个链表的头结点,现在Head指向　整个链表
        Head.next = p;
        /*
        带头结点的链表翻转等价于
        从第二个元素开始重新头插法建立链表
        */
        Node Cur = p.next;
        p.next = null;
        Node next = null;

        while(Cur != null){
            next = Cur.next;
            Cur.next = Head.next;
            Head.next = Cur;
            System.out.println("first " + Head.data);

            Cur = next;
        }

        //　返回左半部分的中点之前的那个节点
        //　从此处开始同步像两边比较
        return Head;
    }

    //无头结点的链表翻转
    public Node inverseLinkList(Node p){
        Node pre = null;
        Node r = head;
        System.out.println("z---" + r.data);
        Node next= null;
        while(r !=p){
            next = r.next;

            r.next = pre;
            pre = r;
            r = next;
        }

        r.next = pre;
        //　返回左半部分的中点之前的那个节点
        //　从此处开始同步像两边比较
        return r;

    }

    public static Node createNode(int value) {
        return new Node(value, null);
    }

    public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }

    public static void main(String[]args){
        SinglyLinkedList link = new SinglyLinkedList(); 
        System.out.println("hello");
        //int data[] = {1};
        //int data[] = {1,2};
        //int data[] = {1,2,3,1};
        //int data[] = {1,2,5};
        //int data[] = {1,2,2,1};
       // int data[] = {1,2,5,2,1};
        int data[] = {1,2,5,3,1};

        for(int i =0; i < data.length; i++){
            //link.insertToHead(data[i]);
            link.insertTail(data[i]);
        }

       // link.printAll();
       // Node p = link.inverseLinkList_head(link.head);
       // while(p != null){
       //     System.out.println("aa"+p.data);
       //     p = p.next;
       // }

        System.out.println("打印原始:");
        link.printAll();
        if (link.palindrome()){
            System.out.println("回文");
        }else{
            System.out.println("不是回文");
        }
    }
}

发表于 | 分类于

1. HTTP 概念？

答：

  • HTTP 全称：HyperText Transfer Protocol，即超文本传输协议。
  • 是一种用于分布式、协作式和超文本信息系统的应用层协议，HTTP 是万维网的数据通信的基础。

2. HTTP 历史版本：

答：

  • HTTP 0.9：1991 年发布的第一个版本，只有一个命令 GET，服务器只能回应 HTML 格式的字符串。

  • HTTP 1.0：

    • 1996 年 5 月发布的版本，内容量大大增加。除了 GET 命令，还引入了 POST 命令和 HEAD 命令。HTTP 请求和回应的格式除了数据部分，每次通信都必须包括头信息，用来描述一些元数据。
    • 为了提高系统的效率，HTTP 1.0 规定客户端与服务器只保持短暂的连接，每次请求都要建立一个 TCP 连接，请求处理后立即断开连接，且每次连接都是无记忆的。
    • TCP 连接建立需要三次握手，是很耗费时间的一个过程，所以 HTTP 1.0 的版本较差。

  • HTTP 1.1：

    • 1997 年发布的版本，进一步完善了 HTTP 协议，直到现在还是最流行的版本。
    • 最主要的改进就是引入了持久连接，即 TCP 连接默认不关闭，可以被多个请求复用。
    • 还引入了管道机制（pipelining），即在同一个 TCP 连接里面，客户端可以同时发送多个请求。进一步提高了客户端的效率，但服务端还是要顺序执行的。

    • 图例：

      HTTP 1.1

  • HTTP 2：

    • 2015 年新发布的版本，SPDY 协议的主要特性也在此版本中，SPDY 协议是 2009 年 Google 为了解决 HTTP 1.1 效率不高的问题而自行研发的协议。
    • HTTP 2 采用了多路复用，即在一个连接里，客户端和服务器都可以同时发送多个请求或回应，而且不用按照顺序一一对应。
    • 采用多路复用的前提是 HTTP 2 进行了二进制分帧，即 HTTP 2 会将所有传输的信息分割为更小的消息和帧（frame），并对它们采用二进制格式的编码。这个负责拆分、组装请求和二进制帧的一层就叫做二进制分帧层。
    • 还有一些其他的优化，比如 Header 压缩和服务端推送（服务端提前将信息发送到客户端的缓存）等。

    • 图例：

      HTTP 2

  • HTTP 3：

    • 根据国际互联网工程任务组（The Internet Engineering Task Force，简称 IETF）消息，HTTP-over-QUIC 实验性协议将被命名为 HTTP 3，并有望成为 HTTP 协议的第三个正式版本。
    • QUIC，即：Quick UDP Internet Connections 是 Google 推出的一个项目，旨在降低基于 TCP 通讯的 Web 延迟，QUIC 非常类似 TCP+TLS+SPDY，但是基于 UDP 实现的。
    • HTTP 3 使用 UDP 代替了 TCP，UDP 是一个非连接的协议，传输数据之前源端和终端不建立连接。UDP 信息包的标题很短，对系统资源的要求比 TCP 要低，并且 UDP 是使用最大努力交付，即不保证可靠交付。
    • 这种基于 QUIC 的 HTTP 协议未来发展如何，目前只能拭目以待了。

    • 图例：

      HTTP 3

  • 各版本对比：

    各版本对比

3. HTTP 主要特点？

答：

  • 支持 C/S （客户端/服务器）模式。
  • 简单快速：客户端向服务器请求服务时，只需传送请求方法和路径。请求方法常用的有 GET、HEAD、POST，每种方法规定了客户端与服务器联系的类型不同。由于 HTTP 协议简单，使得 HTTP 服务器的程序规模小，因而通信速度很快。
  • 灵活：HTTP 允许传输任意类型的数据对象。正在传输的类型由 Content-Type 加以标记。
  • 无连接：限制每次连接只处理一个请求。服务器处理完客户端的请求，并受到客户端的应答后，即断开连接。采用这种方式可以节省传输时间。
  • 无状态：HTTP 协议是无状态（stateless）协议，无状态是指协议不回忆前面请求的连接或结果。缺少状态意味着如果后续处理需要前面的信息，则它必须重传，这样可能导致每次连接传送的数据量增大；另一方面，在服务器不需要先前信息时它的应答速度就较快。
  • HTTP URL 的格式：
    • http://host[":"port][abs_path].
    • http 表示要通过 HTTP 协议来定位网络资源；host 表示合法的 Internet 主机域名或者 IP 地址；port 指定一个端口号，为空则使用默认端口 80；abs_path 指定请求资源的 URI（Web 上任意的可用资源）。HTTP 有两种报文，分别是请求报文和相应报文。

4. HTTP 请求报文？

答：

  • 请求报文的一般格式：

    • HTTP 报文是面向文本的，报文中的每个字段都是一些 ASCII 码串，各个字段的长度是不确定的。
    • 一般一个 HTTP 请求报文由请求行、请求报头、空行和请求数据 4 个部分组成。

    • 图例：

      HTTP 请求报文格式

  • 请求行：

    • 请求行由请求方法、URL 字段和 HTTP 协议的版本组成，格式：Method Request-URI HTTP-Version CRLF。
    • Method 表示请求方法；Request-URI 是一个统一资源标识符；HTTP-Version 表示请求的 HTTP 协议版本；CRLF 表示回车和换行（除了作为结尾的 CRLF 外，不允许出现单独的 CR 或 LF 字符）。
    • HTTP 请求方法有 8 种，分别是 GET、POST、HEAD、PUT、DELETE、TRACE、CONNECT、OPTIONS。对于移动开发，最常用的就是 GET 和 POST 了。
      • GET：请求获取 Request-URI 所标识的资源。
      • POST：在 Request-URI 所标识的资源后附加新的数据。
      • HEAD：请求获取由 Request-URI 所标识的资源的响应消息报头。
      • PUT：请求服务器存储一个资源，并用 Request-URI 作为其标识。
      • DELETE：请求服务器删除 Request-URI 所标识的资源。
      • TRACE：请求服务器回送收到的请求信息，主要用于测试或诊断。
      • CONNECT：HTTP 1.1 协议中预留给能够将连接改为管道方式的代理服务器。
      • OPTIONS：请求查询服务器的性能，或者查询与资源相关的选项和需求。

  • 请求报头：

    • 在请求行之后会有 0 个或者多个请求报头，每个请求报头都包含一个字段和一个值，它们之间用英文冒号 : 分隔。

  • 请求数据：

    • 请求数据不在 GET 方法中使用，而在 POST 方法中使用。POST 方法适用于需要用户填写表单的场合，与请求数据相关的最常用的请求报头是 Content-Type 和 Content-Length。

5. HTTP 响应报文？

答：

  • 响应报文的一般格式：

    • HTTP 的响应报文由状态行、响应报头、空行、响应正文组成。
    • 响应正文是服务器返回的资源的内容。

    • 图例：

      HTTP 响应报文格式

  • 状态行：

    • 状态行的格式：HTTP-Version Status-Code Reason-Phrase CRLF。

    • HTTP-Version 表示服务器 HTTP 协议的版本；Status-Code 表示服务器发回的响应状态码；Reason-Phrase 表示状态码的文本描述。状态码由 3 位数字组成，第一个数字定义了响应的类别，后两个数字没有分类的作用。状态码有以下 5 种可能取值：

      • 100~199：指示信息，收到请求，需要请求者继续执行操作。
      • 200~299：请求成功，请求已被成功接收并处理。
      • 300~399：重定向，要完成请求必须进行更进一步的操作。
      • 400~499：客户端错误，请求有语法错误或请求无法实现。
      • 500~599：服务器错误，服务器不能实现合法的请求。

    • 常见的状态码如下：

      • 200 OK：客户端请求成功。
      • 400 Bad Request：客户端请求有语法错误，服务器无法理解。
      • 401 Unauthorized：请求未经授权，这个状态码必须和 WWW-Authenticate 报头域一起使用。
      • 403 Forbidden：服务器收到请求，但是拒绝提供服务。
      • 500 Internal Server Error：服务器内部错误，无法完成请求。
      • 503 Server Unavailable：服务器当前不能处理客户端的请求，一段时间后可能恢复正常。

6. HTTP 消息报头？

答：消息报头分为通用报头、请求报头、响应报头、实体报头等。消息报头由键值对组成，每行一对，关键字和值用英文冒号 : 分隔。

  • 通用报头：它既可以出现在请求报头，也可以出现在响应报头。比如：

    • Date：表示消息产生的日期和时间。
    • Connection：允许发送指定连接的选项。例如指定连接是连续的；或者指定 close 选项，通知服务器：在响应完成后，关闭连接。
    • Cache-Control：用于指定缓存指令，缓存指令是单向的（响应中出现的缓存指令在请求中未必会出现），且是独立的（一个消息的缓存指令不会影响另一个消息处理的缓存机制）。

  • 请求报头：请求报头通知服务器关于客户端请求的信息，典型的有：

    • Host：请求的主机名，允许多个域名同处一个 IP 地址，即虚拟主机。
    • User-Agent：发送请求的浏览器类型、操作系统等信息。
    • Accept：客户端可识别的内容类型列表，用于指定客户端接收哪些类型的信息。
    • Accept-Encoding：客户端可识别的数据编码。
    • Accept-Language：表示浏览器所支持的语言类型。
    • Connection：允许客户端和服务器指定与请求/响应连接有关的选项。例如，这时为 Keep-Alive 则表示保持连接。
    • Transfer-Encoding：告知接收端为了保证报文的可靠传输，对报文采用了什么编码方式。

  • 响应报头：用于服务器传递自身信息的响应，常见的有：

    • Location：用于重定向接受者到一个新的位置，常用在更换域名的时候。
    • Server：包含服务器用来处理请求的系统信息，与 User-Agent 请求报头是相对应的。

  • 实体报头：用来定义被传送资源的信息，其既可用于请求也可用于响应。请求和响应消息都可以传送一个实体，常见的有：

    • Content-Type：发送给接受者的实体正文的媒体类型。
    • Content-Length：实体正文的长度。
    • Content-Lenguage：描述资源所用的自然语言。
    • Content-Encoding：实体报头被用作媒体类型的修饰符。它的值指示了已经被应用到实体正文的附加内容的编码，因而要获得 Content-Type 报头域中所引用的媒体类型，必须采用相应的解码机制。
    • Last-Modified：实体报头用于指示资源的最后修改日期和时间。
    • Expires：实体报头给出响应过期的日期和时间。

7. HTTPS 协议？

答：

  • HTTPS 的全称是：HyperText Transfer Protocol Secure，即超文本传输安全协议。
  • HTTPS 经由 HTTP 通信，但利用 SSL/TLS 来加密数据包。
  • 使用 HTTPS 的网站：Github、Pornhub 等。

8. HTTP 和 HTTPS 的区别？

答：

  • HTTP 和 HTTPS 是两个不同的协议。
  • HTTP 的 URL 是由 http:// 起始，默认使用端口 80；HTTPS 的 URL 则是由 https:// 起始，默认使用端口 443。
  • HTTP 是不安全的，攻击者可以通过监听和中间人攻击等手段获取敏感信息；HTTPS 的设计可以防止这类攻击，在正确配置时是安全的。

9. 参考

发表于 | 分类于

1. TCP 的传输过程？

答：打开连接 -> 写请求数据 -> 读相应数据 -> 关闭连接。

2. TCP 的握手时机？

答：在 HTTP 连接网络的时候会进行 TCP 的三次握手。

3. TCP 三次握手的过程？

答：

  • 第一次握手：

    • 建立连接。客户端发送连接请求报文段，将 SYN 设置为 1、seq 设置为 x；接下来客户端进入 SYN_SENT 状态，等待服务端的确认。

  • 第二次握手：

    • 服务端收到客户端的 SYN 报文段，对 SYN 报文段进行确认，设置 ACK 为 x+1(seq+1)；同时自己还要发送 SYN 请求信息，将 SYN 设置为 1、seq 设置为 y。服务端将上述所有信息放到 SYN+ACK 报文段中，一并发送给客户端，此时服务端进入 SYN_RCVD 状态。

  • 第三次握手：

    • 客户端收到服务端的 SYN+ACK 报文段；然后将 ACK 设置为 y+1，向服务端发送 ACK 报文段，这个报文段发送完毕后，客户端和服务端都进入 ESTABLISHED (TCP 连接成功)状态，完成 TCP 的三次握手。

4. TCP 的挥手时机？

答：客户端和服务端通过三次握建立了 TCP 连接后，开始传送数据，当数据传送完毕、断开连接时就需要进行 TCP 的四次挥手。

5. TCP 四次挥手的过程？

答：

  • 第一次挥手：

    • 客户端设置 seq 和 ACK，向服务端发送一个 FIN 报文段。此时，客户端进入 FIN_WAIT_1 状态，表示客户端没有数据要发送给服务端了。

  • 第二次挥手：

    • 服务端收到了客户端发送的 FIN 报文段，向客户端回了一个 ACK 报文段。

  • 第三次挥手：

    • 服务端向客户端发送 FIN 报文段，请求关闭连接，同时服务端进入 LAST_ACK 状态。

  • 第四次挥手：

    • 客户端收到服务端发送的 FIN 报文段，向服务端发送 ACK 报文段，然后客户端进入 TIME_WAIT 状态。服务端收到客户端的 ACK 报文段以后，就关闭连接。此时，客户端等待 2MSL(2 倍最大报文段生存时间) 后依然没有收到回复，则说明服务端已正常关闭，这样客户端也可以关闭连接了（服务端先关闭，客户端后关闭）。

6. 画图表示 TCP 三次握手？

答：

TCP 三次握手

7. 画图表示 TCP 四次挥手？

答：

TCP 四次挥手

8. TCP 三次握手四次挥手过程中各种符号的含义？

答：

  • seq（sequence number 序列号）：

    • 占 4 个字节，它是发送端数据包的初始序号。
    • seq=x 表示发送端数据包的初始序列号为 x，seq=0 表示这是第 0 号帧。

  • ack（acknowledge number 确认号）：

    • 占 4 个字节，它是对这次收到数据包的确认，以及对下次收到数据包的期待。
    • ack=x+1 表示我方到 x 为止的所有数据都已正确收到，且告知对方：我期待你方下次给我发送包的初始序号（seq）是 x+1。

  • ACK（Acknowledge field significant 确认序号）：

    • 占一个比特位，它表示响应。
    • ACK=1 表示确认号（seq）有效，ACK=0 确认号无效。

  • SYN（Synchronized sequence numbe 同步序号）：

    • 它表示建立连接。
    • TCP 规定 SYN=1 时不能携带数据，但要消耗一个序号，因此随机选取一个序列号为 seq=x 的数据包（该数据包里就是一个标记 seq，并没有任何的有效数据）。

  • FIN（Final number 结束序号）：

    • 它表示结束一个 TCP 会话，但对应端口仍处于开放状态准备接收后续数据。

9. 为什么 TCP 规定 ISN(Initial Sequence Number, 初始序号) 是随机的？

答：

  • 建立连接的起始方是随机选择 ISN 的初始值，所以这个初始值并没有什么特殊的意义。
  • 这个初始值必须随机选择，如果重复使用一个初始值的话，服务端在一些特殊情况下会感到不确定，可能会认为这是之前报文段的数据重发。
  • 程序都是人写的，从机器的角度来看，不确定性越少越好。

10. 为什么需要三次握手而不是两次四次？

答：

  • 假设， Client 发出连接请求，但因连接请求报文段丢失而未收到 Server 确认，于是 Client 重传一次连接请求。后来收到了 Server 确认，建立了连接，数据传输完毕后，就释放了连接。
  • 但是，很有可能第一次丢失的报文段只是在某些网络结点长时间滞留导致延迟，延迟到连接释放后的某个时间才到达 Server，此时 Server 误以为 Client 又发出一次新的连接请求，于是就向 Client 发出确认报文段，同意建立连接。
  • 所以，不采用三次握手，只要 Server 发出确认，就建立新的连接，此时 Client 不理会 Server 的确认且不发送数据，则 Server 一直等待 Client 发送数据，浪费 Server 资源。

11. 什么是 DDos 攻击？为什么服务器容易受到 DDos 攻击？

答：

  • DDos 全称：Distributed Denial of Service，即分布式拒绝服务。除了 DDos 攻击，还有最早的 DoS 攻击（拒绝服务）和最新的 DRDos 攻击（分布反射式拒绝服务）。
  • DDos 最常用的攻击策略就是使用 SYN-Flood 攻击，即 SYN 洪泛攻击。
  • 服务端的资源分配是在二次握手时分配的，而客户端的资源分配是在完成三次握手时分配的，所以服务器容易受到 SYN 洪泛攻击。SYN 洪泛攻击就是 Client 在短时间内伪造大量的不存在的 IP 地址，并向 Server 不断的发送 SYN 包，Server 则回复确认包，并等待 Client 确认。由于源地址不存在，因此 Server 需要不断重发直至超时（通常在 30 秒到 2 分钟），这些伪造的 SYN 包将长时间占用未连接队列，导致正常的 SYN 请求因为队列满而放弃，从而引起网络堵塞甚至系统瘫痪。

12. 什么是未连接队列？

答：在 TCP 三次握手过程中，服务器维护一个未连接队列，该队列为每个客户端的 SYN 包开设一个条目，该条目表明服务器已收到 SYN 包，并向客户端发出确认，在等待客户端的确认包时，删除该条目，服务器进入 ESTABLISHED 状态。

13. TCP 建立连接后数据传输过程包括哪些？

答：超时重传，快速重传，流量控制，拥塞控制。

14. 为什么连接的时候是三次握手，关闭的时候是四次？

答：

  • 建立连接时，当服务端在 LISTEN 状态下的 SOCKET 收到 SYN 的建立连接请求后，它可以直接发送 SYN+ACK 报文。服务端把 SYN 和 ACK 放到一个报文里，ACK 起应答作用，SYN 起同步作用。
  • 关闭连接时，当服务端收到 FIN 报文，它只表示客户端没有数据要发给服务端了，并不意味着服务端所有数据都已经发给客户端了。所以，服务端并不会立即关闭 SOCKET，只能先回复一个 ACK 报文表示客户端的 FIN 报文已收到。只有当服务端所有报文都发送完了，才会发送 FIN 报文给客户端表示能够关闭连接了。所以这里的 ACK 和 FIN 是分两步分开发送的。

15. 什么是 2MSL？为什么 Client 在 TIME_WAIT 状态还要等 2MSL 才能返回到 CLOSED 状态？

答：

  • 2MSL：
    • MSL 全称：Maximum Segment Lifetime 报文最大生存时间，RFC 793 标准中规定 MSL 为 2 分钟，实际应用中常用的是 30 秒、1 分钟、2 分钟等。
    • 2MSL 即两倍的报文最大生存时间。
  • 理由：
    • 尽管双方都允许关闭连接了，并且握手的 4 个报文也都协调和发送完成，按道理客户端能够直接回到 CLOSED 状态。但我们必须要假设网络是不可靠的，我们无法保证客户端最后发出的 ACK 一定会被服务端收到，因此服务端处于 LAST_ACK 状态下的 SOCKET 可能会由于长时间未收到客户端的 ACK 报文导致超时重发 FIN 报文给客户端，所以客户端这个 TIME_WAIT 状态的作用就是用来重发可能丢失的 ACK 报文给服务端。
    • 报文可能会被混淆，即其他时间的连接可能会被当作本次的连接。当 TCP 连接发送一些物理上的意外情况时，比如网线断开，Linux 上的 TCP 实现会依旧认为当前连接有效，而 windows 则会在一定时间后返回错误信息。

发表于 | 分类于

1. 怎样理解网络分层？

答：

  • 网络分层就是将网络节点所要完成的数据的发送或转发、打包或拆包，以及控制信息的加载或拆出等工作，分别由不同的硬件和软件模块来完成。
  • 这样可以将通信和网络互联这一复杂的问题变得较为简单。网络分层有不同的模型，有的模型分 7 层，有的模型分 5 层。网络分层的每一层都是为了完成一种功能而设的，为了实现这些功能，就需要遵守共同的规则，这个规则就叫作“协议”。
  • 网络分层从上到下分别是应用层、传输层、网络层、数据链路层和物理层，越靠下的层越接近硬件。

2. 怎样理解物理层？

答：

  • 物理层负责比特流在节点间的传输，即负责物理传输。
  • 物理层的协议既与链路有关，也与传输介质有关。
  • 通俗来讲物理层就是把计算机连接起来的物理手段。

3. 怎样理解数据链路层？

答：

  • 数据链路层控制网络层与物理层的通信，主要功能是在不可靠的物理线路上进行数据的可靠传递。
  • 为了保证传输，从网络层接收到的数据被分割成特定的可被物理层传输的帧。帧是用来移动数据的结构包，它不仅包括原始数据，还包括发送方和接收方的物理地址以及纠错控制信息。
  • 帧中的地址确定了帧将发送到何处，而纠错控制信息则确保帧无差错到达。如果在传输数据时，接收点检测到所传数据中有差错，就要通知发送方重发这一帧。

4. 怎样理解网络层？

答：

  • 网络层决定如何将数据从发送方路由到接收方。
  • 网络层通过综合考虑发送优先权、网络堵塞程度、服务质量以及可选路由的花费来决定从一个网络中的节点 A 到另一个网络节点 B 的最佳路径。

5. 怎样理解传输层？

答：

  • 传输层为两台主机上的应用程序提供端到端的通信。相比之下，网络层的功能是建立主机到主机的通信。
  • 传输层有两个传输协议：TCP（传输控制协议）和 UDP（用户数据报协议）。
  • TCP 是一个可靠的面向连接的协议，UDP 是不可靠的或者说无连接的协议。

6. 怎样理解应用层？

答：

  • 应用程序收到传输层的数据后，接下来就要进行解读。
  • 解读必须事先规定好格式，而应用层就是规定应用程序的数据格式的。
  • 应用层的主要协议有 HTTP、FTP、Telnet、SMTP、POP3 等。

发表于 | 分类于

1. MVC 模式

  • 历史：
    • 最早由 Trygve Reenskaug 于 1978 年在 Smalltalk-80 系统上首次提出的一种软件设计模式。

  • 定义：

    • Model（模型层）：针对业务模型，建立的数据结构和相关的类。主要负责网络请求、数据库处理、I/O 等操作。
    • View（视图层）：一般采用 XML 文件或者 Java 代码进行界面的描述，也可以使用 JavaScript+HTML 等方式作为 View 层。
    • Controller（控制层）：Android 的控制层通常在 Activity、Fragment 或由它们控制的其他业务类中。这些类主要是作为初始化页面，展示数据的操作，但是因为你 XML 视图功能太弱，所以 Activity 既要负责视图的显示又要加入控制逻辑，承担的功能过多。

  • 特点：

    • Activity 并不是一个标准的 MVC 模式中的 Controller，它的首要职责是加载应用的布局和初始化用户界面，接受并处理来自用户的操作请求，进而做出响应。随着界面及其逻辑复杂度的不断提升，Activity 类的职责不断增加，以致变得庞大臃肿。
    • View 层和 Model 层相互耦合，不易开发和维护。

2. MVP 模式

  • 历史：
    • MVP 是 MVC 的演化版本。

  • 定义：

    • Model：主要负责数据的存取功能。Presenter 需要通过 Model 层来存储、获取数据。
    • View：负责处理用户事件和视图部分的展示。在 Android 中，它可能是 Activity、Fragment 或者是某个 View 控件。
    • Presenter：作为 View 和 Model 之间沟通的桥梁，它从 Model 层检索数据后返回给 View 层，使得 View 和 Model 之间没有耦合。

  • 特点：

    • 在 MVP 里，Presenter 完全将 Model 和 View 进行了分离，主要的程序逻辑在 Presenter 里实现。
    • Presenter 与具体的 View 是没有直接关联的，而是通过定义好的接口进行交互，从而使得在变更 View 时可以保持 Presenter 的不变，这点符合面向接口编程的特点。
    • View 层理想情况下应该有简单的 set/get 方法，以及用户输入和设置界面显示的内容，除此之外就不应该有更多的内容。绝不允许 View 直接访问 Model，这是其与 MVC 的很大不同之处。

  • 参考：

  • 应用：

3. MVVM 模式

  • 历史：

    • 最早于 2005 年由微软的 WPF 和 Silverlight 的架构师 John Gossman 提出，将 Presenter 改为 ViewModel。
    • 2015 年 Google I/O 大会，Google 发布了 MVVM 架构模式的支持库 Data Binding。
    • Data Binding 官方介绍

  • 定义：

    • 和 MVP 类似，不同的是 ViewModel 和 View 进行双向绑定。
    • 当 View 发生改变时，ViewModel 通知 Model 进行更新数据；同理 Model 数据更新后，ViewModel 通知 View 更新。
    • 通过 Dada Binding，我们可以通过声明式布局以精简的代码来绑定应用程序的逻辑和布局，这样就不用编写大量的类似 findViewById() 这样的模板代码了。

  • 特点：

    • 在默认情况下，Binding 辅助类的名称取决于布局文件的命名，其以大写字母开头，移除下划线，后续的单词首字母大写并以 Binding 结尾，比如 ActivityMainBinding。辅助类包含了布局文件中所有的绑定关系，并会根据绑定表达式给布局文件赋值。
    • 动态更新：Data Binding 提供了 3 种动态更新机制，根据 Model 实体类的内容来动态更新 UI，分别对应于类（Observable）、字段（ObservableField）和集合类型（Observable 容器类）。通过动态更新机制，当 Model 发生变化时，就会通知 ViewModel 对 View 进行动态更新。
    • 双向绑定：Data Binding 在 Android Studio 2.1 Preview 3 版本之后，开始支持双向绑定，即如果 UI 发生变化，Model 实体类实现动态更新，前提是需要结合动态更新机制。

  • 参考：

  • 应用：

发表于 | 分类于

写法

写法（一）：懒汉式（线程不安全）

  • 代码：

    public class Singleton {
    private static Singleton instance;

    // 私有的构造方法，这样除了它本身，不会被其他类实例化
    private Singleton() {}

    // 单例模式中，getInstance() 的写法更常见；Java 源码中 newInstance() 的写法更常见。而且从语义上来说，getInstance() 的方法名更贴近“单例”的含义
    // 通过此静态方法提供全局获取唯一可用对象的访问点
    public static Singleton getInstance() {
        if(instance == null) { // 当多个线程执行到这行代码时会产生多个实例
            intance = new Singleton();
        }
        return instance;
    }
}

  • 分析：这种写法懒加载（lazy loading）很明显，但致命的缺点是在多线程环境下不能正常工作（“永远不要使用线程不安全的单例” – from Tencent Bugly）。

写法（二）：懒汉式（线程安全）

  • 代码：

    public class Singleton {
    private static Singleton instance;

    private Singleton() {}

    public static synchronized Singleton getInstance() { // 通过加锁🔐解决多线程不安全问题
        if(instatnce == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

  • 分析：这种写法能够在多线程环境中很好地工作，而且看起来也具备很好的懒加载（lazy loading）能力。但是，遗憾的是，这种写法的效率很低（耗费内存），99% 的情况下不需要同步。

写法（三）：饿汉式（实例公有化）

  • 代码：

    // Singleton with public final field
public class Singleton {

    // 使用 public 修饰，因此无需 getInstance() 方法，可以直接拿到 instance 实例
    // 此方法由 final 来保证每次返回的都是同一个对象的引用，私有的构造方法也只会被调用一次
    public static final Singleton instance = new Singleton();

    private Singleton() {}
}

  • 分析：优点是比较简洁（不再有优势）

写法（四）：饿汉式（实例私有化）

  • 代码：

    // Singleton with static factory
// 现代的 JVM 基本都内嵌了对 static factory 方法的调用，使得 public field 方式不再有优势
// 此方法更灵活，只需修改 getInstance() 的返回逻辑，而不需要改变 API 就可以将类改为非单例类
public class Singleton {
    private static Singleton instance = new Singleton();

    private Singleton() {}

    public static Singleton getInstance() {
        return instance;
    }
}

  • 分析：这种写法基于 ClassLoader 机制从而避免了多线程环境下的同步问题。不过，instance 在类加载时就实例化（虽然导致类加载的原因有很多），在单例模式中大多都是因为调用 getInstance() 方法，但是也不能确定有其他的方式（或者其他的静态方法）导致类加载，这时候初始化 instance 显然没有达到懒加载（lazy loading）的效果。

写法（五）：饿汉式（静态代码块）

  • 代码：

    public class Singleton {
    private Singleton instance = null;

    private Singleton() {}

    static {
        instance = new Singleton(); // 基静态、子静态 -> 基实例代码块、基构造 -> 子实例代码块、子构造
    }

    public static Singleton getInstance() {
        return this.instance;
    }

}

  • 分析：三种饿汉式差别不大，都是在类初始化时实例化 instance。

写法（六）：静态内部类（ClassLoader）

  • 代码：

    public class Singleton {

    private static class SingletonHolder { // 私有的静态内部类
        private static final Singleton INSTANCE = new Singleton();
    }

    private Singleton() {}

    public static final Singleton getInstance() {
        return SingletonHolder.INSTANCE;
    }
}

  • 分析：这种写法同样利用了 ClassLoader 的类加载机制来保证初始化 instance 时只有一个线程。它跟饿汉式写法不同的是（很细微的差别）：饿汉式是只要 Singleton 类被加载了，那么 instance 就会被实例化（没有达到懒加载的效果），而静态内部类的写法是即使 Singleton 类被加载了，instance 却不一定被实例化。因为 SingletonHolder 内部类没有被主动使用过，只有显示通过调用 getInstance() 方法时，才会显示加载 SingletonHolder 类，从而实例化 instance。想象一下，如果实例化 instance 很消耗资源，我想让它延迟加载；另一方面，我不希望在 Singleton 类加载时就实例化，因为我不能确保 Singleton 类还可能在其他的地方被主动使用从而被加载，那么这个时候实例化 instance 显然是不合适的。这个时候，静态内部类的写法相比饿汉式写法就显得很合理。

写法（七）：双重校验锁（DCL）

  • 代码：

    public class Singleton {
    // volatile 关键字的作用：保证内存可见性、保证有序性（禁止指令重排），但不保证原子性
    // 大部分情况下不加 volatile 也是可以的，但如果发生指令重排，则会在第二次 check 处导致线程不安全
    private volatile static Singleton instance; 

    private Singleton() {}

    public static Singleton getInstance() {
        if(instance == null) { // 第一次 check，避免不必要的同步
            synchronized(Singleton.class) { // 仅同步实例化的代码块
                if(instance == null) { // 第二次 check，保证线程安全
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

// TODO: 还有优化的空间，参见底部参考部分第二篇文章，可以算做第十一种写法

  • 分析：这种写法是第二种写法的升级版，不过在 JDK 1.5 之后，双重校验锁才能达到单例效果。

写法（八）：枚举

  • 代码：

    public enum Singleton {
    INSTANCE;

    // 枚举同普通类一样，可以有自己的成员变量和方法
    public void do() {
        System.out.println("Do whatever you want");
    }
}

  • 分析：这种写法是 《Effective Java》 作者 Josh Bloch 提倡的方式，它不仅能避免多线程同步问题（创建枚举默认就是线程安全的），而且还能防止反序列化重新创建新的对象，可谓是很坚强的壁垒。不过，个人认为由于在 JDK 1.5 中才加入 enum 特性，用这种方式写不免让人感觉生疏。在实际工作中，也很少见有人这么写过。

  • 优点：

    • 枚举单例写法简单：肉眼可见。
    • 枚举可解决线程安全问题：反序列化后，可以发现内部使用了 static、final 修饰每一个枚举项。
    • 枚举可避免反序列化破坏单例：普通类的反序列化会使用反射，反序列化后的对象是重新 new 出来的，这就破坏了单例，而枚举的序列化和反序列化是有特殊定制的。

  • 参考：为什么我墙裂建议大家使用枚举来实现单例

写法（九）：CAS 方式

  • 代码：

    public class Singleton {
    // AtomicReference 是原子引用类型，用来以原子方式更新复杂类型
    private static final AtomicReference<Singleton> INSTANCE = new AtomicReference<Singleton> ();

    private Singleton() {}

    public static Singleton getInstance() {
        for(;;) {
            Singleton instance = INSTANCE.get();
            if(instance != null) {
                return instance;
            }
            instance = new Singleton();
            // CAS 方法有两个参数 expect 和 update，以原子方式实现了比较并设置的功能
            // 如果当前值等于 expect，则更新为 update 并返回 true；否则不更新并返回 false
            if(INSTANCE.compareAndSet(null, instance)) {
                return instance;
            }
        }
    }
}

  • 分析：

    • 上面几种线程安全的单例写法，虽然没有在代码中显示的使用 synchronized（除了双重校验锁写法），但是，都是借助了 ClassLoader 的线程安全机制。而 ClassLoader 的线程安全机制底层也是使用了 synchronized 的；ClassLoader 的 loadClass() 方法在加载类的时候使用了 synchronized 关键字。也正是因为这样， 除非被重写，这个方法默认在整个类加载过程中都是同步的（线程安全的）。
    • 优点：不需要使用传统的锁机制来保证线程安全，CAS 是一种基于忙等待的算法，依赖底层硬件的实现，相对于锁它没有线程切换和阻塞的额外消耗，可以支持较大的并行度。
    • 缺点：如果忙等待一直执行不成功(一直在死循环中)，会对 CPU 造成较大的执行开销。而且，这种写法如果有多个线程同时执行 singleton = new Singleton(); 也会比较耗费堆内存。

  • 参考：不使用 synchronized 和 lock，如何实现一个线程安全的单例？

写法（十）：Lock 方式

  • 代码：

    // 类似双重校验锁写法
public class Singleton {
       private static Singleton instance = null;
       private static Lock lock = new ReentrantLock();

       private Singleton() {}

       public static Singleton getInstance() {
           if(instance == null) {
               lock.lock(); // 显式调用，手动加锁
               if(instance == null) {
                   instance = new Singleton();
               }
               lock.unlock(); // 显式调用，手动解锁
           }
           return  instance;
       }
}

  • 参考：你写的单例是线程安全的吗？

对比

单例模式 是否推荐 懒加载 反序列化单例 反射单例 克隆单例 性能、失效问题
（三种）饿汉模式 eager 加载推荐 ✘ ✘ ✘ ✘ 注意是急切初始化！
（包括同步方法）懒汉模式 ✘ ✔️ ✘ ✘ ✘ 存在性能问题，每次获取实例都会同步
静态内部类 推荐 ✔️ ✘ ✘ ✘
双重校验锁（DCL） 可用 ✔️ ✘ ✘ ✘ JDK < 1.5 失效
枚举 最推荐 ✔️ ✔️ ✔️ ✔️ JDK < 1.5 不支持

总结

  • 有两种场景可能导致非单例的情况（还有一种克隆的场景）：

    • 场景一：如果单例由不同的类加载器加载，那便有可能存在多个单例类的实例。假设不是远端存取，例如一些 servlet 容器，对每个 servlet 使用完全不同的类加载器，这样的话如果有两个 servlet 访问一个单例类，它们就会有各自的实例。

      • 解决办法：

        private static Class getClass(String className) throws ClassNotFoundException {
    ClassLoader classLoader = Thread.currentThread().getContextClassLoader();

    if(classLoader = null) {
        classLoader = Singleton.class.getClassLoader();
    }

    return (classLoader.loadClass(className));
}

    • 场景二：如果 Singleton 实现了 java.io.Serializable 接口，那么这个类的实例就可能被序列化和反序列化。不论如何，如果序列化一个单例类的对象，接下来反序列多个那个对象，那就会有多个单例类的实现。

      • 解决办法：

        public class Singleton implements Serializable {
    public static Singleton INSTANCE = new Singleton();

    protected Singleton() {}

    private Object readResolve() {
        return INSTANCE;
    }
}

  • 就个人来说，更倾向第三种（饿汉式）和第五种（静态内部类），简单易懂，而且在 JVM 层实现了线程安全（如果不是多个类加载器的情况）。

    • 一般情况下，会使用第三种（饿汉式），只有在要明确实现懒加载效果时才会使用第五种（静态内部类）。
    • 另外 ，如果涉及到反序列化创建对象时会尝试使用第六种（枚举）的方式来实现单例。不过，尽量保证我们程序是线程安全的，而且尽量不会使用懒汉式。
    • 如果有其他特殊需求，可能会使用第七种（双重校验锁）方式，毕竟，JDK 1.5 已经没有双重检查锁定的问题了。

  • 一般来说，第一种（懒汉式，线程不安全）不算单例，第三种（饿汉式，线程安全）和第四种（饿汉式，静态代码块变种）就是一种。如果算的话，第五种（静态内部类）也可以分开写了。所以，一般单例都是六种写法，即：懒汉式、饿汉式、静态内部类、枚举、双重校验锁、CAS 方式。

参考