一、常用的http请求头

1.Accept

• Accept: text/html 浏览器可以接受服务器回发的类型为 text/html。
• Accept: */* 代表浏览器可以处理所有类型,(一般浏览器发给服务器都是发这个)。

2.Accept-Encoding

• Accept-Encoding: gzip, deflate 浏览器申明自己接收的编码方法，通常指定压缩方法，是否支持压缩，支持什么压缩方法（gzip，deflate），（注意：这不是只字符编码）。

3.Accept-Language

• Accept-Language:zh-CN,zh;q=0.9 浏览器申明自己接收的语言。

4.Connection

• Connection: keep-alive 当一个网页打开完成后，客户端和服务器之间用于传输HTTP数据的TCP连接不会关闭，如果客户端再次访问这个服务器上的网页，会继续使用这一条已经建立的连接。
• Connection: close 代表一个Request完成后，客户端和服务器之间用于传输HTTP数据的TCP连接会关闭， 当客户端再次发送Request，需要重新建立TCP连接。

5.Host（发送请求时，该报头域是必需的）

• Host:www.baidu.com 请求报头域主要用于指定被请求资源的Internet主机和端口号，它通常从HTTP URL中提取出来的。

6.Referer

• Referer:https://www.baidu.com/?tn=62095104_8_oem_dg 当浏览器向web服务器发送请求的时候，一般会带上Referer，告诉服务器我是从哪个页面链接过来的，服务器籍此可以获得一些信息用于处理。

7.User-Agent

• User-Agent:Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/70.0.3538.110 Safari/537.36 告诉HTTP服务器， 客户端使用的操作系统和浏览器的名称和版本。

8.Cache-Control

• Cache-Control:private 默认为private 响应只能够作为私有的缓存，不能再用户间共享
• `\Cache-Control:public** `**响应会被缓存，并且在多用户间共享。正常情况, 如果要求HTTP认证,响应会自动设置为 private.
• Cache-Control:must-revalidate 响应在特定条件下会被重用，以满足接下来的请求，但是它必须到服务器端去验证它是不是仍然是最新的。
• Cache-Control:no-cache 响应不会被缓存,而是实时向服务器端请求资源。
• Cache-Control:max-age=10 设置缓存最大的有效时间，但是这个参数定义的是时间大小（比如：60）而不是确定的时间点。单位是[秒 seconds]。
• Cache-Control:no-store在任何条件下，响应都不会被缓存，并且不会被写入到客户端的磁盘里，这也是基于安全考虑的某些敏感的响应才会使用这个。

9.Cookie

Cookie是用来存储一些用户信息以便让服务器辨别用户身份的（大多数需要登录的网站上面会比较常见），比如cookie会存储一些用户的用户名和密码，当用户登录后就会在客户端产生一个cookie来存储相关信息，这样浏览器通过读取cookie的信息去服务器上验证并通过后会判定你是合法用户，从而允许查看相应网页。当然cookie里面的数据不仅仅是上述范围，还有很多信息可以存储是cookie里面，比如sessionid等。

10.Range（用于断点续传）

• Range:bytes=0-5 指定第一个字节的位置和最后一个字节的位置。用于告诉服务器自己想取对象的哪部分。

二、常用的http响应头

1.Cache-Control（对应请求中的Cache-Control）

• Cache-Control:private 默认为private 响应只能够作为私有的缓存，不能再用户间共享
• \Cache-Control:public** 浏览器和缓存服务器都可以缓存页面信息。
• Cache-Control:must-revalidate 对于客户机的每次请求，代理服务器必须想服务器验证缓存是否过时。
• Cache-Control:no-cache 浏览器和缓存服务器都不应该缓存页面信息。
• Cache-Control:max-age=10 是通知浏览器10秒之内不要烦我，自己从缓冲区中刷新。
• Cache-Control:no-store 请求和响应的信息都不应该被存储在对方的磁盘系统中。

2.Content-Type

• Content-Type：text/html;charset=UTF-8 告诉客户端，资源文件的类型，还有字符编码，客户端通过utf-8对资源进行解码，然后对资源进行html解析。通常我们会看到有些网站是乱码的，往往就是服务器端没有返回正确的编码。

3.Content-Encoding

• Content-Encoding:gzip 告诉客户端，服务端发送的资源是采用gzip编码的，客户端看到这个信息后，应该采用gzip对资源进行解码。

4.Date

• Date: Tue, 03 Apr 2018 03:52:28 GMT 这个是服务端发送资源时的服务器时间，GMT是格林尼治所在地的标准时间。http协议中发送的时间都是GMT的，这主要是解决在互联网上，不同时区在相互请求资源的时候，时间混乱问题。

5.Server

• Server：Tengine/1.4.6 这个是服务器和相对应的版本，只是告诉客户端服务器信息。

6.Transfer-Encoding

• Transfer-Encoding：chunked 这个响应头告诉客户端，服务器发送的资源的方式是分块发送的。一般分块发送的资源都是服务器动态生成的，在发送时还不知道发送资源的大小，所以采用分块发送，每一块都是独立的，独立的块都能标示自己的长度，最后一块是0长度的，当客户端读到这个0长度的块时，就可以确定资源已经传输完了。

7.Expires

• Expires:Sun, 1 Jan 2000 01:00:00 GMT 这个响应头也是跟缓存有关的，告诉客户端在这个时间前，可以直接访问缓存副本，很显然这个值会存在问题，因为客户端和服务器的时间不一定会都是相同的，如果时间不同就会导致问题。所以这个响应头是没有Cache-Control：max-age=*这个响应头准确的，因为max-age=date中的date是个相对时间，不仅更好理解，也更准确。

8.Last-Modified

• Last-Modified: Dec, 26 Dec 2015 17:30:00 GMT 所请求的对象的最后修改日期(按照 RFC 7231 中定义的“超文本传输协议日期”格式来表示)

9.Connection

• Connection：keep-alive 这个字段作为回应客户端的Connection：keep-alive，告诉客户端服务器的tcp连接也是一个长连接，客户端可以继续使用这个tcp连接发送http请求。

10.Etag

• ETag: “737060cd8c284d8af7ad3082f209582d” 就是一个对象（比如URL）的标志值，就一个对象而言，比如一个html文件，如果被修改了，其Etag也会别修改，所以，ETag的作用跟Last-Modified的作用差不多，主要供WEB服务器判断一个对象是否改变了。比如前一次请求某个html文件时，获得了其 ETag，当这次又请求这个文件时，浏览器就会把先前获得ETag值发送给WEB服务器，然后WEB服务器会把这个ETag跟该文件的当前ETag进行对比，然后就知道这个文件有没有改变了。

11.Refresh

• Refresh: 5; url=http://baidu.com 用于重定向，或者当一个新的资源被创建时。默认会在5秒后刷新重定向。

12.Access-Control-Allow-Origin

• Access-Control-Allow-Origin: * 号代表所有网站可以跨域资源共享，如果当前字段为那么Access-Control-Allow-Credentials就不能为true
• Access-Control-Allow-Origin: www.baidu.com 指定哪些网站可以跨域资源共享

13.Access-Control-Allow-Methods

• Access-Control-Allow-Methods：GET,POST,PUT,DELETE 允许哪些方法来访问

14.Access-Control-Allow-Credentials

• Access-Control-Allow-Credentials: true 是否允许发送cookie。默认情况下，Cookie不包括在CORS请求之中。设为true，即表示服务器明确许可，Cookie可以包含在请求中，一起发给服务器。这个值也只能设为true，如果服务器不要浏览器发送Cookie，删除该字段即可。如果access-control-allow-origin为*，当前字段就不能为true

15.Content-Range

• Content-Range: bytes 0-5/7877 指定整个实体中的一部分的插入位置，他也指示了整个实体的长度。在服务器向客户返回一个部分响应，它必须描述响应覆盖的范围和整个实体长度。

本文整理自

常用的http请求头以及响应头

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

在技术面试中，经常被问到“Cookie和Session的区别”，大家都知道一些，Session比Cookie安全，Session是存储在服务器端的，Cookie是存储在客户端的，然而如果让你更详细地说明，恐怕就不怎么清楚了。

本文分别对Cookie与Session做一个介绍和总结，并分别对两个知识点进行对比分析，让大家对Cookie和Session有更深入的了解。

什么是HTTP

首先要先介绍什么是HTTP

HTTP:超文本传输协议（英文：HyperText Transfer Protocol，缩写：HTTP）是一种用于分布式、协作式和超媒体信息系统的应用层协议。HTTP是万维网的数据通信的基础。设计HTTP最初的目的是为了提供一种发布和接收HTML页面的方法。通过HTTP或者HTTPS协议请求的资源由统一资源标识符（Uniform Resource Identifiers，URI）来标识。

HTTP 是无状态协议，说明它不能以状态来区分和管理请求和响应。也就是说，服务器单从网络连接上无从知道客户身份。

可是怎么办呢？就给客户端们颁发一个通行证吧，每人一个，无论谁访问都必须携带自己通行证。这样服务器就能从通行证上确认客户身份了。这就是Cookie的工作原理。

1.Cookie

什么是cookie

Cookie翻译过来是‘ 小甜饼’，Cookie是客户端保存用户信息的一种机制，用来记录用户的一些信息，实际上Cookie是服务器在本地机器上存储的一小段文本，并随着每次请求发送到服务器。

Cookie技术通过请求和响应报文中写入Cookie信息来控制客户端的状态。

Cookie会根据响应报文里的一个叫做Set-Cookie的首部字段信息，通知客户端保存Cookie。当下客户端再向服务端发起请求时，客户端会自动在请求报文中加入Cookie值之后发送出去.

之后服务端发现客户端发送过来的Cookie后，会检查是那个客户端发送过来的请求，然后对服务器上的记录，最后得到了之前的状态信息。

客户端保存了Cookie之后的发起请求

上图很清晰地展示了发生Cookie 交互的情景，HTTP 请求报文和响应报文的内容如图所示。

第一可以很明显的可出首部字段内没有Cookie的相关信息，其次也能看到set-Cookie里的信息，这就是服务器端生撑的Cookei信息。

看之后请求，请求报文里都自动发送Cookie信息了。

set-Cookie的字段的属性

1
2
3

Set-Cookie: logcookie=3qjj; expires=Wed, 13-Mar-2019 12:08:53 GMT; Max-Age=31536000; path=/;
 domain=fafa.com;secure; HttpOnly;
复制代码

以上面的set-cookie的例子，说一下set-cookie的属性

1.logcookie=3qjj 赋予Cookie的名称和值，logcookie是名字 ，3qjj是值

2.expires 是设置cookie有效期。当省略expires属性时，Cookie仅在关闭浏览器之前有效。可以通过覆盖已过期的Cookie，设置这个Cookie的过期时间是过去的时间，实现对客户端Cookie 的实质性删除操作。

3.path 是限制指定Cookie 的发送范围的文件目录。不过另有办法可避开这项限制，看来对其作为安全机制的效果不能抱有期待。

4.domain 通过domain属性指定的域名可以做到与结尾匹配一致。比如，指定domain是fafa.com，除了fafa.com那么www.fafa.com等都可以发送Cookie。

5.secure 设置web页面只有在HTTPS安全连接时，才可以发送Cookie。HHTP则不可以进行回收。

6.HttpOnly 它使JavaScript 脚本无法获得Cookie，通过上述设置，通常从Web 页面内还可以对Cookie 进行读取操作。但使用JavaScript 的document.cookie 就无法读取附加HttpOnly 属性后的Cookie 的内容了

2.Session管理和Cookie应用

什么是Session

上面我讲到服务端执行session机制时候会生成session的id值，这个id值会发送给客户端，客户端每次请求都会把这个id值放到http请求的头部发送给服务端，而这个id值在客户端会保存下来，保存的容器就是cookie，因此当我们完全禁掉浏览器的cookie的时候，服务端的session也会不能正常使用。

PHP中的Session在默认情况下是使用客户端的Cookie来保存Session ID的，所以当客户端的cookie出现问题的时候就会影响Session了。必须注意的是：Session不一定必须依赖Cookie，这也是Session相比Cookie的高明之处。当客户端的Cookie被禁用或出现问题时，PHP会自动把Session ID附着在URL中，这样再通过Session ID就能跨页使用Session变量了。

1.客户端把信息放入报文的实体部分，通常是以POST 方法把请求发送给服务器。

2.服务器会发放用以识别用户的Session ID。通过验证从客户端发送过来的信息进行验证，然后把用户的认证状态与Session ID 绑定后记录在服务器端。向客户端返回响应时，会在首部字段Set-Cookie 内写入Session ID（如PHPSESSID=l128ogl…）。你可以把Session ID 想象成一种用以区分不同用户的唯一Id。

步骤三：客户端接收到从服务器端发来的Session ID 后，会将其作为Cookie 保存在本地。下次向服务器发送请求时，浏览器会自动发送Cookie，所以Session ID 也随之发送到服务器。服务器端可通过验证接收到的Session ID 验证状态。

3.Cookie与Session的区别

1. cookie数据存放在客户的浏览器（客户端）上，session数据放在服务器上，但是服务端的session的实现对客户端的cookie有依赖关系的；
2. cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗，考虑到安全应当使用session；
3. session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能。考虑到减轻服务器性能方面，应当使用COOKIE；
4. 单个cookie在客户端的限制是3K，就是说一个站点在客户端存放的COOKIE不能超过3K；

本文整理自

Cookie 和 Session 关系和区别

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

简介

一个HTTP方法是幂等的，指的是同样的请求被执行一次与连续执行多次的效果是一样的，服务器的状态也是一样的。换句话说就是，幂等方法不应该具有副作用（统计用途除外）。在正确实现的条件下，GET，HEAD，PUT和DELETE 等方法都是幂等的，而 POST 方法不是。所有的 safe 方法(指不修改资源的 HTTP 方法)也都是幂等的。

幂等性只与后端服务器的实际状态有关，而每一次请求接收到的状态码不一定相同。例如，第一次调用DELETE 方法有可能返回 200，但是后续的请求可能会返回404。DELETE 的言外之意是，开发者不应该使用DELETE方法实现具有删除最后条目功能的 RESTful API。

需要注意的是，服务器不一定会确保请求方法的幂等性，有些应用可能会错误地打破幂等性约束。

GET /pageX HTTP/1.1是幂等的。连续调用多次，客户端接收到的结果都是一样的：

1
2
3
4

GET /pageX HTTP/1.1   
GET /pageX HTTP/1.1   
GET /pageX HTTP/1.1   
GET /pageX HTTP/1.1

POST /add_row HTTP/1.1不是幂等的。如果调用多次，就会增加多行记录：

1
2
3

POST /add_row HTTP/1.1
POST /add_row HTTP/1.1   -> Adds a 2nd row
POST /add_row HTTP/1.1   -> Adds a 3rd row

DELETE /idX/delete HTTP/1.1是幂等的，即便是不同请求之间接收到的状态码不一样：

1
2
3

DELETE /idX/delete HTTP/1.1   -> Returns 200 if idX exists
DELETE /idX/delete HTTP/1.1   -> Returns 404 as it just got deleted
DELETE /idX/delete HTTP/1.1   -> Returns 404

安全方法

安全方法是指不修改资源的 HTTP 方法。譬如，当使用 GET 或者 HEAD 作为资源 URL，都必须不去改变资源。然而，这并不全准确。意思是：它不改变资源的 表示形式。对于安全方法，它仍然可能改变服务器上的内容或资源，但这必须不导致不同的表现形式。

这表示下述是不对的，因为它实际上将删除博客文章：

1

GET /blog/1234/delete HTTP/1.1

安全方法是那些可以被缓存、对资源无损预加载的方法。

幂等性分析

HTTP幂等方法，是指无论调用多少次都不会有不同结果的 HTTP 方法。不管你调用一次，还是调用一百次，一千次，结果都是相同的。

还是以之前的博文的例子为例。

1
2
3
4
5
6

GET     /tickets       # 获取ticket列表
GET     /tickets/12    # 查看某个具体的ticket
POST    /tickets       # 新建一个ticket
PUT     /tickets/12    # 更新ticket 12
PATCH   /tickets/12    # 更新ticket 12
DELETE  /tickets/12    # 删除ticekt 12

HTTP GET方法

HTTP GET方法，用于获取资源，不管调用多少次接口，结果都不会改变，所以是幂等的。

1
2

GET     /tickets       # 获取ticket列表
GET     /tickets/12    # 查看某个具体的ticket

只是查询数据，不会影响到资源的变化，因此我们认为它幂等。

值得注意，幂等性指的是作用于结果而非资源本身。怎么理解呢？例如，这个HTTP GET方法可能会每次得到不同的返回内容，但并不影响资源。

可能你会问有这种情况么？当然有咯。例如，我们有一个接口获取当前时间，我们就应该设计成

1

GET     /service_time # 获取服务器当前时间

它本身不会对资源本身产生影响，因此满足幂等性。

HTTP POST方法

HTTP POST方法是一个非幂等方法，因为调用多次，都将产生新的资源。

1

POST    /tickets       # 新建一个ticket

因为它会对资源本身产生影响，每次调用都会有新的资源产生，因此不满足幂等性。

HTTP PUT方法

HTTP PUT方法是不是幂等的呢？我们来看下

1

PUT     /tickets/12    # 更新ticket 12

因为它直接把实体部分的数据替换到服务器的资源，我们多次调用它，只会产生一次影响，但是有相同结果的 HTTP 方法，所以满足幂等性。

HTTP PATCH方法

HTTP PATCH方法是非幂等的。HTTP POST方法和HTTP PUT方法可能比较好理解，但是HTTP PATCH方法只是更新部分资源，怎么是非幂等的呢?

因为，PATCH提供的实体则需要根据程序或其它协议的定义，解析后在服务器上执行，以此来修改服务器上的资源。换句话说，PATCH请求是会执行某个程序的，如果重复提交，程序可能执行多次，对服务器上的资源就可能造成额外的影响，这就可以解释它为什么是非幂等的了。

可能你还不能理解这点。我们举个例子

1

PATCH   /tickets/12    # 更新ticket 12

此时，我们服务端对方法的处理是，当调用一次方法，更新部分字段，将这条ticket记录的操作记录加一，这次，每次调用的资源是不是变了呢，所以它是有可能是非幂等的操作。

HTTP DELETE方法

HTTP DELETE方法用于删除资源，会将资源删除。

1

DELETE  /tickets/12    # 删除ticekt 12

调用一次和多次对资源产生影响是相同的，所以也满足幂等性。

对比

(部分) HTTP 方法概览

如何设计符合幂等性的高质量RESTful API

HTTP GET方法 vs HTTP POST方法

也许，你会想起一个面试题。HTTP请求的GET与POST方式有什么区别？你可能会回答到：GET方式通过URL提交数据，数据在URL中可以看到；POST方式，数据放置在HTML HEADER内提交。但是，我们现在从RESTful的资源角度来看待问题，HTTP GET方法是幂等的，所以它适合作为查询操作，HTTP POST方法是非幂等的，所以用来表示新增操作。

但是，也有例外，我们有的时候可能需要把查询方法改造成HTTP POST方法。比如，超长（1k）的GET URL使用POST方法来替代，因为GET受到URL长度的限制。虽然，它不符合幂等性，但是它是一种折中的方案。

HTTP POST方法 vs HTTP PUT方法

对于HTTP POST方法和TTP PUT方法，我们一般的理解是POST表示创建资源，PUT表示更新资源。当然，这个是正确的理解。

但是，实际上，两个方法都用于创建资源，更为本质的差别是在幂等性。HTTP POST方法是非幂等，所以用来表示创建资源，HTTP PUT方法是幂等的，因此表示更新资源更加贴切。

HTTP PUT方法 vs HTTP PATCH方法

此时，你看会有另外一个问题。HTTP PUT方法和HTTP PATCH方法，都是用来表述更新资源，它们之间有什么区别呢？我们一般的理解是PUT表示更新全部资源，PATCH表示更新部分资源。首先，这个是我们遵守的第一准则。根据上面的描述，PATCH方法是非幂等的，因此我们在设计我们服务端的RESTful API的时候，也需要考虑。如果，我们想要明确的告诉调用者我们的资源是幂等的，我的设计更倾向于使用HTTP PUT方法。

本文整理自

如何理解 RESTful 的幂等性

[RESTful 手册](https://sofish.github.io/restcookbook/http methods/idempotency/)

幂等

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

字符串匹配是计算机的基本任务之一。

举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？

许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。

这种算法不太容易理解，网上有很多解释，但读起来都很费劲。直到读到Jake Boxer的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。

1.

首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

2.

因为B与A不匹配，搜索词再往后移。

3.

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

4.

接着比较字符串和搜索词的下一个字符，还是相同。

5.

直到字符串有一个字符，与搜索词对应的字符不相同为止。

6.

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。

7.

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

8.

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

9.

已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数：

　　移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

10.

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

11.

因为空格与A不匹配，继续后移一位。

12.

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

13.

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

14.

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

15.

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

　　－　“A”的前缀和后缀都为空集，共有元素的长度为0；

　　－　“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

　　－　“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

　　－　“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

　　－　“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；

　　－　“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；

　　－　“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

16.

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

本文整理自

字符串匹配的KMP算法

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

堆外内存

JVM启动时分配的内存，称为堆内存，与之相对的，在代码中还可以使用堆外内存，比如Netty，广泛使用了堆外内存，但是这部分的内存并不归JVM管理，GC算法并不会对它们进行回收，所以在使用堆外内存时，要格外小心，防止内存一直得不到释放，造成线上故障。

堆外内存的申请和释放

JDK的ByteBuffer类提供了一个接口allocateDirect(int capacity)进行堆外内存的申请，底层通过unsafe.allocateMemory(size)实现，接下去看看在JVM层面是如何实现的。

可以发现，最底层是通过malloc方法申请的，但是这块内存需要进行手动释放，JVM并不会进行回收，幸好Unsafe提供了另一个接口freeMemory可以对申请的堆外内存进行释放。

堆外内存的回收机制

如果每次申请堆外内存，都需要在代码中显示的释放，对于Java这门语言的设计来说，显然不够合理，既然JVM不会管理这些堆外内存，它们是如何回收的呢？

DirectByteBuffer

JDK中使用DirectByteBuffer对象来表示堆外内存，每个DirectByteBuffer对象在初始化时，都会创建一个对用的Cleaner对象，这个Cleaner对象会在合适的时候执行unsafe.freeMemory(address)，从而回收这块堆外内存。

当初始化一块堆外内存时，对象的引用关系如下：

其中first是Cleaner类的静态变量，Cleaner对象在初始化时会被添加到Clener链表中，和first形成引用关系，ReferenceQueue是用来保存需要回收的Cleaner对象。

如果该DirectByteBuffer对象在一次GC中被回收了

此时，只有Cleaner对象唯一保存了堆外内存的数据（开始地址、大小和容量），在下一次FGC时，把该Cleaner对象放入到ReferenceQueue中，并触发clean方法。

Cleaner对象的clean方法主要有两个作用：
1、把自身从Clener链表删除，从而在下次GC时能够被回收
2、释放堆外内存

1
2
3
4
5
6
7
8
9

public void run() {
    if (address == 0) {
        // Paranoia
        return;
    }
    unsafe.freeMemory(address);
    address = 0;
    Bits.unreserveMemory(size, capacity);
}

如果JVM一直没有执行FGC的话，无效的Cleaner对象就无法放入到ReferenceQueue中，从而堆外内存也一直得不到释放，内存岂不是会爆？

其实在初始化DirectByteBuffer对象时，如果当前堆外内存的条件很苛刻时，会主动调用System.gc()强制执行FGC。

不过很多线上环境的JVM参数有-XX:+DisableExplicitGC，导致了System.gc()等于一个空函数，根本不会触发FGC，这一点在使用Netty框架时需要注意是否会出问题。

本文整理自

堆外内存的回收机制分析

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

JVM 的一些知识

在说明finalize()的用法之前要树立有关于java垃圾回收器几个观点:

• 对象可以不被垃圾回收

java的垃圾回收遵循一个特点, 就是能不回收就不会回收.只要程序的内存没有达到即将用完的地步, 对象占用的空间就不会被释放。

因为如果程序正常结束了,而且垃圾回收器没有释放申请的内存, 那么随着程序的正常退出, 申请的内存会自动交还给操作系统;

而且垃圾回收本身就需要付出代价, 是有一定开销的, 如果不使用,就不会存在这一部分的开销。

• 垃圾回收只能回收内存

而且只能回收内存中由java创建对象方式(堆)创建的对象所占用的那一部分内存, 无法回收其他资源, 比如文件操作的句柄, 数据库的连接等等。

• 垃圾回收不是C++中的析构

两者不是对应关系, 因为第一点就指出了垃圾回收的发生是不确定的, 而C++中析构函数是由程序员控制(delete) 或者离开器作用域时自动调用发生, 是在确定的时间对对象进行销毁并释放其所占用的内存。

• 调用垃圾回收器(GC)不一定保证垃圾回收器的运行

finalize的作用

finalize()是Object的protected方法，子类可以覆盖该方法以实现资源清理工作，GC在回收对象之前调用该方法。

finalize()与C++中的析构函数不是对应的。

C++中的析构函数调用的时机是确定的（对象离开作用域或delete掉），但Java中的finalize的调用具有不确定性。

finalize() 的功能: 一旦垃圾回收器准备释放对象所占的内存空间, 如果对象覆盖了finalize()并且函数体内不能是空的, 就会首先调用对象的finalize(), 然后在下一次垃圾回收动作发生的时候真正收回对象所占的空间。

finalize() 有一个特点就是: JVM始终只调用一次. 无论这个对象被垃圾回收器标记为什么状态, finalize()始终只调用一次. 但是程序员在代码中主动调用的不记录在这之内。

finalize函数的调用机制

java虚拟机规范并没有硬性规定垃圾回收该不该搞，以及该如何搞。所以这里提到的调用机制不能保证适合所有jvm。

何时被调用？

finalize啥时候才会被调用捏？

一般来说，要等到JVM开始进行垃圾回收的时候，它才有可能被调用。

而JVM进行垃圾回收的时间点是非常不确定的，依赖于各种运行时的环境因素。

正是由于finalize函数调用时间点的不确定，导致了后面提到的某些缺点。

谁来调用？

常见的JVM会通过GC的垃圾回收线程来进行finalize函数的调用。

由于垃圾回收线程比较重要（人家好歹也是JVM的一个组成部分嘛），为了防止finalize函数抛出的异常影响到垃圾回收线程的运作，垃圾回收线程会在调用每一个finalize函数时进行try catch，如果捕获到异常，就直接丢弃，然后接着处理下一个失效对象的finalize函数。

使用场景

不建议用finalize方法完成“非内存资源”的清理工作

不建议使用的原因

一些问题

一些与finalize相关的方法，由于一些致命的缺陷，已经被废弃了，如System.runFinalizersOnExit()方法、Runtime.runFinalizersOnExit()方法

System.gc()与System.runFinalization()方法增加了finalize方法执行的机会，但不可盲目依赖它们

Java语言规范并不保证finalize方法会被及时地执行、而且根本不会保证它们会被执行

finalize方法可能会带来性能问题。因为JVM通常在单独的低优先级线程中完成finalize的执行

对象再生问题：finalize方法中，可将待回收对象赋值给GC Roots可达的对象引用，从而达到对象再生的目的

finalize方法至多由GC执行一次(用户当然可以手动调用对象的finalize方法，但并不影响GC对finalize的行为)

适合的场景

finalize()主要使用的方面:

根据垃圾回收器的第2点可知, java垃圾回收器只能回收创建在堆中的java对象, 而对于不是这种方式创建的对象则没有方法处理, 这就需要使用finalize()对这部分对象所占的资源进行释放. 使用到这一点的就是JNI本地对象, 通过JNI来调用本地方法创建的对象只能通过finalize()保证使用之后进行销毁,释放内存

充当保证使用之后释放资源的最后一道屏障, 比如使用数据库连接之后未断开,并且由于程序员的个人原因忘记了释放连接, 这时就只能依靠finalize()函数来释放资源.

《thinking in java》中所讲到的“终结条件”验证, 通过finalize()方法来试图找出程序的漏洞

尽管finalize()可以主动调用, 但是最好不要主动调用, 因为在代码中主动调用之后, 如果JVM再次调用, 由于之前的调用已经释放过资源了,所以二次释放资源就有可能出现导致出现空指针等异常, 而恰好这些异常是没有被捕获的, 那么就造成对象处于被破坏的状态, 导致该对象所占用的某一部分资源无法被回收而浪费.

尽量避免使用finalize():

finalize()不一定会被调用, 因为java的垃圾回收器的特性就决定了它不一定会被调用

就算finalize()函数被调用, 它被调用的时间充满了不确定性, 因为程序中其他线程的优先级远远高于执行 finalize() 函数线程的优先级。

也许等到finalize()被调用, 数据库的连接池或者文件句柄早就耗尽了。

如果一种未被捕获的异常在使用finalize方法时被抛出，这个异常不会被捕获，finalize方法的终结过程也会终止，造成对象出于破坏的状态。被破坏的对象又很可能导致部分资源无法被回收, 造成浪费。

finalize()和垃圾回收器的运行本身就要耗费资源, 也许会导致程序的暂时停止。

禁止使用的原因

1.调用时间不确定—有资源浪费的风险

前面已经介绍了调用机制。

同学们应该认清“finalize的调用时机是很不确定的”这样一个事实。

所以，假如你把某些稀缺资源放到finalize()中释放，可能会导致该稀缺资源等上很久很久很久以后才被释放。

这可是资源的浪费啊！另外，某些类对象所携带的资源（比如某些JDBC的类）可能本身就很耗费内存，这些资源的延迟释放会造成很大的性能问题。

2. 可能不被调用—-有资源泄露的风险

很多同学以为finalize()总是会被调用，其实不然。

在某些情况下，finalize()压根儿不被调用。

比如在JVM退出的当口，内存中那些对象的finalize函数可能就不会被调用了。

估计有同学在打“runFinalizersOnExit”的主意，来确保所有的finalize在JVM退出前被调用。

很可惜也很遗憾，该方法从JDK 1.2开始，就已经被废弃了。即使该方法不被废弃，也是有很大的线程安全隐患滴！ 　　

从上述可以看出，一旦你依赖finalize()来帮你释放资源，那可是很不妙啊（有资源泄漏的危险）！

很多时候，资源泄露导致的性能问题更加严重，万万不可小看。

3. 对象可能在finalize函数调用时复活

本来，只有当某个对象已经失效（没有引用），垃圾回收器才会调用该对象的finalize函数。但是，万一碰上某个变态的程序员，在finalize()函数内部再把对象自身的引用（也就是this）重新保存在某处，也就相当于把自己复活了（因为这个对象重新有了引用，不再处于失效状态）。 为了防止发生这种诡异的事情，垃圾回收器只能在每次调用完finalize()之后再次去检查该对象是否还处于失效状态。这无形中又增加了JVM的开销。随便提一下。由于JDK的文档中规定了，JVM对于每一个类对象实例最多只会调用一次finalize()。所以，对于那些诈尸的实例，当它们真正死亡时，finalize()反而不会被调用了。这看起来是不是很奇怪？

4. 要记得自己做异常捕获

刚才在介绍finalize()调用机制时提到，一旦有异常抛出到finalize函数外面，会被垃圾回收线程捕获并丢弃。

也就是说，异常被忽略掉了（异常被忽略的危害，“这里”有提到）。

为了防止这种事儿，凡是finalize()中有可能抛出异常的代码，你都得写上try catch语句，自己进行捕获。

5. 小心线程安全

由于调用finalize()的是垃圾回收线程，和你自己代码的线程不是同一个线程；

甚至不同对象的finalize()可能会被不同的垃圾回收线程调用（比如使用“并行收集器”的时候）。

所以，当你在finalize()里面访问某些数据的时候，还得时刻留心线程安全的问题。

finalize 的执行过程(生命周期)

大致流程

首先，大致描述一下finalize流程：当对象变成(GC Roots)不可达时，GC会判断该对象是否覆盖了finalize方法，若未覆盖，则直接将其回收。

否则，若对象未执行过finalize方法，将其放入F-Queue队列，由一低优先级线程执行该队列中对象的finalize方法。

执行finalize方法完毕后，GC会再次判断该对象是否可达，若不可达，则进行回收，否则，对象“复活”。

具体的finalize流程：

对象可由两种状态，涉及到两类状态空间。

一是终结状态空间 F = {unfinalized, finalizable, finalized}；

二是可达状态空间 R = {reachable, finalizer-reachable, unreachable}。

各状态含义如下：

unfinalized: 新建对象会先进入此状态，GC并未准备执行其finalize方法，因为该对象是可达的

finalizable: 表示GC可对该对象执行finalize方法，GC已检测到该对象不可达。

正如前面所述，GC通过F-Queue队列和一专用线程完成finalize的执行

finalized: 表示GC已经对该对象执行过finalize方法

reachable: 表示GC Roots引用可达

finalizer-reachable(f-reachable)：表示不是reachable，但可通过某个finalizable对象可达

unreachable：对象不可通过上面两种途径可达

• 状态变迁图

变迁说明

新建对象首先处于[reachable, unfinalized]状态(A)

随着程序的运行，一些引用关系会消失，导致状态变迁，从reachable状态变迁到f-reachable(B, C, D)或unreachable(E, F)状态

若JVM检测到处于unfinalized状态的对象变成f-reachable或unreachable，JVM会将其标记为finalizable状态(G,H)。若对象原处于[unreachable, unfinalized]状态，则同时将其标记为f-reachable(H)。

在某个时刻，JVM取出某个finalizable对象，将其标记为finalized并在某个线程中执行其finalize方法。由于是在活动线程中引用了该对象，该对象将变迁到(reachable, finalized)状态(K或J)。该动作将影响某些其他对象从f-reachable状态重新回到reachable状态(L, M, N)

处于finalizable状态的对象不能同时是unreahable的，由第4点可知，将对象finalizable对象标记为finalized时会由某个线程执行该对象的finalize方法，致使其变成reachable。这也是图中只有八个状态点的原因

程序员手动调用finalize方法并不会影响到上述内部标记的变化，因此JVM只会至多调用finalize一次，即使该对象“复活”也是如此。

程序员手动调用多少次不影响JVM的行为

若JVM检测到finalized状态的对象变成unreachable，回收其内存(I)

若对象并未覆盖finalize方法，JVM会进行优化，直接回收对象（O）

注：System.runFinalizersOnExit()等方法可以使对象即使处于reachable状态，JVM仍对其执行finalize方法

测试代码

对象复活

[java]

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

public class GC {  
  
    public static GC SAVE_HOOK = null;  
  
    public static void main(String[] args) throws InterruptedException {  
        SAVE_HOOK = new GC();  
        SAVE_HOOK = null;  
        System.gc();  
        Thread.sleep(500);  
        if (null != SAVE_HOOK) { //此时对象应该处于(reachable, finalized)状态  
            System.out.println("Yes , I am still alive");  
        } else {  
            System.out.println("No , I am dead");  
        }  
        SAVE_HOOK = null;  
        System.gc();  
        Thread.sleep(500);  
        if (null != SAVE_HOOK) {  
            System.out.println("Yes , I am still alive");  
        } else {  
            System.out.println("No , I am dead");  
        }  
    }  
  
    @Override  
    protected void finalize() throws Throwable {  
        super.finalize();  
        System.out.println("execute method finalize()");  
        SAVE_HOOK = this;  
    }  
}

测试案例2

[java]

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

class C { 
    static A a; 
} 
   
class A { 
    B b; 
   
    public A(B b) { 
        this.b = b; 
    } 
   
    @Override 
    public void finalize() { 
        System.out.println("A finalize"); 
        C.a = this; 
    } 
} 
   
class B { 
    String name; 
    int age; 
   
    public B(String name, int age) { 
        this.name = name; 
        this.age = age; 
    } 
   
    @Override 
    public void finalize() { 
        System.out.println("B finalize"); 
    } 
   
    @Override 
    public String toString() { 
        return name + " is " + age; 
    } 
} 
   
public class Main { 
    public static void main(String[] args) throws Exception { 
        A a = new A(new B("allen", 20)); 
        a = null; 
   
        System.gc(); 
        Thread.sleep(5000); 
        System.out.println(C.a.b); 
    } 
}

我的理解:为方便起见, 把a,b两个变量所指的内存空间就叫做a和b

[java]

1
2

A a = new A(new B("allen" , 20)); //此时a和b都是reachable, unfinalized状态
a = null;

这之后, a和b的状态会在某一个时刻变成unreachable, unfinalized(但是b变成了unreachable还是f-reachable我不是很确定, 如果大家知道,欢迎补充^_^) 或者a和b直接变成f-reachable, unfianlized。

然后在某个时刻,GC检测到a和b处于unfinalized状态, 就将他们添加到F-queue,并将状态改为f-reachable finalizable.

之后分两种情况: 第一: GC从F-queue中首先取出a, 并被某个线程执行了finalize(), 也就相当于被某个活动的线程持有, a状态变成了reachable, finalized. 此时由于a被c对象所引用,所以之后不会变成unreachable finalized而被销毁(重生) 与此同时, b由于一直被a所引用, 所以b的状态变成了reachable, finalizable. 然后在某个时刻被从F-queue取出, 变成reachable, finalized状态

第二: GC从F-queue中首先取出b,并被某个线程执行了finalize(), 状态变成reachable finalized. 然后a也类似, 变成reachable finalized状态, 并被c引用, 重生

对象重生的代码2

[java]

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

public class GC
{
    public static GC SAVE_HOOK = null;
 
    public static void main(String[] args) throws InterruptedException, Throwable
    {
        SAVE_HOOK = new GC();
        SAVE_HOOK = null;
        System.gc();
        Thread.sleep(500);
        if (null != SAVE_HOOK)   //此时对象应该处于(reachable, finalized)状态
        {
            System.out.println("Yes , I am still alive");
        }
        else
        {
            System.out.println("No , I am dead");
        }
        SAVE_HOOK = null;
        System.gc();
        Thread.sleep(500);
        if (null != SAVE_HOOK)
        {
            System.out.println("Yes , I am still alive");
        }
        else
        {
            System.out.println("No , I am dead");
        }
    }
 
    @Override
    protected void finalize() throws Throwable
    {
        super.finalize();
        System.out.println("execute method finalize()");
        SAVE_HOOK = this;
    }
}

本文整理自

finalize 方法详解

when-is-the-finalize-method-called-in-java

java finalize方法总结、GC执行finalize的过程

Java禁止使用finalize方法

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

01-输入网址按下回车发生了什么？

1、浏览器从地址栏的输入中获得服务器的IP地址和端口号；（如果使用的是域名，会先使用域名解析功能解析出对呀的IP地址）

2、浏览器用TCP的三次握手与服务器建立连接；

3、浏览器向服务器发送拼好的报文；

4、服务器收到报文后处理请求，同样拼好报文再发给浏览器；

5、浏览器解析报文，渲染输出页面。

02-HTTP报文结构

HTTP协议的请求报文和响应报文的结构基本相同，由三大部分组成：

1. 起始行（start line）：描述请求或响应的基本信息；
2. 头部字段集合（header）：使用key-value形式更详细的说明报文；
3. 消息正文（entity）：实际传输的数据，它不一定是文本，可以是图片、视频等二进制数据。

这其中前两部分起始行和头部字段经常又合称为“请求头”或“响应头”，消息正文又称为“实体”，但与“header”对应，很多时候就直接称为“body”。

HTTP 协议规定报文必须有 header，但可以没有 body，而且在 header 之后必须要有一个“空行”，也就是“CRLF”，十六进制的“0D0A”。

所以，一个完整的 HTTP 报文就像是下图的这个样子，注意在 header 和 body 之间有一个“空行”。

请求行

请求报文里的起始行也就是请求行，它简要的描述了客户端想要如何操作服务器端的资源：

请求行由三部分构成：

1. 请求方法：是一个动词，如GET/POST，表示对资源的操作；
2. 请求目标：通常是一个URI，标记了请求方法要操作的资源；
3. 版本号：表示报文使用的HTTP协议版本。

状态行

响应报文里的起始行也就是状态行，意思是服务器响应的状态：

状态行也是由三部分构成：

1. 版本号：表示报文使用的HTTP协议版本；
2. 状态码：一个三位数，用代码的形式表示处理的结果；
3. 原因：作为数字状态码补充，是更详细的解释文字，帮助人理解原因。

头部字段

请求行或状态行再加上头部字段集合就构成了HTTP报文里完整的请求头或响应头。

头部字段是key-value的形式，key和value之间用”：“分隔，最后用CRLF换行表示字段结束。HTTP头字段非常灵活，不仅可以使用标准里Host、Connection等已有头，也可以任意添加自定义头，这就是HTTP协议带来了无限的扩展可能。

不过使用头字段需要注意下面几点：

1、字段名不区分大小写，例如“Host”也可以写成“host”，但首字母大写的可读性更好；

2、字段名里不允许出现空格，可以使用连字符“-”，但不能使用下划线“_”。例如，“test-name”是合法的字段名，而“test name”“test_name”是不正确的字段名；

3、字段名后面必须紧接着“:”，不能有空格，而“:”后的字段值前可以有多个空格；

4、字段的顺序是没有意义的，可以任意排列不影响语义；

5、字段原则上不能重复，除非这个字段本身的语义允许，例如 Set-Cookie。

常用头字段

HTTP 协议规定了非常多的头部字段，实现各种各样的功能，但基本上可以分为四大类：

1、通用字段：在请求头和响应头里都可以出现；

2、请求字段：仅能出现在请求头里，进一步说明请求信息或者额外的附加条件；

3、响应字段：仅能出现在响应头里，补充说明响应报文的信息；

4、实体字段：它实际上属于通用字段，但专门描述 body 的额外信息

Q&A

Q：试着解释下浏览器在点击页面链接后发生了哪些事情？

Q：如果是一个不存在的域名，那么浏览器的工作流程会是怎么样的呢？

Q：如果拼HTTP报文的时候，在头字段后多加了一个CRLF，导致出现了一个空行，会发生什么？

Q：讲头字段时说”：“后的空格可以有多个，那为什么绝大多数情况下都只使用一个空格呢？

本文整理自

http报文结构

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

维基百科中对 Zero-copy 的解释是

零拷贝技术是指计算机执行操作时，CPU不需要先将数据从某处内存复制到另一个特定区域。这种技术通常用于通过网络传输文件时节省CPU周期和内存带宽。

维基百科里提到的零拷贝是在硬件和操作系统层面的，而本文主要介绍的是Netty在应用层面的优化。不过需要注意的是，零拷贝并非字面意义上的没有内存拷贝，而是避免多余的拷贝操作，即使是系统层的零拷贝也有从设备到内存，内存到设备的数据拷贝过程。

Netty 的零拷贝体现在以下几个方面

• ByteBuf 的 slice 操作并不会拷贝一份新的 ByteBuf 内存空间，而是直接借用原来的 ByteBuf ，只是独立地保存读写索引。
• Netty 提供了 CompositeByteBuf 类，可以将多个 ByteBuf 组合成一个逻辑上的 ByteBuf 。
• Netty 的 FileRegion 中包装了 NIO 的 FileChannel.transferTo()方法，该方法在底层系统支持的情况下会调用 sendfile 方法，从而在传输文件时避免了用户态的内存拷贝。
• Netty 的 PooledDirectByteBuf 等类中封装了 NIO 的 DirectByteBuffer ，而 DirectByteBuffer 是直接在 jvm 堆外分配的内存，省去了堆外内存向堆内存拷贝的开销。

下面来简单介绍下这几种方式。

slice 分片

以下以 AbstractUnpooledSlicedByteBuf 为例讲解 slice 的零拷贝原理，至于内存池化的实现 PooledSlicedByteBuf ，因为内存池要通过引用计数来控制内存的释放，所以代码里会出现很多与本文主题无关的逻辑，这里就不拿来举栗子了。

​

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

// 切片ByteBuf的构造函数，其中字段adjustment为切片ByteBuf相对于被切片ByteBuf的偏移
// 量，两个ByteBuf共用一块内存空间,字段buffer为实际存储数据的ByteBuf
AbstractUnpooledSlicedByteBuf(ByteBuf buffer, int index, int length) {
    super(length);
    checkSliceOutOfBounds(index, length, buffer);//检查slice是否越界
    
    if (buffer instanceof AbstractUnpooledSlicedByteBuf) {
        // 如果被切片ByteBuf也是AbstractUnpooledSlicedByteBuf对象
        this.buffer = ((AbstractUnpooledSlicedByteBuf) buffer).buffer;
        adjustment = ((AbstractUnpooledSlicedByteBuf) buffer).adjustment + index;
    } else if (buffer instanceof DuplicatedByteBuf) {
        // 如果被切片ByteBuf为DuplicatedByteBuf对象，则
        // 用unwrap得到实际存储数据的ByteBuf赋值buffer
        this.buffer = buffer.unwrap();
        adjustment = index;
    } else {
        // 如果被切片ByteBuf为一般ByteBuf对象，则直接赋值buffer
        this.buffer = buffer;
        adjustment = index;
    }

    initLength(length);
    writerIndex(length);
}

以上为 AbstractUnpooledSlicedByteBuf 类的构造函数，比较简单，就不详细介绍了。

下面来看看 AbstractUnpooledSlicedByteBuf 对 ByteBuf 接口的实现代码，以 getBytes 方法为例：

​

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

@Override
public ByteBuf getBytes(int index, ByteBuffer dst) {
    checkIndex0(index, dst.remaining());//检查是否越界
    unwrap().getBytes(idx(index), dst);
    return this;
}

@Override
public ByteBuf unwrap() {
    return buffer;
}

private int idx(int index) {
    return index + adjustment;
}

这是 AbstractUnpooledSlicedByteBuf 重载的 getBytes 方法，可以看到 AbstractUnpooledSlicedByteBuf 是直接在封装的 ByteBuf 上取的字节，但是重新计算了索引，加上了相对偏移量。

CompositeByteBuf

在有些场景里，我们的数据会分散在多个 ByteBuf 上，但是我们又希望将这些 ByteBuf 聚合在一个 ByteBuf 里处理。这里最直观的想法是将所有 ByteBuf 的数据拷贝到一个 ByteBuf 上，但是这样会有大量的内存拷贝操作，产生很大的CPU开销。

而 CompositeByteBuf 可以很好地解决这个问题，正如名字一样，这是一个复合 ByteBuf ，内部由很多的 ByteBuf 组成，但 CompositeByteBuf 给它们做了一层封装，可以直接以 ByteBuf 的接口操作它们。

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

/**
 * Precondition is that {@code buffer != null}.
 */
