仓库地址：http://tinyhttpd.sourceforge.net/

HTTP的相关资料可以再MDN上查到，地址为https://developer.mozilla.org/zh-CN/docs/Web/HTTP

一些常用定义

socketlen_t定义：在socket编程中的accept函数的第三个参数的长度必须和int的长度相同，于是有了此类型。

memset函数：void *memset(void *str, int c, size_t n) 复制字符c到参数str所指向的字符串的前n个字符。

isspace函数：用于判断字符是否是空白字符

Main函数

执行流程：

参数的声明 ⇒ 调用startup函数启动一个服务 ⇒ 在循环中持续的对端口进行监听，调用accept函数处理请求 ⇒ 调用close函数关闭服务

startup

用于启动一个进程在特定端口监听网络服务连接，当端口号是0的时候，会随机选择一个端口，并且会修改原有的端口变量为真实的端口。

执行流程：

创建socket连接 ⇒ 处理socket错误 ⇒ 清空name信息 ⇒ 设置name的参数：使用的协议，AF_INET是IPV4，监听的端口，主机地址 ⇒ 设置端口复用并处理错误setsocketopt ⇒ 使用bind函数绑定socket端口 ⇒ 处理是否是随机端口，是则获取一个可用端口 ⇒ 调用listen函数设置监听的上限数

accept_request

用于从服务器端口上接受一个请求并返回数据。

执行流程：

1. 开始都是一些变量的声明，由于代码比较老，这个地方使用的还是早期的CGI逻辑

2. 读取请求体的第一行

   这里读取的是client端发送过来的报文，通过#define ISspace(x) isspace((int)(x))定义的ISSpace对读取的数据进行判断，如果不是空字符串就继续读取，直到达到method参数的限制。

   这个地方在数组读取的末尾显示的指定\0，可以认为这个地方数据存在复用，这样在后续的读取过程中直接读取此字符则能明白已经是数据的结尾

3. 使用strcasecmp函数对请求方法进行判断。

   1. 由于编写这段代码时间的原因，其本身就只能支持GET和POST方法；并且没有规定方法必须严格的大写，所以得在判断相等的时候忽略大小写
   2. 是POST请求的时候，将cgi的参数置为1

4. 读取url的信息到url的char数组中，此时的url中是可能包含有查询参数的，因为历史的原因，可以发现在POST请求中带有查询参数是没有用的。

5. 当发现是GET请求的时候，要将?后的查询参数读取到query_string中，并且由于代码复用的问题，在结尾也要显示使用\0

6. 使用sprintf函数将url格式化到htdocs%s中，最后赋值给path变量

7. 当路径只是/，则将index.html拼接到path变量之后

8. 使用stat函数判断在系统中请求路径的信息是否存在，不存在则将后续的数据全部抛弃，最后调用not_found函数提示报错信息

   否则进入实际请求。先判断请求的模式是否是文件夹(st.st_mode & S_IFMT) == S_IFDIR，也就是根请求，是则将/index.html追加到path信息中。

   接下来判断文件是否有可执行权限，有则将cgi设置为1，最后根据cgi的值调用不同的函数进行处理。

serve_file

用于向客户端传递读取的文件

1. 先读取此次请求的头信息并将其丢弃
2. 读取文件，文件不存在则用not_found函数提示报错。否则使用headers函数设置响应头信息，用cat函数将读取的数据传递给client
3. 关闭读取的文件

execute_cgi

用于执行cgi脚本

1. 是GET请求的时候，读取并丢弃后续的headers信息
2. 是POST请求的时候读取Content-Length数据，这里并没有读取其他的请求头信息，如果其为空，则使用bad_request 函数向client发送错误信息
3. 创建cgi_input和cgi_output两个管道，创建不成功则使用canot_execute函数向client传递报错信息
4. 创建一个子进程用于执行脚本
   1. 将子进程的标准输出重定向到cgi_output，将子进程的标准输入重定向到cgi_input上
   2. 设置环境变量，将这个环境变量添加到子进程的环境变量中
   3. 根据请求类型的不同构造不同的环境变量
   4. 使用execl函数执行脚本，然后退出此函数
5. 创建子进程不成功则进行关闭处理
   1. 首先关闭cgi_ouput的写和cgi_input的读
   2. 是POST方法则继续读取body的信息，并将信息写入到cgi_input中
   3. 从cgi_output管道中读取数，调用send函数向client发送数据
   4. 关闭两个管道
   5. 等待子进程的退出

CopyOnWriteArrayList

应用于读多写少的环境中，根据类注释，可以直到在所有可变操作（add、set和remove）的时候是创建底层数组副本来实现的。

从源码来看，get操作是直接没有锁和同步操作的，操作的就是原始的数组。

set操作先用ReentrantLock来获取锁，然后拷贝原数组的备份，在其基础上进行修改，最后用setArray方法来替换原数组。add方法也类似，但是在数据增长方面，没有了扩容控制，而是使用了Arrays.copyOf直接返回一个数据加一的新数组。而从固定位置插入的方法则使用System.arrayCopy方法进行操作

ConcurrentLinkedQueue

一个基于链表节点实现的无界线程安全队列。

当许多线程共享一个公共集合时，ConcurrentLinkledQueue是一个合适的选择。

迭代器是弱一致的，返回的元素反映了队列在迭代器创建时或创建后某个时刻的状态，它不抛出ConcurrentModificationException，并且可以与其他操作并发进行。包含在队列里面的元素都将被返回一次。

BlockingQueue

BlockingQueue在处理一个操作不能被立即满足但是能在未来某个时刻被满足的四种情况：

1. 抛出异常

2. 返回特殊值

3. 阻塞当前线程的执行直到条件被满足

4. 在给定的最大时间内进行阻塞

   

BlockingQueue不接受null，有容量限制，主要实现生产者-消费者队列，但是还支持Collection接口，其实现是线程安全的，所有队列方法都使用内部锁或者其他并发控制方式；其本质上不支持任何的colse和shutdown操作。

内存一致性问题：将对象放入一个BlockingQueue的操作要发生在将对象从另一个线程中BlockingQueue移除操作之前

当队列容器已满，生产者线程会被阻塞，直到队列未满；当队列容器为空时，消费者线程会被阻塞，直至队列非空时为止。

ArrryBlockingQueue

由数组构成的有界阻塞队列。这是一个经典的“有界缓冲区”，其中固定大小的数组包含由生产者插入并由消费者提取的元素。容量一旦创建，就不能更改。将元素放入满队列的尝试将导致操作阻塞；从空队列中获取元素的尝试也将类似地阻塞。此类支持可选的公平策略，用于对等待的生产者和消费者线程进行排序。默认情况下，不保证此顺序。但是，在公平性设置为true的情况下构建的队列将按FIFO顺序授予线程访问权限。公平通常会降低吞吐量，但会降低可变性并避免饥饿。

对于并发的控制，使用ReentrantLock加上两个Condition条件控制的。在put和take操作的时候，都需要通过ReentranLock获取锁，最终调用实际的enqueue和dequeue，通过两个condition条件来传递信号。

1
2
3
4
5
6
7
8
9
10
11
12
13

