RxJava 2.x 实战系列（三）：创建操作符

发表于 2019-09-05 | 分类于《RxJava 2.x 实战系列》

1.

RxJava 2.x 实战系列（二）：RxJava 基础知识

发表于 2019-05-02 | 分类于《RxJava 2.x 实战系列》

1. 怎样理解 Observable?

答：

RxJava 的使用通常需要三步：

创建 Observable：Observable 的字面意思是被观察者，使用 RxJava 时需要创建一个被观察者，它会决定什么时候触发事件以及触发怎样的事件。有点类似上游发送命令，可以在这里决定异步操作模块的顺序和异步操作模块的次数。
创建 Observer：Observer 即观察者，它可以在不同的线程中执行任务。这种模式可以极大地简化并发操作，因为它创建了一个处于待命状态的观察者哨兵，可以在未来某个时刻响应 Observable 的通知，而不需要阻塞等待 Observable 发射数据。
使用 subscribe() 进行订阅：创建了 Observable 和 Observer 之后，我们还需要使用 subscribe() 方法将它们连接起来，这样整个上下游就能衔接起来实现链式调用。

2. `subscribe` 的重载方法有？

答：

subscribe(onNext)
subscribe(onNext, onError)
subscribe(onNext, onError, onComplete): 在 subscribe 中 onComplete 是执行完 onNext 之后再执行的。
subscribe(onNext, onError, onComplete, onSubscribe): 先执行 onSubscribe，再执行 onNext 和 onComplete

3. 【笔试题】写出下面代码的输出结果？

答：