private int addComponent0(boolean increaseWriterIndex, int cIndex, ByteBuf buffer) {
    assert buffer != null;
    boolean wasAdded = false;
    try {
        // 检查新增的component的索引是否合法
        checkComponentIndex(cIndex);

        // buffer的长度
        int readableBytes = buffer.readableBytes();

        // No need to consolidate - just add a component to the list.
        @SuppressWarnings("deprecation")
        // 统一为大端ByteBuf
        Component c = new Component(buffer.order(ByteOrder.BIG_ENDIAN).slice());
        if (cIndex == components.size()) {
            // 如果索引等于components的大小，则加在components尾部
            wasAdded = components.add(c);
            if (cIndex == 0) {
                // 如果components中只有一个元素
                c.endOffset = readableBytes;
            } else {
                // 如果components中有多个元素
                Component prev = components.get(cIndex - 1);
                c.offset = prev.endOffset;
                c.endOffset = c.offset + readableBytes;
            }
        } else {
            // 如果新的ByteBuf是插在components中间
            components.add(cIndex, c);
            wasAdded = true;
            if (readableBytes != 0) {
                // 如果components的大小不为0,则依次更新cIndex之后的
                // 所有components的offset和endOffset
                updateComponentOffsets(cIndex);
            }
        }
        if (increaseWriterIndex) {
            // 如果要更新writerIndex
            writerIndex(writerIndex() + buffer.readableBytes());
        }
        return cIndex;
    } finally {
        if (!wasAdded) {
            // 如果没添加成功，则释放ByteBuf
            buffer.release();
        }
    }
}