/*
 * Concurrency control uses the classic two-condition algorithm
 * found in any textbook.
 */

/** Main lock guarding all access */
final ReentrantLock lock;

/** Condition for waiting takes */
private final Condition notEmpty;

/** Condition for waiting puts */
private final Condition notFull;

LinkedBlockingQueue

双锁算法的变体。putLock和takeLock在等待操作时候需要条件，由ReentrantLock进行实现，依赖count字段作为原子维护，以避免在大多数情况下需要同时获取两个锁。 这其实相当于有两个ReentrantLock和两个Contion条件来共同实现保证状态

提供读者和写着的可见性：当元素入队时，putLock获取锁并更新count，后续的读者通过putLock或者takeLock获取入队节点的可见性，读者n = count.get()，这将获取前n个Node的可见性。

默认构建不设置大小，将会将capacity设置位Integer.MAX_VALUE，这也就相当于可以构建一个虚假意义的无界队列

1
2
3
4
5
6
7
8
9
10
11

/** Lock held by take, poll, etc */
private final ReentrantLock takeLock = new ReentrantLock();

/** Wait queue for waiting takes */
private final Condition notEmpty = takeLock.newCondition();

/** Lock held by put, offer, etc */
private final ReentrantLock putLock = new ReentrantLock();

/** Wait queue for waiting puts */
private final Condition notFull = putLock.newCondition();

PriorityBlockingQueue

这个不保证相同优先级的元素排序，如果需要排序，可以自定义辅助键来打破优先级。

由基于数组的二叉堆进行实现，用一个ReentrantLock锁来保护公共操作。在resize的时候，使用简单的自旋锁来保证take操作进行分配，这就避免了等待的消费者的一再等待随之而来的因素累积。

默认的情况下使用自然排序，也可以通过自定义类实现 compareTo方法来指定元素排序规则，或者初始化时通过构造器参数 Comparator来指定排序规则。

1
2
3
4
5
6
7
8

private static final int DEFAULT_INITIAL_CAPACITY = 11;

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// tryGrow的扩容数据
int newCap = oldCap + ((oldCap < 64) ?
                       (oldCap + 2) : // grow faster if small
                       (oldCap >> 1));

在使用tryGrow方法扩容的时候，目前容量小于64，那么就是2 * oldCap + 2，大于64的时候就是原来的1.5倍。

线程池

使用线程池的好处：

1. 降低资源消耗
2. 提高响应速度
3. 提高线程的可管理性

线程池大小的确定（n为内核数量，超线程那种）：

• CPU密集型$n+1$：因为消耗的时cpu资源，应该尽可能的增加计算机资源
• IO密集型$2n$：需要进行的大量的io操作，cpu的压力小，应该尽可能的利用io效率

Executor

基础

Executor接口并不是严格 要求异步执行，一般情况是任务在调用之外的线程中执行，许多Executor的实现对任务的调度情况加以限制。

执行的任务需要实现Runable和Callable接口。

主要由三部分构成：

1. 任务
2. Executor
3. 结果

阿里的开发建议上不允许使用Executors去创建线程池，原因如下：

1. FixedThreadPool和SingleThreadExecutor允许的等待队列是Integer.MAX_VALUE，会造成大量的线程堆积
2. CachedThreadPool和ScheduleldThreadPool允许创建为Intreger.MAX_VALUE数量的线程，极端环境下也能造成大量线程堆积

线程池解决了两个不同的问题：

1. 由于减少了每个任务的调用开销，它们通常在执行大量异步任务时提高了性能，并且它们提供了一种绑定和管理执行任务集合时消耗资源的方法
2. 维护一些基本统计信息

提供了了一下几个工厂方法，底层是基于ThreadPoolExecutor实现的：

1. Executors.newCachedThreadPool无界线程池，具有自动线程回收的功能。从源码上看，corePoolSize被设置为0，maximumPoolSize被设置为Integer.MAX_VALUE ，keepalive被设置为60，工作队列用SynchronousQueue实现。当提交的任务速度大于执行任务的速度时候，就会导致不断创建工作线程，最终导致cpu和内存资源耗尽。
2. Executors.newFixedThreadPool创建固定线程数量的线程池。从源码可以看出，corePoolSize和maximumPoolSize都是传入的nThreads，然后执行的workQueue是LinkedBlockingQueue。不推荐的原因是他的等待队列是默认构造的LinkedBlockingQueue并且corePoolSize和maximumPoolSize相等的原因，导致不可能存在任务队列满的情况，keepAliveTime被设置为0，等待队列默认数量是Intger.MAX_VALUE，极端情况下会占满整个workQueue，最后导致oom
3. Executors.newSingleThreadExecutor，从源码可以看出，corePoolSize和maximumPoolSize都是1，工作队列使用LinkedBlockingQueue来实现，keepalive被设置为0，所以也会和Executors.newFixedThreadPool一样造成oom

推荐使用ThreadPoolExecutor去创建线程池

ThreadPoolExecutor

构造

其构造原理比较简单，就是些赋值操作，但是以下参数比较重要

1. corePoolSize：定义了最小可以同时运行的线程数量

2. maximumPoolSize：线程池中允许的最大线程数量

3. workQueue：在执行当前任务前会判断是否达到最大线程数量，达到就被存放到队列中

4. handler：拒绝异常处理器，用于处理当前线程池达到最大执行容量，workqueue也满的情况

   这个接口有四个实现类，代表了四种处理策略，实现的四个类作为ThreadPoolExecutor的四个内部类

   

   1. AbortPolicy：抛出RejectedExecutionException，这个是默认的拒绝测率
   2. CallerRunsPolicy：调用线程的execute方法执行代码，如果executor关闭，则丢弃任务
   3. DiscardOldestPolicy：丢弃最早未处理的线程
   4. DiscardPolicy：不处理新任务，直接丢弃

对于可伸缩的应用程序，最好使用CallerRunsPolicy策略。

原理

使用ReentrantLock作为全局锁来控制并发

在一个新任务提交时，运行的corePoolSize小于corePoolSize时，即使其他任务存在空闲，一个新线程将被创建用于执行该任务。当运行的线程数大于corePoolSize小于maximumPoolSize时，则只会在workQueue满的时候才会创建新的线程。

默认情况下，即使是核心线程也只在新任务到达时初始创建和启动，但是可以使用prestartCoreThread或prestartAllCoreThread方法动态覆盖。

默认使用ThreadFactory创建新线程。如果未另行指定，则使用Executors.defaultThreadFactory，它创建的所有线程都位于同一ThreadGroup中，并且具有相同的NORM_PRIORITY优先级和非守护进程状态。

可以阅读ThreadPoolExecutor的execute的代码，在开头的注释中，将整个执行过程分成了三个步骤：

1. 如果正在运行的线程少于corePoolSize，则调用addWorker(command,true)增加一个线程，并使用此线程运行任务
2. 任务已经排队成功，也就是运行任务数量大于corePoolSize，则先要判断当前线程池是否关闭，然后还得再次获得线程池状态，如果线程池不是RUNNING状态则要从任务队列中移除任务，还得检查线程是否全部执行完毕，同时执行拒绝操作，还得检查线程池是否为空，为空则增加线程
3. 无法将任务放入队列，则尝试使用addWorker添加一个线程，如果失败通过reject()执行相应的拒绝策略