Observable.just("Hello World)
		.subscribe(new Consumer<String>() {
			@Override
			public void accept(String s) throws Exception {
				System.out.println(s);
			}
		}, new Consumer<Throwable>() {
			@Override
			public void accept(Throwable throwable) throws Exception {
				System.out.println(throwable.getMessage());
			}
		}, new Action() {
			@Override
			public void run() throws Exception {
				System.out.println("onComplete());
			}
		});
		
执行结果：
Hello World
onComplete()

Observable.just("Hello World)
		.subscribe(new Consumer<String> () {
			@Override
			public void accept(String s) throws Exception {
				System.out.println(s);
			}
		}, new Consumer<Throwable> () {
			@Override
			public void accept(Throwable throwable) throws Exception {
				System.out.println(throwable.getMessage());
			}
		}, new Action() {
			@Override
			public void run() throws Exception {
				System.out.println("onComplete");
			}
		}, new Consumer<Disposable> () {
			System.out.println("subscribe);
		});
		
 执行结果：
 subscribe
 Hello World
 onComplete()

Observable.just("Hello World)
		.subscribe(new Observer<String>() {
			@Override
			public void onSubscribe(Disposable d) {
				System.out.println("subscribe");
			}
			
			@Override
			public void onNext(String s) {
				System.out.println(s);
			}
			
			@Override
			public void onError(Throwable e) {
				System.out.println(e.getMessage());
			}
			
			@Override
			public void onComplete() {
				System.out.println("onComplete()");
			}
		});
		
执行结果：
subscribe
Hello World
onComplete()

4. `RxJava 2` 的 5 种观察者模式？

答：

Observable 和 Observer
- Observable: 能够发射 0 或 n 个数据，并以成功或错误事件终止。
Flowable 和 Subscriber
- Flowable：能够发射 0 或 n 个数据，并以成功或错误事件终止。支持背压，可以控制数据源发射的速度。
Single 和 SingleObserver
- Single：只发射单个数据或错误事件。
Completable 和 CompletableObserver
- Completable：从来不发射数据，只处理 onComplete 和 onError 事件。可以看成 Rx 的 Runnable。
Maybe 和 MaybeObserver
- Maybe：能够发射 0 或者 1 个数据，要么成功、要么失败。有点类似 Optional。

5. 怎样理解 `do` 操作符？

答：

do 操作符可以给 Observable 的生命周期的各个阶段加上一系列的回调监听，当 Observable 执行到这个阶段时，这些回调就会被触发。

6. 下面代码的执行结果是？

答：

Observable.just("Hello")
		.doOnNext(new Consumer<String> () {
			@Override
			public void accept(@NonNull String s) throws Exception {
				System.out.println("doOnNext: " + s);
			}
		})
		.doAfterNext(new Consumer<String> () {
			@Override
			public void accept(@NonNull String s) throws Exception {
				System.out.println("doAfterNext: " + s);
			}
		})
		.doOnComplete(new Action() {
			@Override
			public void run() throws Exception {
				System.out.println("doOnComplete: ");
			}
		})
		.doOnSubscribe(new Consumer<Disposable> () { // 订阅之后回调的方法
			@Override
			public void accept(@NonNull Disposable disposable) throws Exception {
				System.out.println("doOnSubscribe: ");
			}
		})
		.doAfterTerminate(new Action() {
			@Override
			public void run() throws Exception {
				System.out.println("doAfterTerminate: ");
			}
		})
		.doFinally(new Action() {
			@Override
			public void run() throws Exception {
				System.out.println("doFinally: ");
			}
		})
		.doOnEach(new Consumer<Notification<String>> () { // Observable 每发射一个数据就会触发这个回调，不仅包括 onNext, 还包括 onError 和 onCompleted
			@Override
			public void accept(@NonNull Notification<String> stringNotification) throws Exception {
				System.out.println("doOnEach: " + (stringNotification.isOnNext()?"onNext":stringNotification.isOnComplete()?"onComplete":"onError"));
			}
		})
		.doOnLifecycle(new Consumer<Disposable>() { // 订阅之后可以取消订阅
			@Override
			public void accept(@NonNull Disposable disposable) throws Exception {
				System.out.println("doOnLifecycle: " + disposable.isDisposed());
			}
		}, new Action() {
			@Override
			public void run() throws Exception {
				System.out.println("doOnLifecycle run: ");
			}
		})
		.subscribe(new Consumer<String>() {
			@Override
			public void accept(@NonNull String s) throws Exception {
				System.out.println("收到消息：" + s);
			}
		});
		
执行结果：
doOnSubscribe:
doOnLifecycle: false
doOnNext: Hello
doOnEach: onNext
收到消息：Hello
doAfterNext: Hello
doOnComplete:
doOnEach: onComplete
doFinally:
doAfterTerminate:

7. 描述一下常用的 `do` 操作符？

答：

doOnSubscribe:
- 一旦观察者订阅了 Observable，它就会被调用。
doOnLifecycle:
- 可以在观察者订阅之后，设置是否取消订阅。
doOnNext:
- 它产生的 Observable 每发射一项数据就会调用它一次，它的 Consumer 接受发射的数据项。一般用于在 subscribe 之前对数据进行处理。
doOnEach:
- 它产生的 Observable 每发射一项数据就会调用它一次，不仅包括 onNext，还包括 onError 和 onCompleted。
doAfterNext:
- 在 onNext 之后执行，而 doOnNext() 是在 onNext 之前执行。
doOnComplete:
- 当它产生的 Observable 在正常终止调用 onComplete 时会被调用。
doFinally:
- 在它产生的 Observable 终止之后会被调用，无论是正常终止还是异常终止。doFinally 优先于 doAfterTerminate 的调用。
doAfterTerminate:
- 注册一个 Action，当 Observable 调用 onComplete 或 onError 时触发。

RxJava 2.x 实战系列（一）：RxJava 简介

发表于 2019-05-01 | 分类于《RxJava 2.x 实战系列》

1. 什么是响应式编程？

答：

响应式编程，Reactive Programming，简称 RP。
在计算机中，响应式编程是一种面向数据流和变化传播的编程范式。这意味着可以在编程语言中很方便地表达静态或动态的数据流，而相关的计算模型会自动将变化的值通过数据流进行传播。
传统的编程方式是顺序执行的，需要等待直至完成上一个任务之后才会执行下一个任务。无论是提升机器的性能还是代码的性能，本质上都需要依赖上一个任务的完成。如果需要响应迅速，就得把同步执行的方式换成异步执行，方法执行变成消息发送。这就是异步编程的方式，它是响应式编程的重要特征之一。

2. 响应式编程的特点？

答：

异步编程：
- 提供了合适的异步编程模型，能够挖掘多核 CPU 的能力、提高效率、降低延迟和阻塞等。
数据流：
- 基于数据流模型，响应式编程提供一套统一的 Stream 风格的数据处理接口。与 Java 8 中的 Stream 相比，响应式编程除了支持静态数据流，还支持动态数据流，并且允许复用和同时接入多个订阅者。
变化传播：
- 简单来说就是以一个数据流为输入，经过一连串操作转化为另一个数据流，然后分发给各个订阅者的过程。这就有点像函数式编程中的组合函数，将多个函数串联起来，把一组输入数据转化为格式迥异的输出数据。

3. 响应式编程的应用？

答：

响应式编程在用户界面编程领域及基于实时系统的动画方面都有广泛的应用。
在处理嵌套回调的异步事件、复杂的列表过滤和变换的时候也都有良好的表现。

4. 什么是函数式编程？

答：

函数式编程，Funtional Programming，简称 FP。
在函数式编程中，由于数据是不可变的（immutable），因此没有并发编程的问题，是线程安全的。
它将计算机运算看作数学中函数的计算，主要特点是将计算过程分解为多个可复用的函数，并且避免了状态及变量的概念。
函数式编程虽然也可以归结到面向过程的程序设计，但其思想更接近数学计算。

5. 函数式编程的特点？

答：

函数是“第一等公民”：
- 所谓“第一等公民”（First Class），指的是函数与其他数据类型一样，处于平等地位，可以赋值给其他变量，也可以作为参数，传入另一个函数，或者作为别的函数的返回值。
闭包和高阶函数：
- 闭包是起函数的作用并可以像对象一样操作的对象。与此类似，FP 语言支持高阶函数。高阶函数可以用另一个函数（间接地，用一个表达式）作为输入参数，在某些情况下，它甚至返回一个函数作为输出参数。这两种结构结合在一起，即可以用优雅的方式进行模块化编程，这是使用 FP 的最大好处。
递归：
- 把递归作为控制流程的机制。例如，在 Haskell 的世界中，没有变量赋值和流程跳转，如果要实现一些简单的功能，比如求一个数组中的最大值，则需要借助递归来实现。
惰性求值（Lazy Evaluation）：
- 它表示为“延迟求值”和“最小化求值”。惰性求值使得代码具备了巨大的优化潜能。支持惰性求值的编译器会像数学家看待代数表达式那样看待函数式编程的程序，即抵消相同项从而避免执行无谓的代码，安排代码执行顺序从而实现更高的执行效率甚至是减少错误。惰性求值另一个重要的好处是它可以构造一个无限的数据类型，无须担心由无穷计算所导致的内存溢出错误。
没有“副作用”（Side Effect）：
- 指的是函数内部与外部互动（最典型的情况，就是修改全局变量的值），产生运算以外的其他结果。函数式编程强调没有“副作用”，意味着函数要保持独立，所有功能就是返回一个新的值，没有其他行为，尤其是不得修改外部变量的值。

6. 什么是函数响应式编程？

答：

函数响应式编程结合了函数式和响应式的优点，把函数范式里的一套思路和响应式编程结合起来就是函数响应式编程。
传统的面向对象编程是通过抽象出的对象关系来解决问题，函数式编程是通过函数（function）的组合来解决问题，响应式编程是通过函数式编程的方式来解决回调地狱（Callback Hell）的问题。
用传统的面向对象来处理异步事件不是很直观，处理并发也十分麻烦，所有才产生了函数响应式编程。

7. RxJava 产生的由来？

答：

RxJava 是 Reactive Extensions 的 Java 实现，用于通过使用 Observable/Flowable 序列来构建异步和基于事件的程序的库。
RxJava 扩展观察者模式以支持数据/事件序列，并添加允许你以声明方式组合序列的操作符，同时提取对低优先级的线程、同步、线程安全性和并发数据结构等问题的隐藏。

8. 什么是 Rx?

答：

ReactiveX 是 Reactive Extensions 的缩写，一般简写为 Rx。最初是 LINQ 的一个扩展，由微软架构师 Erik Meijer 领导的团队所开发，于 2012 年 11 月开源。
Rx 是一个编程模型，目标是提供一致的编程接口，帮助开发者更方便地处理异步数据流，Rx 库支持 .NET、JavaScript 和 C++。
Rx 的大部分语音库由 ReactiveX 这个组织负责维护，比较流行的有 RxJava、RxJS 和 Rx.NET，社区网站是 http://reactivex.io/。

9. ReactiveX 的历史？

答：

微软给的定义是，Rx 是一个函数库，让开发者可以利用可观察序列和 LINQ 风格查询操作符来编写异步和基于事件的程序。通过使用 Rx，开发者可以通过利用 Observables 表示异步数据流，用 LINQ 操作符查询异步数据流，用 Schedulers 参数化异步数据流的并发处理。可以这样定义 Rx: Rx=Observables + LINQ + Schedulers。
在 RxJava 2.x 中，Observables 包含了 Observables、Flowable、Single、Maybe、Completable 等。
ReactiveX.io 给的定义是，Rx 是一个使用可观察数据流进行异步编程的编程接口，ReactiveX 结合了观察者模式、迭代器模式和函数式编程的精华。

10. 怎样理解 Rx 模式？

答：

使用观察者模式：
- 创建：Rx 可以方便地创建事件流和数据流。
- 组合：Rx 使用查询式的操作符组合和变换数据流。
- 监听：Rx 可以订阅任何可观察的数据流并执行操作。
简化代码：
- 函数式风格：对可观察的数据流使用无副作用的输入/输出函数，避免了程序里错综复杂的状态。
- 简化代码：Rx 的操作符通常可以将复杂的难题简化为很少的几行代码。
- 异步错误处理：传统的 try/catch 没办法处理异步计算，Rx 提供了合适的错误处理机制。
- 轻松使用并发：Rx 的 Observables （包括 Observable、Flowable、Single、Completable 和 Maybe）和 Schedulers 可以让开发者摆脱底层的线程同步和各种并发问题。

11. 【笔试题】某 APP 从服务端获取酒店列表，并将价格大于等于 500 的房间全部列出来展示在界面上？

答：

传统写法：

new Thread() {
	@Override
	public void run() {
		super.run();
		// 从服务端获取酒店列表
		List<Hotel> hotels = getHotelsFromServer();
		for(Hotel hotel : hotels) {
			List<Room> rooms = hotel.rooms;
			for(Room room : rooms) {
				if(room.price >= 500) {
					runOnUiThread(
						new Runnable() {
							@Override
							public void run() {
								// 将房间的信息添加到 UI 上
								displayUI(room);
							}
						});
				}
			}
		}
	}	
}.start();

使用 RxJava:

Observable.fromIterable(getHotelsFromServer())
		.flatMap(new Function<Hotel, Observable<Room>> () {
			@Override
			public Observable<Room> apply(Hotel hotel) {
				return Observable.fromIterable(hotel.rooms);
			}
		})
		.filter(new Predicate<Room>() {
			@Override
			public boolean test(@NonNull Room room) throws Exception {
				return room.price >= 500;
			}
		})
		.subscribeOn(Schedulers.io())
		.observeOn(AndroidSchedulers.mainThread())
		.subscribe(new Consumer<Room>() {
			@Override
			public void accept(Room room) {
				// 将房间的信息添加到屏幕上
				displayUI(room);
			}
		});

RxJava + Lambda:

Observable.fromIterable(getHotelsFromServer())
		.flatMap(hotel -> Observable.fromIterable(hotel.rooms))
		.filter(room -> room.price >= 500)
		.subscribOn(Schedulers.io())
		.observeOn(AndroidSchedulers.mainThread()) // 该行和上面一行还能用 compose 操作符和 Transformer 一起封装
		.subscribe(this::displayUI);

12. 【笔试题】写一个 `RxJava` 版的 `Hello World`?

答：

RxJava 版：

Observable.create(new ObservableOnSubscribe<String> () {
	@Override
	public void subscribe(@NonNull ObservableEmitter<String> e) throws Exception {
		e.onNext("Hello World");
	}
}).subscribe(new Consumer<String>() {
	@Override
	public void accept(@NonNull String s) throws Exception {
		System.out.println(s);
	}
});

简化的 RxJava 版：

Observable.just("Hello World").subscribe(new Consumer<String> () {
	@Override
	public void accept(@NonNull String s) throws Exception {
		System.out.println(s);
	}
});

RxJava + Lambda:

1	Observable.just("Hello World").subscribe(System.out::println); // System.out.println 是方法引用，简化版的 Lambda 表达式，是 Java 8 的特性

数据结构与算法之美系列（四）：十大经典排序算法总结

发表于 2019-03-14 | 分类于《数据结构与算法之美系列》

算法分类

算法总结

排序算法	时间复杂度（最好）	时间复杂度（最坏）	时间复杂度（平均）	空间复杂度	稳定性
冒泡排序	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(nk)**	O(n+k)	✔️

算法实现

冒泡排序

动图：

代码：

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;
        }
    }
}

选择排序

动图：

代码：

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;
        }
    }
}