这是添加一个新的 ByteBuf 的逻辑，核心是 offset 和 endOffset ，分别指代一个 ByteBuf 在 CompositeByteBuf 中开始和结束的索引，它们唯一标记了这个 ByteBuf 在 CompositeByteBuf 中的位置。

弄清楚了这个，我们会发现上面的代码无外乎做了两件事：

1. 把 ByteBuf 封装成 Component 加到 components 合适的位置上
2. 使 components 里的每个 Component 的 offset 和 endOffset 值都正确

下面来看看 CompositeByteBuf 对 ByteBuf 接口的实现代码，同样以 getBytes 方法为例：

​

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

@Override
public CompositeByteBuf getBytes(int index, ByteBuf dst, int dstIndex, int length) {
    // 查索引是否越界
    checkDstIndex(index, length, dstIndex, dst.capacity());
    if (length == 0) {
        return this;
    }

    // 用二分搜索查找index对应的Component在components中的索引
    int i = toComponentIndex(index);
    // 循环读直至length为0
    while (length > 0) {
        Component c = components.get(i);
        ByteBuf s = c.buf;
        int adjustment = c.offset;
        // 取length和ByteBuf剩余字节数中的较小值
        int localLength = Math.min(length, s.capacity() - (index - adjustment));
        // 开始索引为index - c.offset，而不是0
        s.getBytes(index - adjustment, dst, dstIndex, localLength);
        index += localLength;
        dstIndex += localLength;
        length -= localLength;
        i ++;
    }
    return this;
}