常见对比

Runable和Callable

Runable不返回结果或抛出检查异常

Callable返回结果和异常

execute和submit

execute用于提交不需要返回值的任务，所以无法判断任务是否呗线程池执行与否

submit用于提交需要返回值的任务，线程池会返回一个Future对象

shutdown和shutdowNow

shutdown（） :关闭线程池，线程池的状态变为 SHUTDOWN。线程池不再接受新任务了，但是队列里的任务得执行完毕。

shutdownNow（） :关闭线程池，线程的状态变为 STOP。线程池会终止当前正在运行的任务，并停止处理排队的任务并返回正在等待执行的 List<Runable>，除了尽力尝试停止处理正在积极执行的任务之外，没有其他保证。此实现通过Thread.interrupt取消任务，因此任何无法响应中断的任务都可能永远不会终止。

ScheduledThreadPoolExecutor

主要用来在给定的延迟后运行任务，或者定期执行任务。但是在实际业务中，会使用Quartz等调度框架。

原理

此类通过以下方式实现ThreadPoolExecutor：

1. 使用自定义类型的ScheduledFutureTask
2. 使用自定义无界DelayQueue的变种DelayedWorkQueue，与ThreadPoolExecutor相比，corePoolSize和maximumPoolSize相同有效简化了一些相同的执行机制
3. 支持可选的关机后运行参数
4. 允许拦截和插装的任务修饰方法

在构造方面，corePoolSize是传入的构造，maximumPoolSize则是被设置为Integer.MAX_VALUE，keepalive为0，这就导致了在极端情况下，也就是提交任务的速度一直大于线程池中执行线程的速度，就会一直新增工作线程，导致耗尽系统资源。

使用DelayedWorkQueue作为任务的排队队列，是一个基于堆的数据结构，每个ScheduledFutureTask还要将其索引记录到堆数组中

执行过程

1. 当调用scheduleAtFixedRate方法时，会构建一个ScheduledFutureTask对象并添加到DelayedWorkQueue中，期间使用decorateTask将其转换成RunnableScheduledFuture对象
2. 使用delayedExecute获取DelayedWorkQueue中的任务，然后执行

同类的多个线程共享堆的方法区，但每个线程拥有自己的程序计数器、虚拟机栈和本地方法栈。

死锁的形成一定能在状态上找到一个环，可以参考死锁产生的必要条件：1. 互斥条件；2.请求与保持；3.不剥夺条件；4.循环等等

从底层看sleep是将线程退出临界区，他一定会再次进入临界区，所以不会释放锁；而wait方法也是退出执行，但是他不一定会再次使用，如不释放锁则会造成死锁，所以要将锁释放；其主要区别是再与语义实现上。

用start方法开启线程会使线程进入就绪状态，而run从语义上是立即执行，相当于直接在当前线程执行代码。

Runnable 接口不会返回结果或抛出检查异常，但是Callable接口可以。所以，如果任务不需要返回结果或抛出异常推荐使用Runnable接口，这样代码看起来会更加简洁。工具类Executors可以实现Runnable对象和Callable对象之间的相互转换。

查看AbstractExecutorService接口的submit方法，可以看到调用newTaskFor的方法返回了一个FeautreTask对象，而execute则是执行相关代码

synchronized

synchronizied早期属于重量级锁，其使用监视器锁进行实现，监视器锁利用系统的信号量实现，所以在使用过程中必然包含大量的上下文切换操作。

其在修饰静态方法时，由于静态方法属于类，所以实际是给类上了锁。

同步语句块

通过简单的demo，并且进行反编译class文件，我们可以看到明显的两个指令monitorenter和monitorexit，这中间包裹的就是同步代码块。

修饰方法

使用ACC_SYNCHRONIZED来表明这是一个同步代码块，在调用方法时就开始同步

和ReentrantLock的比较

1. 两个都是可重入锁，也就是不会堵塞其他线程获取锁
2. synchronized依赖于jvm实现，从class文件可以看出；ReentrantLock依赖于API，灵活度较高，所以可以实现
   1. ReentrantLock提供了能够中断等待锁的线程机制
   2. ReentrantLock可以构建是公平锁还是非公平锁
   3. 可以选择性通知，通过condition类可以很好实现选择性通知

和volatile对比

首选我们得先确定volatile不是一个锁，只是一个同步语义操作，目的是为了防止含有此修饰操作的指令重排，所以在没有锁的特性的情况下会有部分锁同步的特性，所以具体的有一下不同

1. volatile是线程同步的轻量级别实现，性能比synchronized好，但是不能替代，毕竟场景不一样
2. 由于只是一个同步操作，所以不会发生阻塞（毕竟底层只是防止了指令的重排），而synchronized是一个锁，所以会发生阻塞
3. volatile是同步语义操作，所以只能保证可见性，但是不能保证原子性
4. volatile防止了指令重排，虽然重线程层面是多线程操作，但是从内部操作看，其防止指令重排强制线程对数据的访问变成有序的，所以只能作用于变量上面；而synchronized是一个锁操作，其虽然依赖于系统的信号量实现，但是其目的是保证资源同步，相当于强制要求多个线程对资源访问是有序的。

ThreadLocal

从类注释中，可以得到其提供了一个线程访问局部变量的工具，每个访问变量的线程都有自己独立初始化的变量副本。实例通常放在与之管理的私有化的静态域中。当每个变量访问结束后，这个变量都会被回收，除非还有其他引用没有结束。

原理

对于其如何发挥作用的，得先从get方法看起，在获取当前线程后，用getMap来获取具体的线程实例，通过getMap方法，我们来到了Thread类中维护的threadLocals变量，这个时候就会发现这个地方维护了一个定制化的map来存数据，用this来得到当前线程的变量副本，这里的this表示的是当前线程对threadlocal的引用，不为空就返回。为空就说明是第一次调用，去进行初始化操作，对于set方法也是一致的，只有某一个线程第一次调用get或set才会对其进行初始化操作。

然后通过set方法，可以确定threadlocalmap的key是线程的引，只有第一次调用才会去创建map。get方法的初始化在map创建后，会用null作为值，没创建调用createmap构建ThreadLocalMap。

综上，可以看出值是存储在ThreadLocalMap中，而这个值维护在Thread中，而不是将值存在ThreadLocal里面，这只是做了个引用。

内存泄漏

因为ThreadLocal是以类本身作为key存入ThreadLocalMap中，ThreadLocalMap的Entry在源码上是一个WeekRefrence的修饰，是个弱引用，所以当一个使用ThreadLoal的线程使用结束，这个时候如果被gc，会出现key为null的情况，最后导致这个ThreadLocal容器一直都不会被回收。所以为了解决这个问题，get、set以及remove都会调用expungeStaleEntry清除null为键值的数据。

Executors

阿里的开发建议上不允许使用Executors去创建线程池，原因如下：

1. FixedThreadPool和SingleThreadExecutor允许的等待队列是Integer.MAX_VALUE，会造成大量的线程堆积
2. CachedThreadPool和ScheduleldThreadPool允许创建为Intreger.MAX_VALUE数量的线程，极端环境下也能造成大量线程堆积