插入排序

动图：

代码：

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;
      }
}

希尔排序

动图：

代码：

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);
    }
}

归并排序

动图：

代码：

// 归并排序算法, 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];
    }
}

快速排序

动图：

代码：

// 快速排序，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;
}

堆排序

动图：

代码：

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;
    }

}

桶排序

动图：

代码：

 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;
    }

}

计数排序

动图：

代码：

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];
    }
  }

}

基数排序

动图：

代码：

 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;
    }
}

数据结构与算法之美系列（三）：链表（下）：如何轻松写出正确的链表代码

发表于 2019-03-13 | 分类于《数据结构与算法之美系列》

单链表反转

来源：

LeetCode-206: Reverse Linked List

迭代版：

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;
    }
}

链表中环的检测

来源：

LeetCode-141: Linked List Cycle

哈希表：

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;
    }
}

两个有序的链表合并

来源：

LeetCode-21: Merge Two Sorted Lists

一般写法：

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 个结点

来源：

LeetCode-19: Remove Nth Node From End of List

双指针：

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;
    }
}

求链表的中间结点

来源：

LeetCode-876: Middle of the Linked List

快慢指针：

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;
    }
}

数据结构与算法之美系列（二）：链表（上）：如何实现 LRU 缓存淘汰算法

发表于 2019-03-12 | 分类于《数据结构与算法之美系列》

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("不是回文");
        }
    }
}