/**
 * Return the index for the given offset
 */
public int toComponentIndex(int offset) {
    checkIndex(offset);

    for (int low = 0, high = components.size(); low <= high;) {
        int mid = low + high >>> 1;
        Component c = components.get(mid);
        if (offset >= c.endOffset) {
            low = mid + 1;
        } else if (offset < c.offset) {
            high = mid - 1;
        } else {
            return mid;
        }
    }

    throw new Error("should not reach here");
}

可以看到 CompositeByteBuf 在处理 index 时是先将其转换成对应 Component 在 components 中的索引，以及在 Component 中的偏移，然后从这个 Component 的这个偏移开始，往后循环取字节，直到读完。

NOTE：这里有个小trick，因为 components 是有序排列的，所以 toComponentIndex 做索引转换时没有直接遍历，而是用的二分查找。

本文整理自

Netty 之 Zero-copy 的实现（上）

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

首先你应当记住的：不管你传不传参数，不管你传入的长度为多少，在你用HashMap的时候，他的长度都是2的n次方，且最大长度为2的30次方

最大长度

在HashMap的源码中，最大长度这个常量值是这样定义的

1
2
3
4
5
6
7

/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
复制代码

这个值用在哪里呢？

• resize()函数，这个是用来扩容的
• tableSizeFor()，这个也是用来扩容的
• 构造函数中
• putEntries()，存放一组HashMap元素时，不是存放单个