ThreadPoolExecutor

正确环境下我们应该使用这个方法去创建线程池

构造

其构造原理比较简单，就是些赋值操作，但是以下参数比较重要

1. corePoolSize：定义了最小可以同时运行的线程数量

2. maximumPoolSize：线程池中允许的最大线程数量

3. workQueue：在执行当前任务前会判断是否达到最大线程数量，达到就被存放到队列中

4. handler：拒绝异常处理器，用于处理当前线程池达到最大执行容量，workqueue也满的情况

   这个接口有四个实现类，代表了四种处理策略，实现的四个类作为ThreadPoolExecutor的四个内部类

   

   1. AbortPolicy：抛出RejectedExecutionException，这个是默认的拒绝测率
   2. CallerRunsPolicy：调用线程的execute方法执行代码，如果executor关闭，则丢弃任务
   3. DiscardOldestPolicy：丢弃最早未处理的线程
   4. DiscardPolicy：不处理新任务，直接丢弃

对于可伸缩的应用程序，最好使用CallerRunsPolicy策略。

原理

可以阅读ThreadPoolExecutor的execute的代码，在开头的注释中，将整个执行过程分成了三个步骤：

1. 如果正在运行的线程少于corePoolSize，则调用addWorker(command,true)增加一个线程
2. 任务已经排队成功，则先要判断当前线程池是否关闭，然后还得再次获得线程池状态，如果线程池不是RUNNING状态则要从任务队列中移除任务，还得检查线程是否全部执行完毕，同时执行拒绝操作，还得检查线程池是否为空，为空则增加线程
3. 无法将任务放入队列，则尝试添加一个线程，如果失败通过reject()执行相应的拒绝策略

Atomic类

原理

核心原理用AtomicIntenger来分析，其主要在初始化的利用unsafe类工具，使用cas+volatile来保证方法的原子操作，利用objectFieldOffset这个方法直接从内存中获取存储值的地址，从而直接获取导致，另外用volatile进行修饰以组织指令重排而强制让访问此变量的是顺序的。

1
2
3
4
5
6
7
8
9
10
11
12

// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;

static {
    try {
        valueOffset = unsafe.objectFieldOffset
            (AtomicInteger.class.getDeclaredField("value"));
    } catch (Exception ex) { throw new Error(ex); }
}

private volatile int value;

AtomicStampedReference

AtomicStampedReference内部维护一个Pair类，通过此类内部stamp来表示修改状态，以此来解决ABA问题

1
2
3
4
5
6
7
8
9
10
11

private static class Pair<T> {
    final T reference;
    final int stamp;
    private Pair(T reference, int stamp) {
        this.reference = reference;
        this.stamp = stamp;
    }
    static <T> Pair<T> of(T reference, int stamp) {
        return new Pair<T>(reference, stamp);
    }
}

AtomicMarkableReference

同AtomicStampedReference一样内部维护了一个Pair类，但是用Boolean 值mark作为修改标识，只有两个版本，这知识降低了ABA问题发生的概率，但是不能彻底解决

1
2
3
4
5
6
7
8
9
10
11

private static class Pair<T> {
    final T reference;
    final boolean mark;
    private Pair(T reference, boolean mark) {
        this.reference = reference;
        this.mark = mark;
    }
    static <T> Pair<T> of(T reference, boolean mark) {
        return new Pair<T>(reference, mark);
    }
}

线程安全，在类注释中就直接表面这个是为了替代HashTale来实现的，并且兼容HashTable的操作方法。

1.7版本

内部维护了一个Segment的内部类，通过继承ReentrantLock来实现，为了简化一些锁操作，避免单独的构造。Segment维护了一个entry列表来保持一致性，所以可以在读的时候无锁，然后再segment的内部使用hashentry数组来维护数据。

初始化

大体步骤如下：

1. 参数校验
2. 计算掩码，偏移量操作，默认构造掩码是15，偏移量28
3. 初始化，segment的容量是sszie,是通过循环左移1，直到找到一个小于concurrentLevel附近的数,
   1. Segment[0]的HashEntry[]大小是cap,通过initialCapacity / ssize计算得到c，然后移循环左移找到数据，其是又是一个小于c附近的2的幂次值
   2. Segment[]的大小是sszie
   3. 将s0放到ss中是通过unsafe类的putOrderedObject操作实现的

初始化segment[0]，默认为2，负载因子是0.75，扩容的阈值就是1.5，只有插入第二个数值的时候才会扩容。

put操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because ConcurrentHashMap uses power-of-two length hash tables,
 * that otherwise encounter collisions for hashCodes that do not
 * differ in lower or upper bits.
 */