数据结构与算法之美系列（一）：如何抓住重点，系统高效地学习数据结构与算法

发表于 2019-03-11 | 分类于《数据结构与算法之美系列》

图谱

重点

10 个数据结构：
- 数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树。
10 个算法：
- 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

计算机网络系列（三）：详解 HTTP 协议原理

发表于 2019-03-10 | 分类于《计算机网络系列》

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

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 个部分组成。
- 图例：
请求行：
- 请求行由请求方法、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-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. 参考

计算机网络系列（二）：详解 TCP 三次握手与四次挥手

发表于 2019-03-10 | 分类于《计算机网络系列》

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 则会在一定时间后返回错误信息。

计算机网络系列（一）：详解网络分层

发表于 2019-03-10 | 分类于《计算机网络系列》

1. 怎样理解网络分层？

答：

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

2. 怎样理解物理层？

答：

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

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

答：

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

4. 怎样理解网络层？

答：

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

5. 怎样理解传输层？

答：

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

6. 怎样理解应用层？

答：

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

1.

1. 怎样理解 Observable?

2. subscribe 的重载方法有？

3. 【笔试题】写出下面代码的输出结果？

4. RxJava 2 的 5 种观察者模式？

5. 怎样理解 do 操作符？

6. 下面代码的执行结果是？