为什么table长度一定是2的n次方

注意，源码中他们采用了延迟初始化操作，也就是table只有在用到的时候才初始化，如果你不对他进行put等操作的话，table的长度永远为”零”

主要有两个函数保证了他的长度为2的n次方

• tableSizeFor()
• resize()

至于计算过程以及加载过程，请参考我的这篇文章：table的长度到底是多少

这篇文章我从源码分析table的创建过程，包括上面提到的函数的调用，看了这个你一定明白为啥table的长度一定是2的n次方

当然我针对hashMap写的一部分源码的中文注释github上也有：HashMap源码中文注释

2的n次有什么好处

• 计算方便
• hash分布更均匀

分布均匀

如果不是2的n次方，那么有些位置上是永远不会被用到(我觉得比较牵强,前提是使用&优化%)

具体可以参考这篇博文，他用例子讲述了为什么，为啥长度要是2的n次方

计算方便

• 当容量一定是2^n时，h & (length - 1) == h % length
• 扩容后计算新位置，非常方便，相比 JDK1.7

JDK 1.8改动

在 JDK1.8 中，HashMap有了挺大的改动，包括

• 元素迁移算法(旧的到新的数组)
• 使用红黑树
• 链表为尾插法

其中我重点讲下元素迁移算法，JDK1.8的时候