private static int hash(int h) {
    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

在此版本中的hash算法，当然也就要传入调用hashcode方法后的值，也是遵循着冲突容易发生在低位，所以用移位，异或，求和操作得到一个值，最后再与自己右移16的数进行异或操作得到最终的哈希值。

对于存储在哪个segment位置的计算，在使用默认的构造情况下，相当于将hash值右移28位后再与掩码15进行与运算。

在发现插入位的segment为null的时候，调用ensureSegment操作进行初始化，对于这个初始化，流程大体如下：

1. 从0中获取初始化长度作为cap
2. 从0中获取负载因子
3. 计算扩容阈值
4. 创建一个cap容量的HashEntry数组

这个操作类似构造器初始化的时候创建segment[0]的数据，当然不同的是，在这个操作中，会利用unsafe类中的自旋操检测是否还是null，然后再使用unsafe类的cas操作。

在最后插入值的时候，首先是使用tryLock获取锁，未活得则调用scanAndLockForPut方法自旋的获取锁，超过Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1的时候就使用lock()强制获取锁。

使用(tab.length - 1) & hash计算出插入的位置，对这个HashEntry链表进行遍历：

1. key存在，直接替换
2. 不存在，接着遍历
   1. 容量不够，扩容，也就是移动到了扩容位
   2. 移动到最后，也就是key不存在，也扩容结束，就使用头插法插入数据

扩容rehash

从注释和实际代码中，我们可以看到，扩容是直接扩容为原来的2倍，老数组里的数据移动到新的数组中的时候，要么不变，要么是index+oldsize，最后用头插法插入新节点。

1.8版本

当然和同版本的HashMap一样，修改成了链表变红黑树的实现，对于位置从原来的segment修改成了node数组。对于构造器，只是申明的大小，只有在插入数据的时候才会去开辟空间。

在操作前面有tabAt，casTabAt和setTabAt三个前置操作，进行数据可见性的操作，setTabAt操作始终锁定在锁定区域内进行，因此只要求发布顺序。

对于hash函数，其与HashMap不同，是在右移16，减少冲突后，然后在与本身进行异或操作，这个适合会出现负数请求，所以再与0x7fffffff进行并操作后，就能获取正数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Spreads (XORs) higher bits of hash to lower and also forces top
 * bit to 0. Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

get操作

在get操作的适合，使用tabAt来进行可见性操作。其原理比较简单，根据哈希值和tabat找到node节点，头简单就是就返回，是红黑树就用find函数查找，是链表就遍历查找。

put操作

当添加到table表空间点的时候：

1. 为null，也就刚申明好，这个时候使用initTable调用进行空间的开辟
2. 桶内为空，也就是刚初始化好，进行的第二次循环，这个时候直接使用cas操作放入数据
3. 当当前位置的hashcode == MOVED == -1就进行扩容，和之前的tabat操作有关
4. 代码顺序，在tabat操作的时候已经找到了需要插入node节点的位置，在下一次循环的时候就可以进行真实的数据插入操作；
   1. 直接使用synchronized锁住当前节点
   2. 再次使用tabat进行同步，fh值是通过hash得到的，为正数的时候说明还是最初的列表，然后在次节点链表中进行遍历，同时进行bincount的自增操作，key相同则替换数据，移动到末尾则插入数据
   3. 如果是红黑树，则使用红黑树的插入操作。
5. 最后检查bincount的值，大于树化阈值则进行书化操作

remove操作

通过浏览remove的代码，可以看到大体逻辑和put操作类似，但是可以发现，在红黑树删除的代码里面，有这么一行setTabAt(tab, i, untreeify(t.first));，也就是说当冲突减小到阈值的时候，又会变为链表。

1.8之前是数组+链表构成，1.8改成了当阈值为8的时候，将链表转换为红黑树（当链表长度小于64的时候是会进行扩容而不是直接转红黑树），在键值上运行使用null作为键值，

1.7版本

创建的默认值是16，如果指定大小，则从1开始向左移位移循环，直到找到一个$2^n$数字大于或等于初始化容量大小作为构建的容量。

对于哈希函数，要求传入的是对象的hashcode()方法的值，对其进行一个补充的哈希计算，防止出现劣质的哈希值（也就是冲突较大，哈希后的数值分布不均匀），在注释中可以看到hashmap用的2的幂次方的哈希表，容易在地位出现冲突，null的作为key用于返回0哈希值。其在使用异或操作和右移操作确保每个位置仅有一定数量的冲突。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

因为1.7的代码中解决冲突的方式很暴力，就直接使用链地址法（也就是拉链法），再用indexFor找到要放置的链表位置，遍历查找是否有已经存在，最后在数组中指定位置插入数据，如果超过数组的存储阈值就直接扩大两倍然后拷贝到新数组中。

删除操作也是也是直接通过indexFor函数查出存在哪个bucket中，然后再其中进行遍历查找出数据进行删除。

1.8版本

对于使用默认无参的构造器进行构建，则在初始化容量的时候会使用tableSizeFor进行操作。tableSizeFor使用移位和异或操作进行实现的，相比于1.7的版本，其在获取数据的时候是常数级别的。

因为冲突经常发生在最低位，所以1.8处理的方式比较简单，直接右移16位，将高位移动到地位，这样在哈希算法寻找位置的时候冲突较低。

在添加元素的时候，当第一次添加元素的时候才会在添加位置创建链表分配空间，然后才进行数据的插入，此时被分为了三种情况：

1. 元素本身就是链表头节点，那直接进行后续的操作
2. 需要插入的节点是红黑树，那走红黑树的插入
3. 插入节点还是普通列表，会遍历该节点，查找是否存在同key的，有就跳出进行后续的操作，否则继续寻找，直到走到末尾节点，此时如果已经超过了默认的8个元素，就会调用treeifyBin进行数化（在此函数中会判断table数组大小是否超过64，只有超过64的时候才会进行当前树化，否则只会进行当前节点的扩容）

在扩容的resize的代码注释上写着，扩容后，要么保持在相同的索引位置，要么就要移动到新表中2次幂的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

1、两数之和

方法一 暴力循环法

直接利用两次循环解决问题

方法二 两次哈希

1. 遍历数组，构建Map，下标作为value
2. 再次遍历数组，用target减去当前值做键去寻找数据，要排除获取的数组下标就是当前值的情况

方法三 一次哈希

从哈希表中取出的数据就是正确答案，否则无答案：

1
2
3
4
5
6
7
8
9
10
11
12

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> targetMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int key = target - nums[i];
        if (Objects.nonNull(targetMap.get(key))) {
            return new int[]{i, targetMap.get(key)};
        }
        targetMap.put(nums[i], i);
    }

    throw new IllegalArgumentException("错了啊");
}

6、Z字形变化

由上图可以看出，以每个竖列加中间数据作为一组，可以确定每组可以放$2n-2$个数据，这个时候就能取模获得在数组中的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public String convert(String s, int numRows) {
    // 处理边界
    if (1 == numRows) {
        return s;
    }

    String[] result = new String[numRows];

    // 默认数组初始会以null填充
    Arrays.fill(result, "");

    char[] stTemp = s.toCharArray();
    int period = numRows * 2 - 2;

    for (int i = 0; i < stTemp.length; i++) {
        int mod = i % period;
        // 在row里面，直接存指定位置
        if (mod < numRows) {
            result[mod] += stTemp[i];
        } else {
            // 已经超过，直接减去就能找到正确位置
            result[period - mod] += stTemp[i];
        }

    }

    return String.join("", result);
}

14、最长公共子前缀

初始化结果为默认的第一个字符串，对给定的字符串数组进行遍历，每次对字符串中的字符与结果字符串的相同位置进行比较，遇到不同则截断字符串，最后返回（要处理给定字符串数组为空的边界条件）

相当于每次都是当前字符串与结果字符中的字符一一比较

15、三数之和

1. 先进行排序
2. 遍历数据，每次固定当前值，计算剩下两个数的目标和
3. 对接下来的数据进行双针扫描，如果结果比计算值少，则移动左指针，扩大数据；结果过大，则移动右指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    ArrayList<List<Integer>> result = new ArrayList<>();
    // 固定尾部，移动头部
    for (int i = 0; i < nums.length; i++) {
        int value = -nums[i];
        int lp = i + 1;
        int rp = nums.length - 1;
        // 因为排序，当这个只大于0就没有继续的必要
        if (0 < nums[i]) {
            break;
        }
        // 数据在一起
        if (lp != rp && (i == 0 || nums[i] != nums[i - 1])) {
            while (lp < rp) {
                if (nums[lp] + nums[rp] == value) {
                    result.add(Arrays.asList(nums[i], nums[lp], nums[rp]));
                    lp++;
                    rp--;
                    while (lp < rp && nums[lp] == nums[lp -1]) {
                        lp++;
                    }
                    while (lp < rp && nums[rp] == nums[rp + 1]) {
                        rp--;
                    }

                } else if (nums[lp] + nums[rp] < value) {
                    lp++;
                } else {
                    rp--;
                }
            }
        }
    }

    return result;
}

26、删除排序数组中的重复项

双针法解决，一个指针表示当前已经不重复的元素的位置，另外一个为遍历指针，数据相同移动遍历指针，数据不同交换数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public int removeDuplicates(int[] nums) {

    int interval = 0;

    for (int i = 1; i < nums.length;) {
       if (nums[interval] == nums[i]) {
           i +=1;
       } else {
           nums[interval + 1] = nums[i];
           interval +=1;
       }
    }
    return interval + 1;
}

27、原地删除

1. 遍历数组，每次都将当前数据移动到正确位置
2. 并记录出现关键值的次数
3. 最后数组长度减去关键值次数并返回