7. 描述一下常用的 do 操作符？

1. 什么是响应式编程？

2. 响应式编程的特点？

3. 响应式编程的应用？

4. 什么是函数式编程？

5. 函数式编程的特点？

6. 什么是函数响应式编程？

7. RxJava 产生的由来？

8. 什么是 Rx?

9. ReactiveX 的历史？

10. 怎样理解 Rx 模式？

11. 【笔试题】某 APP 从服务端获取酒店列表，并将价格大于等于 500 的房间全部列出来展示在界面上？

12. 【笔试题】写一个 RxJava 版的 Hello World?

算法分类

算法总结

算法实现

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序

堆排序

桶排序

计数排序

基数排序

单链表反转

来源：

迭代版：

递归版：

链表中环的检测

来源：

哈希表：

双指针：

两个有序的链表合并

来源：

一般写法：

递归版本（一）：

递归版本（二）：

删除链表倒数第 n 个结点

来源：

双指针：

求链表的中间结点

来源：

快慢指针：

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

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

思路：

基于 Array：

基于 LinkedList：

基于 LinkedHashMap：

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

图谱

重点

1. HTTP 概念？

2. HTTP 历史版本：

3. HTTP 主要特点？

4. HTTP 请求报文？

5. HTTP 响应报文？

6. HTTP 消息报头？

7. HTTPS 协议？

8. HTTP 和 HTTPS 的区别？

9. 参考

1. TCP 的传输过程？

2. TCP 的握手时机？

3. TCP 三次握手的过程？

4. TCP 的挥手时机？

5. TCP 四次挥手的过程？

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

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

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

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

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

2. `subscribe` 的重载方法有？

4. `RxJava 2` 的 5 种观察者模式？

5. 怎样理解 `do` 操作符？

7. 描述一下常用的 `do` 操作符？

12. 【笔试题】写一个 `RxJava` 版的 `Hello World`?