首先看下java代码

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

// 将原来数组中的所有元素都 copy进新的数组
if(oldTab != null){
    for (int j = 0; j < oldCap; j++) {
        Entry e;

        if((e = oldTab[j]) != null){
            oldTab[j] = null;

            // 说明还没有成链，数组上只有一个
            if(e.next == null){
                // 重新计算 数组索引 值
                newTable[e.h & (newCap-1)] = e;

            }
            // 判断是否为树结构
            //else if (e instanceof TreeNode)


            // 如果不是树，只是链表,即长度还没有大于 8 进化成树
            else{
                // 扩容后，如果元素的 index 还是原来的。就使用这个lo前缀的
                Entry loHead=null, loTail =null;

                // 扩容后  元素index改变，那么就使用 hi前缀开头的
                Entry hiHead = null, hiTail = null;
                Entry next;
                do {
                    next = e.next;
                    //这个非常重要，也比较难懂，
                    // 将它和原来的长度进行相与，就是判断他的原来的hash的上一个  bit 位是否为 1。
                    //以此来判断他是在相同的索引还是table长度加上原来的索引
                    if((e.h & oldCap) == 0){
                        // 如果 loTail == null ,说明这个 位置上是第一次添加，没有哈希冲突
                        if(loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }
                    else{
                        if(hiTail == null)
                            loHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e ;
                    }

                }while ((e = next) != null);


                if(loTail != null){
                    loTail.next = null;
                    newTable[j] = loHead;
                }

                // 新的index 等于原来的 index+oldCap
                else {

                    hiTail.next = null;
                    newTable[j+oldCap] = hiHead;
                }

            }
        }

    }
}

我们看到上面源码的最后一句，newTable[j+oldCap] = hiHead;意思就是哪怕我们的元素从旧的数组迁移到新的数组，我们也不需要重新计算他的hash和新数组长度相与的值，只需要直接将现在的索引值+原来数组的长度即可

蓝色的表示不需要移动的，绿色的表示需要重新计算索引的，我们看到，他只是加了16(原来的数组table长度)

计算索引需要

我们注意到上面的源代码中，判断扩容后元素位置需不需要改变的时候，我们使用到了这个判断

if((e.h & oldCap) == 0)，

如果为0，那么就不需要改变，使用旧的索引即可；如果为1，那么就需要使用新的索引

为啥会这样呢？

• 如果元素的索引要变那么 hash&(newTable.length-1)一定是和 hash&(oldTable.length-1)+oldTable.length相等
• 因为table的长度一定是2的n次方，也就是oldCap 一定是2的n次方，也就是说 oldCap有且只有一位是1，而且这个位置在最高位；

我们来举个例子：

我们假设元素的hash值的后12位是 110111010111，数组原来的长度为16，扩容后数组长度为32

你可以试下下次扩容时，扩容到64时，索引变不变化。当然答案是不会变化，因为元素的hash值在那个位置为 0

对比1.7扩容

我们来对比JDK1.7 的方式，他如果要扩容，并且扩容后计算元素的索引的话要使用 indexFor函数

1
2
3
4
5
6
7

/** 
     * Returns index for hash code h. 
     */  
    static int indexFor(int h, int length) {  
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";  
        return h & (length-1);  
    }

也就是要把元素的hash值重新再和新的数组长度-1 再相与一次，会比较麻烦而且不优雅，完全没有我看到1.8计算方式的那种惊艳感。

本文整理自

为啥HashMap的长度一定是2的n次方

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

为什么链表的长度为8是变成红黑树？为什么为6时又变成链表？

因为，大部分的文章都是分析链表是怎么转换成红黑树的，但是并没有说明为什么当链表长度为8的时候才做转换动作。本人第一反应也是一样，只能初略的猜测是因为时间和空间的权衡

1
2
3
4
5
6

首先
当链表长度为6时 查询的平均长度为 n/2=3
红黑树为 log(6)=2.6
    
为8时 ： 链表  8/2=4   
         红黑树   log(8)=3

根据两者的函数图也可以知道随着bin中的数量越多那么红黑树花的时间远远比链表少，所以我觉得这也是原因之一。为7的时候两者应该是 链表花的时间小于红黑树的，但是为什么不是在7的时候转成链表呢，我觉得可能是因为把7当做一个链表和红黑树的过渡点。

事实上真的是因为考虑到时间复杂度所以才把是在8的时候进行转成红黑树吗？其实这并不是真正的原因

至于为什么阈值是8，我想，去源码中找寻答案应该是最可靠的途径。

8这个阈值定义在HashMap中，如下所示，这段注释只说明了8是bin（bin就是bucket，即HashMap中hashCode值一样的元素保存的地方）从链表转成树的阈值，但是并没有说明为什么是8：

1
2
3
4
5
6
7
8

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

我们继续往下看，在HashMap中有一段Implementation notes，笔者摘录了几段重要的描述，第一段如下所示，大概含义是当bin变得很大的时候，就会被转换成TreeNodes中的bin，其结构和TreeMap相似，也就是红黑树：

1
2
3

This map usually acts as a binned (bucketed) hash table, but
when bins get too large, they are transformed into bins of TreeNodes,
each structured similarly to those in java.util.TreeMap

继续往下看，TreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，链表长度达到8就转成红黑树，当长度降到6就转成普通bin。

这样就解析了为什么不是一开始就将其转换为TreeNodes，而是需要一定节点数才转为TreeNodes，说白了就是trade-off，空间和时间的权衡：

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

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins.  In
usages with well-distributed user hashCodes, tree bins are
rarely used.  Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of
resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5)*pow(0.5, k)/factorial(k)). 
The first values are:
0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million

这段内容还说到：当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。

通俗点将就是put进去的key进行计算hashCode时 只要选择计算hash值的算法足够好(hash碰撞率极低)，从而遵循泊松分布，使得桶中挂载的bin的数量等于8的概率非常小，从而转换为红黑树的概率也小，反之则概率大。

所以，之所以选择8，不是拍脑袋决定的，而是根据概率统计决定的。由此可见，发展30年的Java每一项改动和优化都是非常严谨和科学的。

本文整理自

为什么hashmap链表的长度为8时变成红黑树

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!