1
2
3
4
5
6
7
8
9
10
11
12

public int removeElement(int[] nums, int val) {
    int interval = 0;

    for (int i = 0; i < nums.length; i++) {
        if (val == nums[i]) {
            interval += 1;
        }else {
            nums[i - interval] = nums[i];
        }
    }
    return nums.length - interval;
}

66、加一

三种情况：

1. 末尾加一不用进位
2. 末尾加一只用进一位
3. 全是9的情况

解决方法如下：

1. 申明进位数据，默认为0，因为刚开始的时候不用进位
2. 处理末尾自增
3. 处理自增后还需要进位的情况
4. 处理首位要自增构建新数组的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public int[] plusOne(int[] digits) {
    int addon = 0;
    for (int i = digits.length - 1; i >= 0; i--) {
        digits[i] += addon;
        addon = 0;

        // 先处理最后一位
        if (digits.length - 1 == i) {
            digits[i] += 1;
        }

        // 处理需要进位的情况
        if (digits[i] == 10) {
            addon = 1;
            digits[i] %= 10;
        }
    }

    // 处理最后首位需要进位的情况
    if (1 != addon) {
        return digits;
    }

    int[] result = new int[digits.length + 1];
    result[0] = 1;
    System.arraycopy(result, 1, digits, 0, digits.length);
    return result;
}

122、买卖股票的最佳时机II

最中要的限制就是不能在同一天买入和卖出，所以这个时候在画出每一天的数据的折线图后，就有以下解决办法：

方法一 连续递增的端点

此方法认为在递增段上获取利润，所以

1. 遍历给定数据
2. 遇到增长就计算利润：

1
2
3
4
5

for (int i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i -1]) {
        maxprofit += prices[i] - prices[i - 1];
    }
}

方法二 计算每次波谷和波峰的利润

就是每次先波谷买入，波峰卖出:

1. 遍历数据
   1. 先找波谷
   2. 再找波峰
   3. 波峰 - 波谷
2. 重复以上过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

for (int i = 0; i < prices.length; i++) {
    // 计算波谷
    while (i < prices.length - 1 && prices[i] >= prices[i + 1]) {
        i++;
    }
    int minIndex = i;

    // 计算波峰
    while (i < prices.length - 1 && prices[i] <= prices[i + 1]) {
        i++;
    }
    int maxIndex = i;

    maxprofit += prices[maxIndex] - prices[minIndex];
}

189、旋转数组

两个前置条件：

1. 数组长度为空或者一的时候直接返回原数组
2. 当移动长度大于数组长度的时候要以数组长度取模k % nums.length

方法一 反转数组

移动数组k次，相当于将数组尾部的k个元素移动到数组头部，所以方法如下：

1. 反转整个数组
2. 反正0到k个数组元素
3. 反正k后的数组元素

反转数组的代码如下：

1
2
3
4
5
6
7

public void reverse(int start, int end, int[] nums) {
    for (int i = 0; i < (end - start) / 2; i++) {
        nums[i + start] += nums[end - i - 1];
        nums[end - i - 1] = nums[i + start] - nums[end - i - 1];
        nums[i + start] = nums[i + start] - nums[end -i -1];
    }
}

方法二 环状替代

直接交换两个元素，当形成环的时候结束，如果还有没有交换过的元素，则偏移后进行下一次循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int count = 0;
for (int i = 0; count < nums.length; i++) {
    int current = i;
    int prevValue = nums[current];
    do  {
        int prev = (current + k) % nums.length;

        int temp = nums[prev];
        nums[prev] = prevValue;
        prevValue = temp;

        current = prev;
        count++;
    } while (i != current);
}

350、两数组交集II

方法一 构建Map的方式

1. 交换两数组，将长度小的交换的到前面（减少空间）
2. 初始化Map并遍历第一个数组，并统计每个数字出现的频率
3. 遍历第二个数组，并与Map的键值对比，不存在继续；若存在，则输出到第一个数组种，并让下标index偏移

方法二 交替遍历

1. 对两个数组进行排序

2. 对两个数组交替进行遍历，遇到相同则记录，核心代码如下

   1 2 3 4 5 6 7 8 9 10 11 12

   while (i < nums1.length && j < nums2.length) { if (nums1[i] > nums2[j]) { j++; } else if (nums1[i] < nums2[j]) { i++; } else { nums1[k] = nums1[i]; i++; j++; k++; } }

底层使用Object[]实现，操作受到底层数组实现的限制，在指定位置插入和删除元素的操作的时候会大量消耗性能，在末尾插入唯一消耗性能的是扩容，所以最好能在使用前预估好大小。

因为是基于数组实现的，其更符合计算机底层，其在内存上是连续排布，所以在获得内存地址加偏移后能很快的获取指定元素，所以支持高效的随机元素访问。

RandomAccess

这个接口的主要作用就是标识实现此接口的类具有随机访问能力（也表明其更贴近计算机的底层实现），当容器类实现此接口的时候，fori循环的速度会快于iterator的遍历，因为其相当于直接在内存上递增查找。

例如使用Collections.binarySearch() 方法时候，容器类本身实现RandomAccess，则会走indexedBinarySearch()获取更高的性能，否则则会走iteratorSearch()

扩容

默认的元素大小是 10，在不指定大小的情况下调用重载的构造器构造默认大小为 10 的空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，在指定大小为 0 的时候直接使用用于共享的空数组实例EMPTY_ELEMENTDATA，所以在默认情况下，只有在插入数据的时候才会构建，不然都是使用方法本身提供的共享空数组实例。从Collection对象中构建，先使用toArray方法直接转换，如果容量为 0 则用EMPATY_ELEMENTDATA替换原实例，否则在不是ArrayList对象则用Arrays.copyOf()方法转换后替代并保持原顺序。

1.8 的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

  /**
   * Appends the specified element to the end of this list.
   *
   * @param e element to be appended to this list
   * @return <tt>true</tt> (as specified by {@link Collection#add})
   */
  public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      elementData[size++] = e;
      return true;
  }

private void ensureCapacityInternal(int minCapacity) {
      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          return Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      return minCapacity;
  }

private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }

  /**
   * Increases the capacity to ensure that it can hold at least the
   * number of elements specified by the minimum capacity argument.
   *
   * @param minCapacity the desired minimum capacity
   */
  private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      // minCapacity is usually close to size, so this is a win:
      elementData = Arrays.copyOf(elementData, newCapacity);
  }

private static int hugeCapacity(int minCapacity) {
      if (minCapacity < 0) // overflow
          throw new OutOfMemoryError();
      return (minCapacity > MAX_ARRAY_SIZE) ?
          Integer.MAX_VALUE :
          MAX_ARRAY_SIZE;
  }

默认直接空构造ArrayList，首先调用ensureCapacityInternal进行容量大小的判断；当添加第一个元素的时候，minCapacity为 1，DEFAULT_CAPACITY为 10，最后此方法会返回 10；调用ensureExplicitCapacity方法，minCapacity - elementData.legth > 10成立，调用grow方法，第二个元素的时候这两个值相同，不会调用grow方法；grow 的方法直接将容量进行右移一位的操作（右移 n 位相当于$原数据\times2^n$），此时新的容量为此前的 1.5 倍左右，小于最小值的时候直接用最小值替代扩容值（这个地方一般出现在指定初始化容量小于DEFAULT_CAPACITY或者是空构造添加第一个元素的时候）

