Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
1 | $ hexo new "My New Post" |
More info: Writing
1 | $ hexo server |
More info: Server
1 | $ hexo generate |
More info: Generating
1 | $ hexo deploy |
More info: Deployment
通过N2N即可组成局域网，在外面可以访问家里的路由器、机器。
n2n有V1和V2两个版本， 两个版本不兼容，据说V1的性能还略高于V2,V2是增加了一些安全相关的提升。
所以我这里都是基于V1版本搭建的。
1 | $ git clone https://github.com/meyerd/n2n |
启动：
1 | $ nohup supernode -l 86 -v -f > supernode.log & |
####
1 | $ git clone https://github.com/meyerd/n2n |
这里我是在虚拟机中安装的Openwrt可以先下载虚拟机文件，虚拟机
http://downloads.openwrt.org/attitude_adjustment/12.09/x86/generic/openwrt-x86-generic-combined-ext4.vdi
安装与配置：
1 | $ opkg update |
启用，启动、停止：
1 | /etc/init.d/n2n enable |
参考文章：
前段时间看到了那篇为什么1000 == 1000返回为False，而100 == 100会返回为True?
1 | Integer a = 1000, b = 1000; |
一般你会拿到结果：1
2false
true
这里我强调了是在一般情况下，原文中并没有写到是一般，我们不更改代码，第一个a == b结果也可能返回true，修改jvm参数配置就可以达到这种效果，文章的最后我提供了测试代码。
其实出现不同的原因是在这里：
Integer a = 100 ==> 创建了Integer对象 Integer.valueOf(i)，方法经过判断会是下面两种情况的一种：IntegerCache.cache[n] new Integer(i)会有两种情况：一种会新建对象，一种返回一个缓存的对象
== 用来比较值的，对象的值是否相等请使用 obj.equals(o)，这里两个Integer对象使用==来比较本身就是一种“不正当使用”，对象==取的是对象内存地址。
下面我们看下这个IntegerCache.cache的缓存区间：
cache[]: final int low = -128 ， final int high: sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high"); or 127[-128...127]呢？个人认为可能主要有以下两个原因：
2^8，256个数字，带上符号就是 [-128…127]使用科学的方法来判断相等：
==.equals另外，如果你的程序比较特殊，有大量的 < 128 或 > 127 的数字存在，你可以尝试考虑调节下参数java.lang.Integer.IntegerCache.high，当然这是一种锱铢必较的手段，会带来一些交付上的问题，就是每个环境可能都要加上此配置，这里只是一种优化上的思路假设。
测试 场景：1 千万的 Integer数组，将每个设值为[0, 1000]的随机整数，对比初始时间、各代空间占比
总的对比结果如下（前者代表默认，后者代表–XX:AutoBoxCacheMax=1000）：
源码请看这里
再次读《大话数据结构》这本书，回过头再跟着书系统的走一遍，记录巩固下基础。
数据结构是相互之间存在一种或多种特定关系的数据元素集合。
物理结构是面向计算机的，逻辑机构是面向问题的。 其基本目标就是将数据及其逻辑关系存储到计算机的内存中。
数据在计算机内的存储形式，也称之为存储结构。
顺序存储 : 数据元素存放在地址连续的储存单元中。
链式存储: 把数据元素存放在任意的存储单元里。数据元素的存储关系不能反映其逻辑关系，需要指针存放数据元素的地址。
数据对象中数据元素之间的关系，逻辑结构分为以下四种：
集合结构：集合结构中的数据元素同属一个集合，他们之间没有任何关系。
线性结构: 线性结构中的数据元素之间是一对一的关系。
树形结构: 树形结构中的数据元素是一对多的关系。
图形结构: 图形结构中的数据元素是多对多的关系。
另外，我们用示意图表示数据的逻辑结构时，要注意两点：
数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
我的理解中，数据类型分一下：
对已有的数据类型进行抽象，就有了抽象数据类型。
抽象数据类型（Abstract Data Type, ADT）: 是指一个数学模型及定义在该模型上的一组操作，后面会用以下格式来表示抽象数据类型：1
2
3
4
5
6
7
8
9
10
11
12ADT 抽象数据类型名称
DATA
数据元素之间逻辑关系的定义
Operation
操作1
初始条件
操作结果描述
操作2
...
操作n
...
endADT
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
五个基本特性：输入、输出、有穷性、确定性和可行性
所谓“是骡子是马，拉出来溜溜”。比较容易想到的方法就是，通过对算法的数据测试，利用计算机的计时功能，来度量不同算法效率的高低，平常见到的benchmark就应该属于此类。
为了对算法的评判更加科学，计算机前辈们研究出一种叫做事前分析估算的方法。事前分析估算方法：在计算机程序编制之前，依据统计方法对算法进行估算
如以下有两种方法实现的指定范围内的求和实现：
第一种算法：1
2
3
4
5int i, sum = 0, n = 100; /* 执行 1 次 */
for (i = 1; i <= n; i++) { /* 执行 n+1 次 */
sum = sum + i; /* 执行 n 次 */
}
printf("%d", sum); /* 执行 1 次*/
第二种算法：1
2
3int sum = 0, n = 100; /* 执行 1 次*/
sum = (1 + n) * n/2; /* 执行 1 次*/
printf("%d", sum); /* 执行 1 次*/
显然第一种算法执行了 2n + 3次，第二种算法是3次; 事实上两个算法的首、尾语句都是一样的，我们把循环看作一个整体，那么两个算法其实就是n次与1次的差距。算法好坏显而易见。
随着n的增加，算法A比算法B越来越好(执行的次数比B少)。于是我们可以得出结论，算法A总体上要算法B。 此时我们给出这样的定义，输入规模n，在没有限制的情况下，只要超过一个数值N，这个函数总是大于另一个函数，我们称函数是渐进增长的。
从中可以发现，随着n的增大，后面的+3、+1其实不影响最终算法变化，所以，我们可以忽略这些加法常数。
我们来看第二个例子，算法C是4n + 8，算法D是2n² + 1:
对比可以看出：最高次项相乘的常数并不重要
判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项(最高阶项)
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的数量。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。
用大写的O()来体现算法时间复杂度的记法，称之为大O记法。比如O(n)、O(1)、O(n²)我们取的非官方名称分别为：线性阶、常数阶、平方阶。
推导大O阶：
线性表：零个或多个数据元素的有限序列
特点：
1 | ADT 线性表(List) |
对于实际问题中涉及的更复杂的操作，完全可以基于以上的基本操作的组合来实现。
下面看一下线性表的两种物理存储结构的第一种，顺序存储结构：用一段连续的存储单元依次存储线性表的数据元素。
顺序存储示意图：
在内存中申请一段连续的地址，用来存储元素，那么这段地址长度意味着这个线性表的长度，实际使用个数代表元素实际长度。
排队插入示意图：
插入算法思路：
删除示意图：
删除算法思路：
优点：
缺点:
线性表顺序结构存储最大的问题就是插入、删除时，其他位置的元素需要挪位置，链式存储结构的线性表能够解决此问题。链式存储结构不考虑相邻位置，那有空位就到哪里，只是让每个元素知道它的下一个元素的位置在哪里。
1 | typedef struct Node { |
在顺序存储结构的线性表中，我们根据元素位置取元素是非常容易的。但在单链表中，没有办法一开始就知道，必须得从头开始找。
获取链表第i个数据的算法思路：
单链表中没有定义表长，所以事先不知道要循环多少次，其核心思想就是工作指针后移
插入示意图：
我们可以看出来，新元素的插入，主要操作：新元素指针域指向后一个元素，更新前一个元素的指针域指向新元素。
删除示意图：
同样可以看出来，元素的删除，主要操作：被删除元素的前一个元素更新指针域为被删除元素的指针域地址、销毁(返回)被删除元素
用数组描述的链表叫做静态链表 ，数组元素由两个数据域组成：
将终端节点的指针指向头结点，是整个单链表形成一个环，这种头尾相连的单链表称为单循环链表。
在单链表的节点中增加一个指针，将其指向前驱节点
栈是限定仅在表尾进行插入和删除操作的线性表。
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表
手枪的弹匣就像是栈，放子弹进弹匣就是入栈，开枪打出子弹则是出栈。
1 | ADT 栈(stack) |
由于栈本身是一个线性表，所以之前提到过的线性表的顺序存储和链式存储，对于栈也同样适用。
看下栈的结构定义：1
2
3
4
5typedef int SElementType; /* SElementType 类型根据实际情况而定，这里假设为int*/
typedef struct{
SElementType data[MAXSIZE];
int top; /* 用于记录栈顶 */
}SqStack;
栈就像”阉割”版的线性表，强调的是栈顶的操作，高级语言中一般会提供push、pop、peek这样的方法。
这里用java简单的实现了顺序存储的栈MyStack
栈的链式存储结构，简称链栈。
栈的操作都是在栈顶上的，那链式存储的栈将栈顶放到链表的头部还是尾部呢？ 链表本身有头指针，栈也需要栈顶指针，所以合二为一，将栈顶放在单链表的头部。
这里就不过多介绍链式存储的栈了，其对比顺序存储栈的特点体现在链式存储上。
队列就像排队买票，强调的是新来的人排在队尾，买票的人在队头，强调先进先出。
1 | ADT 队列(Queue) |
同样，队列也是一种特殊的线性表，也有顺序存储和链式存储。
队列顺序存储的问题：与顺序存储的线性表不同，如果单纯用数组首个元素作为队列头，最后一个元素作为队列尾，那么元素出队列，数组内的元素就需要往前移动，很明显队列就是专门用来处理入队、出队的数据类型，不像线性表的数据是单调读多、单调写多。所以就有了循环队列来解决这个问题。
头尾相连顺序存储结构的队列。
使用front表示头，rear表示尾。
这样有一个问题，空队列时 front == rear、队列满时也是如此，那怎么区分呢？
有两种方法：
用java实现的循环队列：MyArrayQueue.java
串是由零个或多个字符组成的有限序列，又名字符串。
两个数字很容易比较大小。2 > 1，这完全正确，可是两个字符串比较呢？比如“silly”、“stupid”这样同样表达“愚蠢的”单词字符串，它们在计算机中的大小取决于挨个字母的前后顺序。首个字母“s”忽相等，第二个字母“i”字母比“t”字母靠前，所以i < t，故 silly < stupid。
实际上，串的比较是通过组成串的字符之间的编码来进行的，比如这里的纯英文字母可以采用ascii编码来比较。
串的逻辑结构和线性表和相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符，哪怕串的字符是“123”，或者“2010-10-10”，其中每个元素都是字符，它们只能理解为长度为3和长度为10的字符串。
因此，对于串的基本操作与线性表的操作是由很大差别的。线性表关注的是单个元素的操作，比如操作一个元素、插入或删除一个元素，但字符串更多的是查找字符串位置、得到指定位置子串、替换子串等操作。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17ADT 串(String)
Data
串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
StrAssign(T, *chars): 生成一个其值等于字符串常量chars的串T。
StrCopy(T, S): 由串S复制得串T。
ClearString(S): 将串清空。
StringEmpty(S): 若串S为空，返回true，否则返回false。
StrLength(S): 返回串S的元素个数，即串长度。
StrCompare(S, T): 若S>T，返回值大于0，若S=T，返回0，若S<T，返回值小于0。
Concat(T, S1, S2): 用T返回S1和S2联接而成的新串。
SubString(Sub, S, Pos, len): 串S存在，1≤pos≤StrLength(S)，且0≤len≤StrLength(S)-pos+1，用Sub返回串S的第pos个字符起长度为len的子串。
Index(S, T, Pos): 串S和T存在，T是非空串，1≤pos≤StrLenght(S)。若主串S中存在和串T值相等的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则为0。
Replace(S, T, V): 串S、T、V存在，T是非空串。用V替换主串S中出现的所有与T相等不重叠的子串。
StrInsert(S, pos, len): 串S、T存在，1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T。
StrDelete(S, pos, len): 串S存在，1≤pos≤StrLenght(S)-len+1。从串S中删除第pos个字符起长度为len的子串。
endADT
串的顺序存储结构使用一组地址连续的存储单元来存储串中的字符串序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长的数组来定义。
串的链式存储结构与线性表是相似的，实际中链式存储的串除了在连接串有一定方便之外，总的来说不如顺序存储灵活。
子串的定位操作通常称作串的模式匹配，比如要从主串S=”goodgoogle”中，找到T=”google”这个子串的位置。我们通常需要下面的的步骤：
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作，简称KMP算法。
如果主串S=abcdefgab，匹配串T=abcdex，如果用前面的朴素算法的话，前5个字母，两个串完全相等，直到第6个字母，“f”与“x”不等，如图：
接下来，按照朴素算法，2、3、4、5、6，首字符与子串T的首字符均不等。
似乎这也是理所当然，原来的算法就是这么设计的。仔细观察发现，对于要匹配的子串T来说，“abcdex”首字母“a”与后面的串“bcdex”中任意一个字符都不相等，那么对于图中①来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2位到第5位字符相等。即②、③、④、⑤的判断都是多余的。
注意这里是理解KMP算法的关键。如果我们知道T串中首字符“a”与T中后面的字符均不相等(注意这是前提)。而T串的第二位的“b”与S串中的“b”在图中①已经判断是相等的，那么也就意味着T串中首字符“a”与S串中第二位“b”是不需要判断也知道他们是不可能相等的，这样上图中②这一步就可以省略。如下：
同样道理，在我们知道T串首字符“a”与T中后面的字符均不相等的前提下，T串的“a”与S串后面的“c”、“d”、“e”也都可以在①之后就可以确定不相等，所以算法②③④⑤没有必要，只保留①⑥即可，如下图：
跟着书中的这些文字转的有些晕了，停顿耗费了不少时间，跟着例子敲了以下的实现，就此带过了！
java实现：CharSequenceKMPCompare.java
理解了，不用了又淡忘了，渐渐模糊混淆，感觉耗费大把的经历。
通信，其实也就是网络通信，所以从Chrome的控制台的Network可以看到前端与后端的通信，如下图：
我暂时打算记录一下开发经常碰到的问题。
这里的介绍不会一应俱全，如果有需要你可以去参考一些权威指南。跟着自己的思考，带着一些问题来记录。
就像你在围墙外面，我在围墙里面，我们通过扔纸条的方式来通信，我不知道你是谁。
无状态带来的问题很明显，如果有两个人站在墙外，我不知道你是谁，那我们就不能聊一些私密的话题了。
在互联网，乃至整个现实世界，要绝对的确认一个人的身份是不可能的，网络上的信息可以被截取、模仿，现实世界有人工智能，就像那句“我不是李开复,我是人工智能。”
请求与响应就类似传递的信件，一部分是正文，一部分是必要的附加信息比如地址、身份等等。所以HTTP的“信件”分为了head、body部分。像一封信一样，虽然分为head、body但是他们是在一个报文内的。
HTTP/1.1 head 是文本(ASCII编码), body 可以是文本，也可以是二进制。
HTTP/2 则是一个彻底的二进制协议，头、数据体都是二进制，并且统称为“帧”（frame）：头信息帧、数据帧，因为帧可以方便的扩展，解析更为方便，HTTP/2已经定义了近十种帧。
来看下一个Ajax完整的请求报文：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15POST https://www.tzb360.com/tzb-api/api/public/login HTTP/1.1
Host: www.tzb360.com
Connection: keep-alive
Content-Length: 47
Origin: https://www.tzb360.com
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.86 Safari/537.36
Content-Type: application/x-www-form-urlencoded; charset=UTF-8
Accept: */*
X-Requested-With: XMLHttpRequest
Referer: https://www.tzb360.com/html/common/login.html
Accept-Encoding: gzip, deflate, br
Accept-Language: zh-CN,zh;q=0.8
Cookie: userId=test01; io=j8nS4_Ph2Jaq1aSWAFX4
loginName=cqtl123&password=tk110234&imgVefCode=
可以看出：
空行，即CR+LF（Carriage Return 回车， Line Feed 换行）响应头报文如下：1
2
3
4
5
6
7
8
9HTTP/1.1 200 OK
Server: nginx/1.9.9
Date: Tue, 11 Jul 2017 06:02:51 GMT
Content-Type: application/json
Content-Length: 928
Connection: keep-alive
Set-Cookie: TZB_SESSIONID=5788439a2c524880a5f79c6b81e97fcf; Path=/; HttpOnly
{"code":"0000","data":{},"msg":"操作成功"}
同样可以看出，也是使用\r\n作为头、体的分隔符的。
编码方面这前端请求主要用：XMLHttpRequest/fetch来实现，后台用Spring MVC来实现，只涉及到POST与GET方式的请求。
首先有必要讲下请求头中易忘、易混淆的字段：
Content-type ，内容类型，即描述body，作为请求头时，一般有以下4种分类来描述body：multipart/form-data; 类似页面表单，支持多字段、多类型。此类型请求体中会有对每个子段的的描述，就像请求体中分了多个子的请求头、请求体。application/x-www-form-urlencoded “=”号相隔的ascii键值串，非ascii字符与特殊字符需要转码，js中可以使用encodeURIComponent。请求体格式：a=value-a&b=value-btext/plain、application/json、text/xml，这一类请求意味着请求体是一块整体，告诉服务器按照Content-type来解析这块整体。Content-type。form如果不科学的使用，会引起误解，比如method=GET，提交时会忽略action问号后的参数，自动将表单内的input转换为地址的QueryString。当method=POST提交时，如果action的QueryString与表单内的字段都会被提交，后台可以从两个来源中得到同样的参数，而可能值不同。所以有必要强调的是，一般意义上的参数取法是当后台判断请求方法是GET时，取参从QueryString中取，当判断请求的方法是POST时，取参从FormData中取。后台可以取到POST请求的QueryString，GET请求是无body的。
错误的请求头设置，会导致后台不能正常的接收数据，请根据具体的场景选择请求方式、Content-type。
开发中会碰到一些复杂嵌套的对象需要传输，一般是前端设置ContentType: application/json 也就是body是一个raw，作为一个整体，后端使用@RequestBody描述对象。
使用jquery发起ajax请求时，会有data部分的参数设置，jquery发现请求是get时，会把data对象作为head的queryString提交，如果是POST，则会将data放置到body部分。
fetch方法默认情况下不会发送本地的cookie到服务器，注意如果需要依赖cookie，需要配置credentials，其配置值有：omit、same-origin、include，其意分别为不携带、同源携带、一直携带。更多关于fetch的信息可以参考MDN-GlobalFetch
这里再简单的记录下HTTP的几个版本的区别: （需要明白协议的实现要客户端、服务端共同完成，即新的浏览器、新的Web服务（Nginx/Apache/IIs等））
HTTP/1.1 (当今主流)
Connection: keep-alive，TCP默认不关闭，可以供多个请求复用，不用手动声明。连接没有活动，客户端就可以主动关闭连接了。规范的请求是，客户端发送最后一个请求时发送Connection: close，明确要求服务器关闭TCP连接。一般对于同一个域名，浏览器允许建立6个持久连接。Content-length的前提是在传输之前就得知道要传输的数据长度，对于一些耗时久、数据块大的操作来说，意味长时等待，这不太合理。更好的办法是产生一块数据，发送一块数据。使用Transfer-Encoding: chunked来表明数据是数量未定的数据块组成，每个非空数据块之前，会有一个16进制的数值，表示这个块的长度，最后一个大小为0的块，表示本轮数据传输完毕。下面有个chunked的响应例子：1 | HTTP/1.1 200 |
HTTP/2
在之前的java多线程编程核心技术文章中，主要是记录了书《Java多线程编程核心技术》的一些内容，其中没有介绍到LockSupport类，但是这个类在jdk源码中也经常会碰到，所以特意拿出来再看一番。
ReentrantLock，为什么还需要LockSupport呢？主要区别在于他们面向的对象不同。
我们先简单来回顾下ReentrantLock的使用：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public static void reviewReentrantLock() {
ReentrantLock lock = new ReentrantLock();
new Thread(() -> {
try {
lock.lock();
System.out.println("thread-A doXX");
TimeUnit.SECONDS.sleep(3);
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock(); // 记得 finally 中 释放锁
}
}, "thread-A").start();
new Thread(() -> {
try {
lock.lock();
System.out.println("thread-B doXX");
} finally {
lock.unlock();
}
}, "thread-B").start();
}
接下来看下LockSupport要怎么使用，看了下LockSupport的源码有以下特点：
1 | public static void useLockSupport() { |
可以使用unpark(thread)先取的许可，再执行park,如下：1
2
3
4
5
6
7
8public static void useLockSupport2() {
Thread thread = Thread.currentThread();
LockSupport.unpark(thread); // 为给定的线程提供许可；如果线程在park上被阻塞，那么它将被解除阻塞。否则它的下一次 park 执行将不会被阻塞
LockSupport.park(); // 等待许可，因为上一步已经提供了，所以会直接往下执行
System.out.println("block"); // 像没事人样，正常输出
LockSupport.park(); // 等待许可，前面的许可已经被使用了，故此线程将会进入休眠，等待许可
System.out.println("block 2"); // 阻塞，不会被输出
}
park，那么线程将会一直阻塞下去，故LockSupport是不可重入的 ，对比而言ReentrantLock是可重入的，一个线程可以多次获取同一把锁，lock.getHoldCount()方法会得到当前线程持有该锁的个数，也就是lock()方法的次数。总的来说就是：lock.lock()可以重复调用(线程内执行相应的lock.unlock())，而LockSupport.park()则是单次不重复的，只可等待其他线程LockSupport.unpark(t)下面我们看下线程对应中断会怎样响应：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public static void main(String[] args) throws InterruptedException {
Thread t = new Thread(() -> {
long start = System.currentTimeMillis();
long end = 0;
int count = 0;
while (end - start <= 1000) {
count++;
end = System.currentTimeMillis();
}
System.out.printf("after 1 second: acount=%s\n", count);
LockSupport.park(); // 等待许可
System.out.println("thread-child over." + Thread.currentThread().isInterrupted());
}, "thread-child");
t.start();
Thread.sleep(2000);
t.interrupt(); // 中断线程
System.out.println("main over!");
}
控制台输出：1
2
3after 1 second: acount=85732003
main over!
thread-child over.true
ReentrantLock 关注线程内部取锁lock()，unlock()的问题，都是线程内部代码在掌控锁，自己关注方法内的业务逻辑。LockSupport 更倾向线程间的协作，一个线程“LockSupport.park()”等待许可，另外一个线程来“唤醒”等待的线程。
LockSupport像是站在线程间的指挥家，可以指定唤醒哪个线程(LockSupport.unpark(thread))、什么时候唤醒等。
更准确的理解可以去查看LockSupport的源码注释。
主要参考：
从刚接触计算机理论起，就被灌输这是一台只认识0、1的机器，数字、字符串、声音、图像、视频等都可以在计算机中表示，这就是所谓的数字化吧。
既然说到了，字符编码，想必已经理解了这个问题只有0、1怎么表示2、3、4这些数字呢？，表示如下1
2
3
4
5
60000 -> 0
0001 -> 1
0010 -> 2
0011 -> 3
0100 -> 4
...
采用进位使用多个bit位来表示就可以了，小数的表示这里就不展开说了，有兴趣的可以从这里看。
bit 单元格，内存里面茫茫一片的01...， 内存并不去区分这个01是十进制1中的01，还是10进制2中的01 ，怎么区分这个交由具体的程序去做， 关于CPU位数，OS位数以及内存大小关系
内存位置16进制编号，一个网格，网格上每个都有编号，用16进制表示，0x....表示
程序指引 int a = 1; int b = 1
进入今天的正题字符编码，同样的问题0、1怎么来表示字符呢，比如hello、你好？
抽象的字符编码层面：把一个字符“编码”到一个数字
具体的字符编码层面：把抽象层面的数字“编码”成最终的储存形式，明确是定长还是变长；定长的话是定几个字节；用变长的话有哪几种字节长度，具体如何实现；
一般来说，字符集(关系表) 与 具体实现的编码是，1对1的关系，像ASCII、GB2312(EUC-CN存储)等，但是 Unicode 与 UTF-X 是1对多的，UTF-X 有UTF-8、UTF-16、UTF-32等
U+[XX]XXXX，X为16进制数字，4-6位表示。U+0000~U+10FFFF；两种理解思路:U+10FFFF 1*16^5 + 16^4 = 1114112U+10FFFF + 1 = U+110000个，前一个1是后一个1的16倍，(16+1) * 65536 = 1114112UTF-X 中X就代表了多少个比特位表示一个编码单元。Unicode码点最大10FFFF最大21位
UTF-8: 8bit即单字节为1个编码单元，UTF-16: 16bit即2个字节为1个编码单元, UTF-32：32bit即4个字节为1个编码单元
定长编码：意味着这类编码使用固定长度的字节，如ASCII固定占1个字节长度、UTF-32固定占4个字节长度。特点：复杂度低，其存在的问题是定多长，定少了不够用，定多了浪费空间
变长编码：字符所占长度不固定，如UTF-8占1/2/3/4个字节长度、UTF-16占2/4个字节长度。特点：具有一定复杂度，其核心解决的问题是如何区分不同的变长字节
定长编码的读取我们好理解，一次读固定长度的字节，根据码表将二进制翻译字符显示即可；写入时根据字符翻译成二进制，不足固定长度，向前补0即可；
那变长编码的读取和写入呢？
UTF-8：UTF-8利用高位保留来做区分来解决上面提到的如何区分不同的变长字节问题，缺点就是减少了有效编码空间
这种编码方式类似前缀编码：设计长短不等的编码，则必须是任一字符不是另一字符编码的前缀 ,就像压缩算法中应用的哈夫曼编码
UTF-8单个字节字符的字节0开头，n个字节的字符高字节是n个1开头，其中开头字节就像前缀一样。由于高位不同，多字节不会包含一字节的模式，0开头的字节不会出现在多字节字符编码中，二字节的模式不会出现在三字节模式中，也不会出现在四字节模式中；三字节的模式中也不会出现在四字节模式中；
| UNICODE码点范围 | UTF-8 | UTF-8二进制 | 有效编码 |
|---|---|---|---|
| U+0000~U+007F | 1字节 | 0XXXXXXX | 2^7=128个(ASCII) |
| U+0080~U+07FF | 2字节 | 110XXXXX 10XXXXXX | 2^11=2048个 |
| U+0800~U+FFFF | 3字节 | 1110XXXX 10XXXXXX 10XXXXXX | 2^16=65536个 |
| U+010000~U+10FFFF | 4字节 | 11110XXX 10XXXXXX 10XXXXXX 10XXXXXX | 2^21=2097152个 |
(n*8)-(n+1+(n-1)*2)=5n+1上面有效编码可以看出来，ASCII段占1个字节、大多数字符是占1或者3个字节的，一些生僻极其罕见的才会占4个字节
UTF-16: UTF-16是使用所谓的代理区来实现。从BMP字符集-鸟瀚图可以看到D8-D9整行都是空，这块空白就是所谓的代理区(Surrogate Area)。
代理区实现原理：我们来自己实现一种字符编码来体验下代理区吧
大多数占2个字节，生僻极其罕见的占4个字节。
ASCII: 计算机早期应用，只在美国，33个计算机控制字符、33个英文标点字符、10个数字字符、52个大小写字母字符，33+33+10+52=128 用一个字节的后7位表示，还空闲一个高位0XXX XXXX
EASCII: 计算机发展至欧洲，欧洲国家128个字符不够用，利用ASCII字节空闲的最高位扩展128个.
GB2312: 国标，每个汉字及符号以两个字节来表示，第一个字节为“高位字节”，第二个字节为“低位字节”
GBK: 国标扩展
EUC: EUC-CN ，Extended Unix Code，是一个使用8位编码来表示字符的方法
BIG5: 港澳台同胞
两个独立的尝试创立单一字符集的组织:
UNICODE: Unicode是Unicode Standard（Unicode标准）,定义了码点与字符的关系
ISO: 国际标准化组织
UCS: 通用字符集(Universal Character Set)，由ISO制定的ISO 10646标准；
BOM: Byte Order Mark，UTF-8采用字节为编码单元，没有字节序问题，常见的是UTF-16的字节序问题。
FF EE， 小的作为尾巴在后面。windows txt 另存时的Unicde 为UTF-16LEEE FF， 大的作为尾巴在后面。很多编码语言如java、javascript内码采用UTF-16BE沉下心，才会远离烦恼。
java提供了多线程，用户只要继承Thread类或实现Runnable接口就能轻松达到多线程的目的。简单的应用时，我们硬编码固定的线程数可能就能满足要求，但是涉及到线程资源的重复利用、管理、响应性能等，我们就需要线程池来协助了。类似数据库连接池，线程池主要有以下优点：
Java 1.5中引入了Executor框架把任务的提交和执行进行了解耦。只需要定义好任务，然后提交给线程池。而不用关心任务如何被执行、被哪个线程执行、以及什么时候执行等。
Executor接口：1
2
3public interface Executor {
void execute(Runnable command);
}
Executor只是一个简单的接口，但它为灵活而强大的框架创造了基础，Executor 基于 生产者-消费者模式。如果你在程序中实现一个生产者-消费者的设计，使用Executor通常是最简单的方式。
1 | public class ExecutorCase { |
Executors是java线程池的工厂类，通过它可以快速初始化一个符合业务需求的线程池，如Executors.newFixedThreadPool方法产生一个拥有固定数量的线程池。1
2
3
4
5public static ExecutorService newFixedThreadPool(int nThreads) {
return new ThreadPoolExecutor(nThreads, nThreads,
0L, TimeUnit.MILLISECONDS,
new LinkedBlockingQueue<Runnable>());
}
其中ExecutorService接口继承接口Executor，方法内本质是通过不同参数初始化ThreadPoolExecutor，下面看下这个方法是怎么定义的：1
2
3
4
5
6
7public ThreadPoolExecutor(int corePoolSize,
int maximumPoolSize,
long keepAliveTime,
TimeUnit unit,
BlockingQueue<Runnable> workQueue) {
this(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue, Executors.defaultThreadFactory(), defaultHandler);
}
最准确的注释，你还可以查看jdk源码中的英文注释。
要保存在池中的线程数，包括空闲的。除非allowCoreThreadTimeOut参数被设置。如果执行了prestartAllCoreThreads()方法，将提前创建并启动所有核心线程。
线程池允许的最大线程数，超出的提交将进入BlockingQueue阻塞队列，故executor.execute(xxTask)之后的代码不会因线程数量的限定而阻塞。
线程的空闲存活时间。该参数只在线程数大于核心线程数时起作用，结合corePoolSize的注释理解。
keepAliveTime的单位。
保存任务的阻塞队列，限定了队列中只能存储实现了Runnable接口的任务。BlockingQueue<Runnable>接口在JDK中有以下实现：
ArrayBlockingQueue: 基于数组结构的有界阻塞队列。LinkedBlockingQueue: 基于链表机构的阻塞队列。SynchronusQueue: 一个不存储元素的阻塞队列，每个插入操作必须等另一个线程调用移除操作，否则插入一直处于阻塞状态。PriorityBlockingQueue: 具有优先级的无界阻塞队列。前两者的味道类似于ArrayList与LinkedList，主要是具有数据结构Array、链表的特点。而SynchronusQueue则类似于CSP场景中，一个没有buffer缓冲的channel，《七周七并发模型》中一书中的CSP模型中提到新手往往会认为有缓存的channel会比无缓存的channel应用更广泛，但实际情况却恰恰相反。，虽然这不一定对，但是这提醒了我们一定要根据场景去选择使用。PriorityBlockingQueue则是更接近场景需求优先级的解决办法。
创建线程的工厂，具有名称前缀pool-,主要实现如下：1
2
3
4
5
6
7
8DefaultThreadFactory() {
SecurityManager s = System.getSecurityManager();
group = (s != null) ? s.getThreadGroup() :
Thread.currentThread().getThreadGroup();
namePrefix = "pool-" +
poolNumber.getAndIncrement() +
"-thread-";
}
任务队列达到限制的饱和处理策略。线程池提供了4中策略：
AbortPolicy: 直接抛出异常，默认策略CallerRunsPolicy: 用调用者所在线程来执行任务DiscardOldesPolicy: 丢弃队列最前面的任务，执行新的任务。类似于CSP模型中的sliding方式DiscardPolicy: 直接丢弃任务。类似于CSP模型中的dropping方式RejectedExecutionHandler接口，自定义饱和处理策略，比如日志记录、邮件提醒等。Executors工厂类提供了线程的初始化接口，主要有如下几种：
1 | public static ExecutorService newFixedThreadPool(int nThreads) { |
功能如其名，入参只有一个数字。指定固定的线程个数，其中 corePoolSize == maximumPoolSize，0L代表不会释放core线程，使用LinkedBlocingQueue作为任务队列。
1 | public static ExecutorService newCachedThreadPool() { |
初始化一个缓存限定时间线程的线程池，默认缓存60s，线程空闲超过60s时会自动释放线程，不会保留core线程。
1 | public static ExecutorService newSingleThreadExecutor(ThreadFactory threadFactory) { |
创建单个工作线程的Executor，等同于newFixedThreadPool(1, threadFactory)，返回的Executor不可再重新配置。
1 | public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize) { |
创建的线程池可以在指定的时间内周期性的执行所提交的任务，在实际的业务场景中可以使用该线程池定期同步数据。
1 | public static ExecutorService newWorkStealingPool() { |
jdk 1.8中出现，创建一个work-stealing的线程池，内部ForkJoinPool使用一个并行因子来创建，默认为主机CPU的可用核心数。
可以从方法内部的实例化代码看出，前三者都是ThreadPoolExecutor类实现的，newScheduledThreadPool返回类型都发生了变化，其实现是ScheduledThreadPoolExecutor，另外newWorkStealingPool返回值没有变化，说明暴露给外部的使用上没有变，内部使用ForkJoinPool来做了优化。
1 | private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0)); // ctl 包含了两个概念，因为两个的关联关系，巧妙的组合在一起；高3位表示线程池状态； 低29位 表示workerCount |
RUNNING : 线程池会接收新任务，并处理排队的任务 SHUTDOWN: 线程池不接收新任务，但会处理队列中的任务STOP: 线程池不接收新人无，不处理队列中的任务，并中断正在运行的任务TIDYING: 所有任务已经终止，workCount为零，线程过渡到TIDYING状态TERMINATED: terminated() 钩子方法运行完毕线程池框架提供了两种方式提交任务：
Executor.execute(Runnable command) 返回void, 不关心返回值
1 | void execute(Runnable command); |
ExecutorService.submit(Callable<T> task) 返回Future<T>
1 | <T> Future<T> submit(Callable<T> task) |
1 | int c = ctl.get(); // 获取原子变量的值 |
addWorker方法主要是创建线程，执行任务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
27private boolean addWorker(Runnable firstTask, boolean core) {
retry: // 重试标记层级
for (;;) { // 无限定条件的for
int c = ctl.get();
int rs = runStateOf(c);
// Check if queue empty only if necessary.
if (rs >= SHUTDOWN &&
! (rs == SHUTDOWN &&
firstTask == null &&
! workQueue.isEmpty()))
return false; // 线程池状态不满足则直接返回 false
for (;;) {
int wc = workerCountOf(c);
if (wc >= CAPACITY || // 如果 workerCount 大于 容量
wc >= (core ? corePoolSize : maximumPoolSize))
// 如果 workerCount 大于 核心线程数（外部以核心线程数作为判断依据时） 或 workerCount 大于 最大线程数(外部以最大线程数作为判断依据时)
return false; // 容量受限，返回false
if (compareAndIncrementWorkerCount(c)) // 通过上面的检测，并更新数值成功
break retry; // 跳出 多层循环，往方法的下半部分继续执行
c = ctl.get(); // Re-read ctl
if (runStateOf(c) != rs) // 上面未设值成功，状态 没有变化
continue retry; // 继续外部循环
// else CAS failed due to workerCount change; retry inner loop
}
}
以上是这个方法的前半部分，主要是线程池状态检测、线程池数量限制检测、线程池相关数量与状态的更新。以下是下半部分代码，主要是创建线程，执行任务: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
38boolean workerStarted = false;
boolean workerAdded = false;
Worker w = null;
try {
w = new Worker(firstTask); // 线程池的工作 通过 Worker 类，Worker 类继承了 AQS （AbstractQueuedSynchronizer）
final Thread t = w.thread; // 线程是取的 worker中的线程，而worker中的线程是线程池初始化的 线程工厂创建的
if (t != null) {
final ReentrantLock mainLock = this.mainLock; // ReentrantLock 锁的保证下，插入到 workers(HashSet结构)中
mainLock.lock();
try {
// Recheck while holding lock.
// Back out on ThreadFactory failure or if
// shut down before lock acquired.
int rs = runStateOf(ctl.get());
if (rs < SHUTDOWN ||
(rs == SHUTDOWN && firstTask == null)) {
if (t.isAlive()) // precheck that t is startable
throw new IllegalThreadStateException();
workers.add(w); // 加入 hashSet 中
int s = workers.size();
if (s > largestPoolSize)
largestPoolSize = s;
workerAdded = true;
}
} finally {
mainLock.unlock();
}
if (workerAdded) {
t.start(); // 添加成功 开始 运行
workerStarted = true;
}
}
} finally {
if (! workerStarted)
addWorkerFailed(w);
}
return workerStarted;
1 | Worker(Runnable firstTask) { // |
1 | final void runWorker(Worker w) { |
1 | private Runnable getTask() { |
1 | public class ExecutorCase2 { |
在实际业务场景中，Future与Callable一般是成对出现的，Callable负责执行任务产生结果，Future则是负责获取结果
Callable接口类似Runnable接口，只是Runnable没有返回值。所以如果你关心你每个任务的执行返回结果，就可以采用Callable，否则你就直接使用Runnable就好了。Callable执行的任务如果发生异常，该异常也会被返回，即Future可以拿到异步执行任务的各种结果。Future.get方法是阻塞的，直到Callable任务执行完成1 | public <T> Future<T> submit(Callable<T> task) { |
Callable任务通过submit()方法被封装为一个RunnableFuture的FutureTask.
1 | /* |
FutureTask的状态，NEW，构造函数使用callable成员变量存储了入参callable任务FutureTask实现了Runnable接口，最终实际执行的是FutureTask中的run方法1 | public V get() throws InterruptedException, ExecutionException { |
内部通过awaitDone方法阻塞，代码如下：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
36private int awaitDone(boolean timed, long nanos)
throws InterruptedException {
final long deadline = timed ? System.nanoTime() + nanos : 0L;
WaitNode q = null;
boolean queued = false;
for (;;) {
if (Thread.interrupted()) {
removeWaiter(q);
throw new InterruptedException();
}
int s = state;
if (s > COMPLETING) {
if (q != null)
q.thread = null;
return s;
}
else if (s == COMPLETING) // cannot time out yet
Thread.yield();
else if (q == null)
q = new WaitNode();
else if (!queued)
queued = UNSAFE.compareAndSwapObject(this, waitersOffset,
q.next = waiters, q);
else if (timed) {
nanos = deadline - System.nanoTime();
if (nanos <= 0L) {
removeWaiter(q);
return state;
}
LockSupport.parkNanos(this, nanos);
}
else
LockSupport.park(this);
}
}
COMPLETING说明已经完成，直接返回状态即可COMPLETING说明已经完成，使用yield让渡一下cpu，state则会过度到NORMAL了WaitNode简单链表封装当前线程，并通过UNSAFE添加到waiters链表LockSupport的park或parkNanos来挂起线程，另外finishCompletion方法中会unpark1 | public void run() { |
run 方法是线程池中的线程来执行的，而非主线程callable.call方法来运行任务call通过时用set方法来保存结果call出现异常时用setException方法来保持异常信息1 | protected void set(V v) { |
通过UNSAFE修改了FutureTask的状态，最终都通过调用finishCompletion方法通知主线程任务完成。
1 | private void finishCompletion() { |
waiters的值LockSupport.unpark(t)唤醒主线程主要参考：