hugeCapacity对于溢出的限制，当前minCapacity还是比数组最大值小的时候为数组最大值，否则为整数最大值；当扩容到INTEGER.MAX_VALUE的情况下，在下一次增加元素的情况下，minCapacity已经溢出，这个时候余下两个判段都会进入，最后抛出OutOfMemoryError错误。

Arrays.copyOf的内部调用System.arrayCopy进行实现，copyOf的目的是拷贝原数组指定容量的数据，并返回新数组；而System.arrayCopy是一个native方法，主要是拷贝指定数组的指定数据到目标数组，所以copyof内部用此来实现高效的数组拷贝。]

modCount的作用：这是来源于AbstractList的一个变量，用来表示当前列表被操作的次数，使用这个数据可以进行快速的判错，入iterator用此来判断是否被修改而抛出异常。

ensureCapacity这个方法是提供给使用者使用的，如果在初始化的时候没有创建合适的容量，可以在向其添加数据前调用此方法用以扩容到合适的容量，以减少增加过程中的扩容消耗，其也是调用ensureExplicitCapacity来实现扩容

1.11 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

  /**
   * Appends the specified element to the end of this list.
   *
   * @param e element to be appended to this list
   * @return {@code true} (as specified by {@link Collection#add})
   */
  public boolean add(E e) {
      modCount++;
      add(e, elementData, size);
      return true;
  }

private void add(E e, Object[] elementData, int s) {
      if (s == elementData.length)
          elementData = grow();
      elementData[s] = e;
      size = s + 1;
  }

核心的扩容原理没有改变，只是前置条件改了，当插入位置已经和原有列表长度一直的时候就扩容，减少了判断次数，删除了ensureExplicitCapacity和ensureCapacityInternal方法。

删除操作

包含两种删除操作，下标的操作直接用System.arraycopy进行一个本身到本身的拷贝，相当于将目标下标后的元素进行整体移动，时间复杂度为$O(n-i)$;而元素移除的操作需要先遍历查找元素的下标，然后调用fastremove使用下标进行移除，这个地方也要进行下标后的数据前移

圆圈正义

能否增进人的幸福 (快乐)。但是“幸福”这个词语本身是模糊的。边沁认为, 幸福没有高下之分, 口腹之欲和心智之养没有区别。如果人只根据自己的经验计算利害得失, 不可避免地会走向庸俗。这种功利观一定会让人追求现实的快乐, 追逐眼前的利益, 在勇敢和懦弱之间, 后者往往是最佳的选择。

但是穆勒却认为, 幸福是有高下之分的。 “做一个不满足的人, 胜于做一只满足的猪; 做不满足的苏格拉底, 胜于做一个满足的傻瓜。如果那个傻瓜或猪有不同的看法, 那是因为他们只知道自己那个方面的问题, 而相比较的另一方即苏格拉底之类的人, 则对双方的问题都很了解。”

当生命中缺乏一个终极的敬仰对象, 人就不可避免地会把自己置于生命中最重要的地位, 形成无法抑制的自恋。自恋让人总是自觉优越: 或是出生的优越、种族的优越, 或是智力的优越、知识的优越, 或是财富的优越、阶层的优越,或是地域的优越、口音的优越, 甚至是道德的优越、宗教的优越。正是这种自我的优越感使得人类冲突不断。无论是儒家的“华夷之辨”, 清政府的“非我族类, 其心必异”, 本质上都是人类自恋的产物。

已有的事, 后必再有; 已行的事, 后必再行。日光之下,并无新事。历史已经, 而且还将继续告诫我们, 国家权力绝不是完美无瑕的, 刑法也不应成为统治者任意操控的工具。刑法要追求公平和正义, 而不能唯权力马首是瞻。法律是对世俗社会的诫命, 它要约束包括统治者在内的一切权力。在这个意义上, 不是法律匍匐于权力之下, 而是权力在法律之下俯首称臣。

刑事法律要遏制的不是犯罪人,而是国家。

对别国经验的介绍并不是崇洋媚外, 一个伟大的民族从来都应以开放的心态去汲取一切人类的智慧成就。儒家的大同梦想从来都有兼济天下的胸怀, 而非在个别地域、个别族群制造地方性知识。法治是人类政治智慧的一大标志, 也是走向政治文明的必由之路。

法治必须约束权力, 保障自由。通俗地说, 国家只拥有法律所规定的权力, 而法律所不禁止的则是公民自由驰骋之地。当权力有其固定的边界时, 民众才能享有法律所赋予的免于恐惧的自由。如若法外另有民众无法知悉内部规则, 人们也就无法形成合理的预期, 不可避免地会陷入未知的恐惧。

唯有真理的光照, 才能学会谦卑, 走出自我的偏狭, 从而自由而不放纵, 独立而不狂狷, 尽责而不懈怠。

真正的自由是做正确事情的自由, 随意吸毒不叫自由,可以控制自己不去沾染毒品才是自由。任意更换性伴侣, 始乱终弃不是自由, 可以约束自己的欲望才叫自由。百花争妍,但仍能忠于命定的那朵玫瑰, 才是真正的性自由。

大学之大, 不在大楼, 不在大师, 更不在大官, 而在伟大的观念。

司法实践中有些司法机关习惯性地认为, 民众必须接受法律所推行的价值观, 而忘记了法律的价值观本身来源于民众朴素的道德期待。法律只是道德的载体, 权力意志不能任意产生道德法则, 道德在法律之上, 法律及立法者的意志在道德之下。法律的超验权威不是人的理性所创造的, 而是写在历史、文化、传统和习俗中, 写在活生生的社会生活之中。

道德谴责的打开方式

真正的勇敢是要付出代价的, 不是敲敲键盘、唱唱高调就可以成为勇士。

愿我们每一个人都能成为真正的勇士。但, 愿我们每一个人都不要轻易遇到考验我们勇气的时候。

有人说, 法律人优点 (或是缺点, 端看你采取何种立场)之一, 便是他既不相信口号, 也不相信群众。那些立场鲜明、非此即彼的口号式论说最容易获得民心, 但这种单极化的思维在人类历史上却带来了无数浩劫。因此, 法律的训练让我对任何口号都心存警惕。

哈佛大学教授德肖维茨说: “一个国家是否有真正的自由, 试金石之一是它对那些为有罪之人、为世人不耻之徒辩护的人的态度。在大部分专制国家里, 独立自主的辩护律师队伍是不存在的。诚然, 专制压迫肆虐无忌的明显标志之一就是政府开始迫害辩护律师。”

身负权力各自珍重

已有的事, 后必再有; 已行的事, 后必再行。日光之下,并无新事。

法律人的理智和多数人的情感

法律的训练让我对曾经的侠客梦至少有两点反思: 首先,个体的认识能力是有限的, 有许多隐秘的事情我们并不知晓,因此个人对于正义的理解一定是片面的。凭借个体对正义的有限理解去“匡扶正义”很有可能出现灾难性的后果。其次,正常的社会并不是黑白分明、非此即彼的, 有时善与善也会发生冲突。人的有限性很容易让我们在自己所看重的事情上附上不着边际的价值。就如每一次虐狗事件中的人虐狗后会发生“狗虐人”——很多爱狗人士就把自己认为正确的价值无限放大。这就是唐朝魏征说的:“憎者唯见其恶, 爱者止见其善。爱憎之间, 所宜详慎。”

法治的根本前提就是对人类内心这种幽暗势力的预设。拥有的权力越大, 破坏的能力越强, 因此权力要受到法律严格的约束。人类的历史一而再再而三地告诫我们, 权力与德行绝非正相关关系。

法律人要用冷静的思维告诉民众, 死刑从来不能遏制犯罪, 反而会把人逼向绝路, 导致犯罪升级, 在某种意义上, 它制造了犯罪, 而不是减少了犯罪。

当双方存在信任关系, 一方很可能利用自己的优势地位对处于弱势地位的对方施加不正当的影
响, 利用对方在身体上和心理上的不利地位, 这种“同意”下的性明显是不正当的。

切斯特顿曾写下过这样一段话, 值得深思: “性滥交不是高估而是降低了性的价值, 抱怨只能结婚一次就像抱怨只能出生一次, 与当中涉及的无比兴奋绝不能相提并论。这个抱怨显示的不是对性的极端敏感, 而是异乎寻常的不敏感……性放纵是对性快乐的糟蹋, 是对性的缺乏认识, 就像一个人心不在焉地采下五颗梨子一样。”

生命的尊严

人类三种事情无法避免, 一是苦难, 二是死亡,三是邪恶。

很多时候人们并不知道如何选择,你不是遵循道义的指引, 就是按照国家意志来生活。无视道义约束的个人自由与漠视道义的国家意志不过是一体两面。

心怀永恒活在当下

宋朝皇帝真宗赵恒说得比大家更为直白: “富家不用买良田, 书中自有千钟粟;安居不用架高堂, 书中自有黄金屋; 出门莫恨无人随, 书中车马多如簇; 娶妻莫恨无良媒, 书中自有颜如玉; 男儿若遂平生志, 六经勤向窗前读。”

在我看来, 读书的真正目的是追求智慧, 而非单纯的知识, 从表面上来看, 读书是一个悖论: 让你在求知的过程中越来越觉得自己的无知。这就像苏格拉底所说的“承认自己的无知才是开启智慧的大门”。

很多人为了寻找爱情, 在不同的情人中周旋探索, 最后却是越来越觉得孤独。原因就在于, 自恋的爱永远不能长久, 任何一个人都无法达到你对他的全部预设。

原因

1. 开发过程很容易遇到需要导出数据进行分析的情况
2. 需要对导出的数据进行处理，如果不处理直接找一个RDMS软件进行处理就行
3. 使用Python+Pandas结合起来方便，代码量少，还能对导出的数据进行处理

环境依赖

以下是Pipfile中的文件

1
2
3
4
5
6

records = "*"
mysqlclient = "*"
pandas = "*"
sqlalchemy = "*"
pymongo = "*"
openpyxl = "*"

代码主体逻辑

1. 数据库连接
2. 需要执行的 SQL
3. 导出 Excel 或者迁移到其他数据库

代码示例

下面这段代码因为就一次使用，就没封装函数那些：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from sqlalchemy import create_engine
import pandas

client_db = create_engine(
    'mysql://username:password@host:port/database?charset=utf8mb4')

# TODO 在这写入合适的SQL
fr_sql = '''
'''

fr_df = pandas.read_sql(fr_sql, con=client_db)

# TODO 对导出数据的 DataFrame 进行处理和修改
for index, row in fr_df.iterrows():
    # 处理代码    

fr_df.to_excel('example.xlsx', index=False)

Feign From 的使用

建立一个feign的配置文件，并在其中写入如下代码：

1
2
3
4

@Bean
fun encoder(): Encoder {
    return FormEncoder()
}

然后在请求到接口上加入consumes = [MediaType.APPLICATION_FORM_URLENCODED_VALUE]，
对于请求到参数，使用model进行封装，然后使用map封装请求参数

feign 在 spring boot 2.0 中提示错误

当使用 Spring boot 2.0 的时候，idea 会提示无法注入，这个时候在client中加入
@Component注解就可以了

自动注入冲突

在使用Spring boot 2.0的时候，有可能会出现多个自动配置到Bean冲突到情况，这个
时候可以将不需要注入到Bean加入到spring.autoconfigure.exclude中就可以了，例如
consul和kubernetes冲突到情况，可以用如下设置：

1
2
3
4

spring:
  autoconfigure:
    exclude: 
      - org.springframework.cloud.kubernetes.discovery.KubernetesDiscoveryClientAutoConfiguratio

lombok 在 IDE 提示报错到情况

当出现lombok报错的时候，在 peferences -> build -> annotation processors 中设置

feign 的 name 同名提示报错

当在Spring boot 2.0使用feign的时候，使用Bean提示如下错误：

1
2
3
4
5
6
7

Description:

The bean Bean 的名称, defined in null, could not be registered. A bean with that name has already been defined in null and overriding is disabled.

Action:

Consider renaming one of the beans or enabling overriding by setting spring.main.allow-bean-definition-overriding=tru

此时，可以考虑如下两个解决办法：

1. 在配置文件中加入运行使用同名Bean的配置

   1 2 3

   spring: main: allow-bean-definition-overriding: true

2. 将每个Bean配置成不同的名称

Java 和 Kotlin 类型不兼容

在使用spring data redis允许lua脚本的时候会出现返回值是Int，然后在kotlin中出现了
类型不兼容的情况，这是因为kotlin中的Long指向的是Java中的long，并且在接口上做了不
可以为空判定，大部分情况下是可以兼容的，但是spring框架类中使用了反射强制获取了Java中
的Long类型，也就是在获取包装类型的情况下，只能强制指定返回的类型为包装类习惯，这
是因为在不指定的话默认的类型转换是不可空的，如下

1
2

java.lang.Long
java.lang.Long::class.java

简单的分布式锁的实现

实现分布式锁最简单的方式就是在reids中执行lua脚本，因为lua是单进程执行的，在不是
集群部署的情况下实现一个分布式锁或者进行分布式限流相对来说是比较简单的。当在系统
部署的时候使用了集群的方式，应该考虑的是数据在每个slot中同步的问题，一个简单的解
决办法是在少数节点只进行写入操作，在多数节点进行写操作。
在spring中，使用spring data redis对大部分的redis操作进行了封装，并且可以在使用集
群的情况下设置写入节点和读取节点，然后在其中对数据进行处理，所有的后续操作都要等
到redis中的数据真实有效变更后才能进行后续操作

Git 重置所有提交记录

基本思想是新建一个分支,然后把本地的master分支删了,然后重命名当前分支,具体操作如
下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 新建分支
git checkout --orphan latest_branch

# 进行提交
git add -A
git commit -am "commit message"

# 删除master分支
git branch -D master

# 重命名当前分支
git branch -m master

# 按需进行强制提交
git push -f origin master