Https双向认证,实现系统间通讯双向认证

转自: https://blog.csdn.net/u012977486/article/details/88815621

一、Http

HyperText Transfer Protocol,超文本传输协议,是互联网上使用最广泛的一种协议,所有WWW文件必须遵循的标准。HTTP协议传输的数据都是未加密的,也就是明文的,因此使用HTTP协议传输隐私信息非常不安全。

使用TCP端口为:80

二、Https

Hyper Text Transfer Protocol over Secure Socket Layer,安全的超文本传输协议,网景公式设计了SSL(Secure Sockets Layer)协议用于对Http协议传输的数据进行加密,保证会话过程中的安全性。

使用TCP端口默认为443

三、SSL协议加密方式

SSL协议即用到了对称加密也用到了非对称加密(公钥加密),在建立传输链路时,SSL首先对对称加密的密钥使用公钥进行非对称加密,链路建立好之后,SSL对传输内容使用对称加密。

对称加密

速度高,可加密内容较大,用来加密会话过程中的消息

公钥加密

加密速度较慢,但能提供更好的身份认证技术,用来加密对称加密的密钥

四、单向认证

Https在建立Socket连接之前,需要进行握手,具体过程如下:

1、客户端向服务端发送SSL协议版本号、加密算法种类、随机数等信息。

2、服务端给客户端返回SSL协议版本号、加密算法种类、随机数等信息,同时也返回服务器端的证书,即公钥证书

3、客户端使用服务端返回的信息验证服务器的合法性,包括:

证书是否过期

发型服务器证书的CA是否可靠

返回的公钥是否能正确解开返回证书中的数字签名

服务器证书上的域名是否和服务器的实际域名相匹配

验证通过后,将继续进行通信,否则,终止通信

4、客户端向服务端发送自己所能支持的对称加密方案,供服务器端进行选择

5、服务器端在客户端提供的加密方案中选择加密程度最高的加密方式。

6、服务器将选择好的加密方案通过明文方式返回给客户端

7、客户端接收到服务端返回的加密方式后,使用该加密方式生成产生随机码,用作通信过程中对称加密的密钥,使用服务端返回的公钥进行加密,将加密后的随机码发送至服务器

8、服务器收到客户端返回的加密信息后,使用自己的私钥进行解密,获取对称加密密钥。 在接下来的会话中,服务器和客户端将会使用该密码进行对称加密,保证通信过程中信息的安全。

五、双向认证

双向认证和单向认证原理基本差不多,只是除了客户端需要认证服务端以外,增加了服务端对客户端的认证,具体过程如下:

1、客户端向服务端发送SSL协议版本号、加密算法种类、随机数等信息。

2、服务端给客户端返回SSL协议版本号、加密算法种类、随机数等信息,同时也返回服务器端的证书,即公钥证书

3、客户端使用服务端返回的信息验证服务器的合法性,包括:

证书是否过期

发型服务器证书的CA是否可靠

返回的公钥是否能正确解开返回证书中的数字签名

服务器证书上的域名是否和服务器的实际域名相匹配

验证通过后,将继续进行通信,否则,终止通信

4、服务端要求客户端发送客户端的证书,客户端会将自己的证书发送至服务端

5、验证客户端的证书,通过验证后,会获得客户端的公钥

6、客户端向服务端发送自己所能支持的对称加密方案,供服务器端进行选择

7、服务器端在客户端提供的加密方案中选择加密程度最高的加密方式

8、将加密方案通过使用之前获取到的公钥进行加密,返回给客户端

9、客户端收到服务端返回的加密方案密文后,使用自己的私钥进行解密,获取具体加密方式,而后,产生该加密方式的随机码,用作加密过程中的密钥,使用之前从服务端证书中获取到的公钥进行加密后,发送给服务端

10、服务端收到客户端发送的消息后,使用自己的私钥进行解密,获取对称加密的密钥,在接下来的会话中,服务器和客户端将会使用该密码进行对称加密,保证通信过程中信息的安全。

六. 代码实现

 1. 多个springboot项目,以两个springboot项目为例,这里暂且叫Client项目,Server项目。

 2. Client项目所在的服务器,Client.p12(客户端证书库) ,Client.cer(客户端公钥);

     Server项目所在的服务器,Server.p12(服务端证书库),Server.cer(服务端公钥);

4.实现步骤

 1. 创建springboot项目,Client ,Server 此处,请自行百度创建如何创建springboot项目。

 2. 使用jdk自带的keytool工具,生成Client和Server端相应的证书,步骤如下:

      a. Client端证书生成步骤:

           1.生成客户端 Client.p12文件    

keytool -genkey -v -alias Client -keyalg RSA -storetype PKCS12 -keystore C:\D\jdk1.8.0_161\Client.p12

设置密码: lq123456
注意事项:生成证书,您的名字与姓氏一项,应该填写服务器的ip(此处应该是域名,但是没有域名,故此处填写服务器ip)
           2 . 导出客户端公钥Client.cer 文件

keytool -keystore C:\D\jdk1.8.0_161\Client.p12  -export -alias Client -file C:\D\jdk1.8.0_161\Client.cer

      b. Server端证书生成步骤

           1.  生成服务端Server.p12文件

keytool -genkey -v -alias Server  -keyalg RSA -storetype PKCS12 -keystore C:\D\jdk1.8.0_161\Server.p12

           设置密码: lq123456
   注意事项:生成证书,您的名字与姓氏一项,应该填写服务器的ip(此处应该是域名,但是没有域名,故此处填写服务器ip)
           2.    导出服务端公钥Server.cer 文件

keytool -keystore C:\D\jdk1.8.0_161\Server.p12 -export -alias Server -file C:\D\jdk1.8.0_161\Server.cer

      c. 将Client端和Server端的公钥文件(.cer文件)导入双方系统的jre运行环境的cacerts证书库

           1.    将客户端公钥导入的服务端jdk信任库

keytool -import -file Client.cer -keystore C:\D\jdk1.8.0_161\jre\lib\security\cacerts –v

           2.    将服务端公钥导入到客户端的jdk信任库

 keytool -import -file Server.cer -keystore  C:\D\jdk1.8.0_161\jre\lib\security\cacerts –v

           3.  将客户端公钥导入到服务端Server.p12证书库

keytool -import -v -file C:\D\jdk1.8.0_161\Client.cer  -keystore C:\D\jdk1.8.0_161\server.p12

      注意事项:此处导入的密码为changeit,默认密码

至此,证书生成完成,证书库导入完成!

       d. 代码实现

            1.Server端

            第一步:在application.properties中添加如下配置:包括本地证书库和受信任证书配置

server.port=8090
server.address=10.119.165.171
server.ssl.key-store=classpath:server.p12
server.ssl.key-store-password=lq123456
server.ssl.key-alias=server
server.ssl.keyStoreType=JKS
 
 
server.ssl.trust-store=classpath:server.p12
server.ssl.trust-store-password=lq123456
server.ssl.client-auth=need
server.ssl.trust-store-type=JKS
server.ssl.trust-store-provider=SUN


             第二步:服务端接口开放


package com.example.server1.controller;
 
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;
 
/**
 * @author lucasliang
 * @date 01/03/2019 3:21 下午
 * @Description
 */
@RestController
@RequestMapping("/server")
public class ServerController {
 
  @RequestMapping("/hello")
  public String getUrlInfo() {
    return "************request https success************";
  }
 
}

     2. Client端

             第一步:在application.properties中添加如下配置:

 server.port=8091
 server.address=10.119.165.171
 server.ssl.key-store=classpath:client.p12
 server.ssl.key-store-password=lq123456
 server.ssl.key-alias=client
 server.ssl.keyStoreType=JKS

第二步:单元测试:

package com.example.client;
 
import java.io.FileInputStream;
import java.security.KeyStore;
import java.security.SecureRandom;
import javax.net.ssl.KeyManager;
import javax.net.ssl.KeyManagerFactory;
import javax.net.ssl.SSLContext;
import javax.net.ssl.TrustManager;
import javax.net.ssl.TrustManagerFactory;
import org.apache.http.HttpEntity;
import org.apache.http.client.methods.CloseableHttpResponse;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.conn.ssl.SSLConnectionSocketFactory;
import org.apache.http.impl.client.CloseableHttpClient;
import org.apache.http.impl.client.HttpClients;
import org.apache.http.util.EntityUtils;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;
 
/**
 * @author lucasliang
 * @date 04/03/2019 2:13 下午
 * @Description
 */
@SpringBootTest(classes = {Client1ApplicationTests.class})
@RunWith(SpringRunner.class)
public class P12CertTest {
 
  private final static String TEST_URL = "https://10.119.165.171:8090/server/hello";
 
  @Test
  public void getHKVesselTrip() throws Exception {
    KeyStore clientStore = KeyStore.getInstance("PKCS12");
    clientStore
        .load(new FileInputStream("C:\\D\\jdk1.8.0_161\\shuangxiang\\client_original.p12"),
            "lq123456".toCharArray());
 
    KeyManagerFactory kmf = KeyManagerFactory.getInstance(KeyManagerFactory.getDefaultAlgorithm());
    kmf.init(clientStore, "lq123456".toCharArray());
    KeyManager[] kms = kmf.getKeyManagers();
    TrustManagerFactory tmf = TrustManagerFactory
        .getInstance(TrustManagerFactory.getDefaultAlgorithm());
 
    KeyStore trustStore = KeyStore.getInstance("JKS");
    trustStore.load(new FileInputStream("C:\\D\\jdk1.8.0_161\\jre\\lib\\security\\cacerts"),
        "changeit".toCharArray());
    tmf.init(trustStore);
    TrustManager[] tms = tmf.getTrustManagers();
    SSLContext sslContext = SSLContext.getInstance("TLS");
    sslContext.init(kms, tms, new SecureRandom());
    SSLConnectionSocketFactory sslsf = new SSLConnectionSocketFactory(sslContext,
        SSLConnectionSocketFactory.BROWSER_COMPATIBLE_HOSTNAME_VERIFIER);
    CloseableHttpClient httpclient = HttpClients.custom().setSSLSocketFactory(sslsf).build();
    try {
      HttpGet httpget = new HttpGet(TEST_URL);
      System.out.println("executing request" + httpget.getRequestLine());
      CloseableHttpResponse response = httpclient.execute(httpget);
      try {
        HttpEntity entity = response.getEntity();
        if (entity != null) {
          System.out.println(EntityUtils.toString(entity));
        }
      } finally {
        response.close();
      }
    } finally {
 
      httpclient.close();
    }
 
  }
 
}

此时,Client端发送请求到Server端,请求成功,https双向认证完成!

关于Hibernate更新后, 获取的值仍是旧的问题

最近在更新商品库存的时候遇到一个诡异的问题:

1.取出本地商品信息,

2.查询总库库存, 将库存更新到本地

3.再取出商品和库存, 更新库存预警信息

结果在第三步骤出了问题: 取出来的库存是旧的, 不是刚更新的库存???

JAVA类 SkuRepo:

@Modifying
@Query(value = "update Sku set inv=:inv where id=:id")
void updateInv(@Param("id") String id, @Param("inv") int inv);

JAVA类 SkuServie:

//获取sku
Sku slSkuDB = skuRepo.findById("123456").orElse(null);
//获取总库库存
int inv = 0;
........
//更新库存
skuRepo.updateInv(slSkuDB.getId(), inv);
//发送事件
Event.publish(slSkuDB.getId());

JAVA类 SkuInvListener:
//监听库存改变事件
public void onInvChange(String skuId){
Sku slSkuDB = skuRepo.findById("123456").orElse(null);
int inv = slSkuDB.getInv();
................这里获取的库存是旧的
}

问题分析:

经过调试, 发现库存肯定更新成功的.

那么事件监听中, Sku对象不是从数据库取的, 而是上次Hibernate中已有的对象.

而且updateInv并没有更新Hibernate的缓存.

验证:

无奈, 只能断点debug: 发现”SkuServie”获取的Sku和”SkuInvListener”获取的Sku, 指向的Hibernate对象是同一个, 而且inv还是旧值. HQL语句也不会触发缓存更新!!!

处理:

更新库存
  skuRepo.updateInv(slSkuDB.getId(), inv);
改成:
  slSkuDB.setInv(inv);
  skuRepo.save(slSkuDB);

总结:

使用Hibernate一定要实时关注它的缓存问题(一级缓存和二级缓存)

更新对象,最好用Hibernate自带的更新操作, 任何Native SQL和HQL都不会同步到缓存中.

正则表达式 – 匹配XML标签

开发中经常用到html标签匹配, 这里做个整理:

1.匹配标签 <[^>]+>

private static final String REGEX = "<[^>]+>";
static Pattern pattern = Pattern.compile(REGEX, Pattern.CASE_INSENSITIVE);
 Matcher matcher = pattern.matcher(content);
    while (matcher.find()) {
      MatchResult result = matcher.toMatchResult();
      System.out.println(result.group(0));
    }

2. 获取标签里面的某个属性值 attr=\”([^\”]*)\”

private static final String REGEX = "name=\"([^\"]*)\""; //取name属性
static Pattern pattern = Pattern.compile(REGEX, Pattern.CASE_INSENSITIVE);
 Matcher matcher = pattern.matcher(tag);
    if(matcher.find()) {
      MatchResult result = matcher.toMatchResult();
      System.out.println(result.group(1));
    }

3. 结合标签, 直接获取所有input标签里面的name属性: <TAG[^>]*ATTR=\”([^\”]*)\”[^>]+>

private static final String REGEX = "<input[^>]*name=\"([^\"]*)\"[^>]+>";
static Pattern pattern = Pattern.compile(REGEX, Pattern.CASE_INSENSITIVE);
while (matcher.find()) {
      MatchResult result = matcher.toMatchResult();
      System.out.println(result.group(1));
    }

JDK8 tomcat启动时SecureRandom 非常慢解决办法

转:jdk8 tomcat启动很慢的问题

JDK8+tomcat8环境tomcat启动时SecureRandom 非常慢解决办法

 

JDK 8 + tomcat8 启动有时会出现 org.apache.catalina.util.SessionIdGeneratorBase- Creation of SecureRandom instance for session ID generation using [SHA1PRNG] took [413,255] milliseconds
耗时时间很长。
Tomcat 8启动很慢,且日志上无任何错误,在日志中查看到如下信息:
Log4j:[2015-10-29 15:47:11] INFO ReadProperty:172 – Loading properties file from class path resource [resources/jdbc.properties]
Log4j:[2015-10-29 15:47:11] INFO ReadProperty:172 – Loading properties file from class path resource [resources/common.properties]
29-Oct-2015 15:52:53.587 INFO [localhost-startStop-1] org.apache.catalina.util.SessionIdGeneratorBase.createSecureRandom Creation of SecureRandom instance for session ID generation using [SHA1PRNG] took [342,445] milliseconds.
原因

Tomcat 7/8都使用org.apache.catalina.util.SessionIdGeneratorBase.createSecureRandom类产生安全随机类SecureRandom的实例作为会话ID,这里花去了342秒,也即接近6分钟。

SHA1PRNG算法是基于SHA-1算法实现且保密性较强的伪随机数生成器。

在SHA1PRNG中,有一个种子产生器,它根据配置执行各种操作。

1)如果Java.security.egd 属性或securerandom.source属性指定的是”file:/dev/random”或”file:/dev/urandom”,那么JVM 会使用本地种子产生器NativeSeedGenerator,它会调用super()方法,即调用 SeedGenerator.URLSeedGenerator(/dev/random)方法进行初始化。

2)如果java.security.egd属性或securerandom.source属性指定的是其它已存在的URL,那么会调用SeedGenerator.URLSeedGenerator(url)方法进行初始化。

这就是为什么我们设置值为”file:///dev/urandom”或者值为”file:/./dev/random”都会起作用的原因。

在这个实现中,产生器会评估熵池(entropy pool)中的噪声数量。随机数是从熵池中进行创建的。当读操作时,/dev/random设备会只返回熵池中噪声的随机字节。/dev/random非 常适合那些需要非常高质量随机性的场景,比如一次性的支付或生成密钥的场景。

当熵池为空时,来自/dev/random的读操作将被阻塞,直到熵池收集到足够的环境噪声数据。这么做的目的是成为一个密码安全的伪随机数发生器,熵池要有尽可能大的输出。对于生成高质量的加密密钥或者是需要长期保护的场景,一定要这么做。

那么什么是环境噪声?

随机数产生器会手机来自设备驱动器和其它源的环境噪声数据,并放入熵池中。产生器会评估熵池中的噪声数据的数量。当熵池为空时,这个噪声数据的收集是比较花时间的。这就意味着,Tomcat在生产环境中使用熵池时,会被阻塞较长的时间。

解决

有两种解决办法:

1)在Tomcat环境中解决

可以通过配置JRE使用非阻塞的Entropy Source。

在catalina.sh中加入这么一行:-Djava.security.egd=file:/dev/./urandom 即可。

加入后再启动Tomcat,整个启动耗时下降到Server startup in 2912 ms。
2)在JVM环境中解决

打开$JAVA_PATH/jre/lib/security/java.security这个文件,找到下面的内容:

securerandom.source=file:/dev/urandom
替换成

securerandom.source=file:/dev/./urandom
经测试:在JVM环境中解决比较有效。

tomcat 调优

1. 关闭AJP端口

AJP是为 Tomcat 与 HTTP 服务器之间通信而定制的协议,能提供较高的通信速度和效率。如果tomcat前端放的是apache的时候,会使用到AJP这个连接器。若tomcat未与apache配合使用,因此不使用此连接器,因此需要注销掉该连接器。

 2. 开启线程池:

conf/server.xml中配置:

<Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
         minSpareThreads="100" maxQueueSize="100" prestartminSpareThreads="true"
         maxThreads="1000"/>

3. tomcat启动apr模式


Tomcat支持三种接收请求的处理方式:BIO、NIO、APR
1>、BIO模式:阻塞式I/O操作,表示Tomcat使用的是传统Java I/O操作(即java.io包及其子包)。
Tomcat7以下版本默认情况下是以bio模式运行的,由于每个请求都要创建一个线程来处理,线程开销较大,不能处理高并发的场景,在三种模式中性能也最低。
启动tomcat看到如下日志,表示使用的是BIO模式:
Sep 17, 2018 6:59:47 PM org.apache.coyote.AbstractProtocol start
INFO: Starting ProtocolHandler [“http-bio-8090”]
Sep 17, 2018 6:59:47 PM org.apache.coyote.AbstractProtocol start
INFO: Starting ProtocolHandler [“ajp-bio-8009”]


2>、NIO模式:是Java SE 1.4及后续版本提供的一种新的I/O操作方式(即java.nio包及其子包)。
是一个基于缓冲区、并能提供非阻塞I/O操作的Java API,它拥有比传统I/O操作(bio)更好的并发运行性能。
要让Tomcat以nio模式来运行比较简单,只需要在Tomcat安装目录/conf/server.xml文件中将如下配置:

<Connector port="9080" protocol="HTTP/1.1"
               connectionTimeout="20000"
               redirectPort="9443" URIEncoding="utf-8" />

修改成:

<Connector executor="tomcatThreadPool" port="9080" protocol="org.apache.coyote.http11.Http11AprProtocol"
               connectionTimeout="20000"
               redirectPort="9443" URIEncoding="utf-8" />


注意:Tomcat8以上版本,默认使用的就是NIO模式,不需要额外修改

2>、APR模式:简单理解,就是从操作系统级别解决异步IO问题,大幅度的提高服务器的处理和响应性能, 也是Tomcat运行高并发应用的首选模式。
启用这种模式稍微麻烦一些,需要安装一些依赖库,介绍安装步聚:

#install apr
wget http://mirrors.cnnic.cn/apache/apr/apr-1.6.3.tar.gz
tar zxvf apr-1.6.3.tar.gz -C /usr/local/
cd apr-1.6.3
./configure --prefix=/usr/local/apr
make & make install
#install apr-util
wget http://mirrors.cnnic.cn/apache/apr/apr-util-1.6.1.tar.gz
tar zxvf apr-util-1.6.1.tar.gz -C /usr/local/
cd apr-util-1.6.1
./configure --prefix=/usr/local/apr-util --with-apr=/usr/local/apr
make & make install

备注: 如果报错:xml/apr_xml.c:35:19: fatal error: expat.h: No such file or directory

         则说明少了expat库,yum install expat-devel安装该库

#其他插件
# yum install apr-devel
yum install openssl-devel
yum install gcc
yum install make
#安装tomcat-native
进入tomcat的bin目录,解压
tar -xvzf tomcat-native.tar.gz -C /usr/local
cd /usr/local
mv tomcat-native-1.1.29-src/ tomcat-native-1.1.29
cd /usr/local/tomcat-native-1.1.29/jni/native
./configure --with-apr=/usr/local/apr --with-java-home=/usr/local/java
make && make install

#配置apr
编辑$TOMCAT_HOME/bin/catalina.sh文件,在虚拟机启动参数JAVA_OPTS中添加java.library.path参数,指定apr库的路径
JAVA_OPTS=”$JAVA_OPTS -Djava.library.path=/usr/local/apr/lib”

Tomcat8以下版本,需要指定运行模式,
然后进入tomcat安装目录,编辑配置文件:conf/server.xml,
将protocol从HTTP/1.1改成org.apache.coyote.http11.Http11AprProtocol

<Connector executor="tomcatThreadPool" port="9080" protocol="org.apache.coyote.http11.Http11AprProtocol"
               connectionTimeout="20000"
               redirectPort="9443" URIEncoding="utf-8" />

其他参考:https://blog.csdn.net/huiyunfei/article/details/79165120

RESTful API 设计最佳实践

 

RESTful API 设计最佳实践

 
摘要:目前互联网上充斥着大量的关于RESTful API(为了方便,以后API和RESTful API 一个意思)如何设计的文章,然而却没有一个”万能“的设计标准:如何鉴权?API格式如何?你的API是否应该加入版本信息?

背景

目前互联网上充斥着大量的关于RESTful API(为了方便,以后API和RESTful API 一个意思)如何设计的文章,然而却没有一个”万能“的设计标准:如何鉴权?API格式如何?你的API是否应该加入版本信息?当你开始写一个app的时候,特别是后端模型部分已经写完的时候,你不得不殚精竭虑的设计和实现自己app的public API部分。因为一旦发布,对外发布的API将会很难改变。

在给SupportedFu设计API的时候,我试图以实用的角度来解决上面提到的问题。我希望可以设计出容易使用,容易部署,并且足够灵活的API,本文因此而生。

API设计的基本要求

网上的很多关于API设计的观点都十分”学院派“,它们也许更有理论基础,但是有时却和现实世界脱轨(因此我是自由派)。所以我这篇文章的目标是从实践的角度出发,给出当前网络应用的API设计最佳实践(当然,是我认为的最佳了~),如果觉得不合适,我不会遵从标准。当然作为设计的基础,几个必须的原则还是要遵守的:

 

  1. 当标准合理的时候遵守标准。
  2. API应该对程序员友好,并且在浏览器地址栏容易输入。
  3. API应该简单,直观,容易使用的同时优雅。
  4. API应该具有足够的灵活性来支持上层ui。
  5. API设计权衡上述几个原则。

 

需要强调的是:API的就是程序员的UI,和其他UI一样,你必须仔细考虑它的用户体验!

使用RESTful URLs 和action.

虽然前面我说没有一个万能的API设计标准。但确实有一个被普遍承认和遵守:RESTfu设计原则。它被Roy Felding提出(在他的”基于网络的软件架构“论文中第五章)。而REST的核心原则是将你的API拆分为逻辑上的资源。这些资源通过http被操作(GET ,POST,PUT,DELETE)。

那么我应该如何拆分出这些资源呢?

显然从API用户的角度来看,”资源“应该是个名词。即使你的内部数据模型和资源已经有了很好的对应,API设计的时候你仍然不需要把它们一对一的都暴露出来。这里的关键是隐藏内部资源,暴露必需的外部资源。

在SupportFu里,资源是 ticket、user、group。

一旦定义好了要暴露的资源,你可以定义资源上允许的操作,以及这些操作和你的API的对应关系:

 

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

 

可以看出使用REST的好处在于可以充分利用http的强大实现对资源的CURD功能。而这里你只需要一个endpoint:/tickets,再没有其他什么命名规则和url规则了,cool!

这个endpoint的单数复数

一个可以遵从的规则是:虽然看起来使用复数来描述某一个资源实例看起来别扭,但是统一所有的endpoint,使用复数使得你的URL更加规整。这让API使用者更加容易理解,对开发者来说也更容易实现。

如何处理关联?关于如何处理资源之间的管理REST原则也有相关的描述:

 

  • GET /tickets/12/messages- Retrieves list of messages for ticket #12
  • GET /tickets/12/messages/5- Retrieves message #5 for ticket #12
  • POST /tickets/12/messages- Creates a new message in ticket #12
  • PUT /tickets/12/messages/5- Updates message #5 for ticket #12
  • PATCH /tickets/12/messages/5- Partially updates message #5 for ticket #12
  • DELETE /tickets/12/messages/5- Deletes message #5 for ticket #12

 

其中,如果这种关联和资源独立,那么我们可以在资源的输出表示中保存相应资源的endpoint。然后API的使用者就可以通过点击链接找到相关的资源。如果关联和资源联系紧密。资源的输出表示就应该直接保存相应资源信息。(例如这里如果message资源是独立存在的,那么上面 GET /tickets/12/messages就会返回相应message的链接;相反的如果message不独立存在,他和ticket依附存在,则上面的API调用返回直接返回message信息)

不符合CURD的操作

对这个令人困惑的问题,下面是一些解决方法:

 

  1. 重构你的行为action。当你的行为不需要参数的时候,你可以把active对应到activated这个资源,(更新使用patch).
  2. 以子资源对待。例如:GitHub上,对一个gists加星操作:PUT /gists/:id/star 并且取消星操作:DELETE /gists/:id/star.
  3. 有时候action实在没有难以和某个资源对应上例如search。那就这么办吧。我认为API的使用者对于/search这种url也不会有太大意见的(毕竟他很容易理解)。只要注意在文档中写清楚就可以了。

 

永远使用SSL

毫无例外,永远都要使用SSL。你的应用不知道要被谁,以及什么情况访问。有些是安全的,有些不是。使用SSL可以减少鉴权的成本:你只需要一个简单的令牌(token)就可以鉴权了,而不是每次让用户对每次请求签名。

值得注意的是:不要让非SSL的url访问重定向到SSL的url。

文档

文档和API本身一样重要。文档应该容易找到,并且公开(把它们藏到pdf里面或者存到需要登录的地方都不太好)。文档应该有展示请求和输出的例子:或者以点击链接的方式或者通过curl的方式(请见openstack的文档)。如果有更新(特别是公开的API),应该及时更新文档。文档中应该有关于何时弃用某个API的时间表以及详情。使用邮件列表或者博客记录是好方法。

版本化

在API上加入版本信息可以有效的防止用户访问已经更新了的API,同时也能让不同主要版本之间平稳过渡。关于是否将版本信息放入url还是放入请求头有过争论:API version should be included in the URL or in a header. 学术界说它应该放到header里面去,但是如果放到url里面我们就可以跨版本的访问资源了。。(参考openstack)。

strip使用的方法就很好:它的url里面有主版本信息,同时请求头俩面有子版本信息。这样在子版本变化过程中url的稳定的。变化有时是不可避免的,关键是如何管理变化。完整的文档和合理的时间表都会使得API使用者使用的更加轻松。

结果过滤,排序,搜索:

url最好越简短越好,和结果过滤,排序,搜索相关的功能都应该通过参数实现(并且也很容易实现)。

过滤:为所有提供过滤功能的接口提供统一的参数。例如:你想限制get /tickets 的返回结果:只返回那些open状态的ticket–get /tickektsstate=open这里的state就是过滤参数。

排序:和过滤一样,一个好的排序参数应该能够描述排序规则,而不业务相关。复杂的排序规则应该通过组合实现:

 

  • GET /ticketssort=-priority- Retrieves a list of tickets in descending order of priority
  • GET /ticketssort=-priority,created_at- Retrieves a list of tickets in descending order of priority. Within a specific priority, older tickets are ordered first

 

这里第二条查询中,排序规则有多个rule以逗号间隔组合而成。

搜索:有些时候简单的排序是不够的。我们可以使用搜索技术(ElasticSearch和Lucene)来实现(依旧可以作为url的参数)。

 

  • GET /ticketsq=return&state=open&sort=-priority,created_at- Retrieve the highest priority open tickets mentioning the word ‘return’

 

对于经常使用的搜索查询,我们可以为他们设立别名,这样会让API更加优雅。例如:
get /ticketsq=recently_closed -> get /tickets/recently_closed.

限制API返回值的域

有时候API使用者不需要所有的结果,在进行横向限制的时候(例如值返回API结果的前十项)还应该可以进行纵向限制。并且这个功能能有效的提高网络带宽使用率和速度。可以使用fields查询参数来限制返回的域例如:
GET /ticketsfields=id,subject,customer_name,updated_at&state=open&sort=-updated_at

更新和创建操作应该返回资源

PUT、POST、PATCH 操作在对资源进行操作的时候常常有一些副作用:例如created_at,updated_at 时间戳。为了防止用户多次的API调用(为了进行此次的更新操作),我们应该会返回更新的资源(updated representation.)例如:在POST操作以后,返回201 created 状态码,并且包含一个指向新资源的url作为返回头

是否需要 “HATEOAS

网上关于是否允许用户创建新的url有很大的异议(注意不是创建资源产生的url)。为此REST制定了HATEOAS来描述了和endpoint进行交互的时候,行为应该在资源的metadata返回值里面进行定义。

(译注:作者这里认为HATEOAS还不算成熟,我也不怎么理解这段就算了,读者感兴趣可以自己去原文查看)

只提供json作为返回格式

现在开始比较一下XML和json了。XML即冗长,难以阅读,又不适合各种编程语言解析。当然XML有扩展性的优势,但是如果你只是将它来对内部资源串行化,那么他的扩展优势也发挥不出来。很多应用(youtube,twitter,box)都已经开始抛弃XML了,我也不想多费口舌。

当然如果的你使用用户里面企业用户居多,那么可能需要支持XML。如果是这样的话你还有另外一个问题:你的http请求中的media类型是应该和accept 头同步还是和url?为了方便(browser explorability),应该是在url中(用户只要自己拼url就好了)。如果这样的话最好的方法是使用.xml或者.json的后缀。

命名方式?

是蛇形命令(下划线和小写)还是驼峰命名?如果使用json那么最好的应该是遵守JAVASCRIPT的命名方法-也就是说骆驼命名法。如果你正在使用多种语言写一个库,那么最好按照那些语言所推荐的,java,c#使用骆驼,python,ruby使用snake。

个人意见:我总觉得蛇形命令更好使一些,当然这没有什么理论的依据。有人说蛇形命名读起来更快,能达到20%,也不知道真假http://ieeexplore.ieee.org/xpl/articleDetails.jsptp=&arnumber=5521745

默认使用pretty print格式,使用gzip

只是使用空格的返回结果从浏览器上看总是觉得很恶心(一大坨有没有?~)。当然你可以提供url上的参数来控制使用“pretty print”,但是默认开启这个选项还是更加友好。格外的传输上的损失不会太大。相反你如果忘了使用gzip那么传输效率将会大大减少,损失大大增加。想象一个用户正在debug那么默认的输出就是可读的-而不用将结果拷贝到其他什么软件中在格式化-是想起来就很爽的事,不是么?

下面是一个例子:

 

$ curl https://API.github.com/users/veesahni > with-whitespace.txt
$ ruby -r json -e 'puts JSON JSON.parse(STDIN.read)' < with-whitespace.txt > without-whitespace.txt
$ gzip -c with-whitespace.txt > with-whitespace.txt.gz
$ gzip -c without-whitespace.txt > without-whitespace.txt.gz

 

输出如下:

 

  • without-whitespace.txt- 1252 bytes
  • with-whitespace.txt- 1369 bytes
  • without-whitespace.txt.gz- 496 bytes
  • with-whitespace.txt.gz- 509 bytes

 

在上面的例子中,多余的空格使得结果大小多出了8.5%(没有使用gzip),相反只多出了2.6%。据说:twitter使用gzip之后它的streaming API传输减少了80%(link:https://dev.twitter.com/blog/announcing-gzip-compression-streaming-APIs).

只在需要的时候使用“envelope”

很多API象下面这样返回结果:

 

[java] view plain copy print ?
 
  1. {
  2. “data” : {
  3. “id” : 123,
  4. “name” : “John”
  5. }
  6. }
{
  "data" : {
    "id" : 123,
    "name" : "John"
  }
}

 

 

理由很简单:这样做可以很容易扩展返回结果,你可以加入一些分页信息,一些数据的元信息等-这对于那些不容易访问到返回头的API使用者来说确实有用,但是随着“标准”的发展(cors和http://tools.ietf.org/html/rfc5988#page-6都开始被加入到标准中了),我个人推荐不要那么做。

何时使用envelope?

有两种情况是应该使用envelope的。如果API使用者确实无法访问返回头,或者API需要支持交叉域请求(通过jsonp)。
jsonp请求在请求的url中包含了一个callback函数参数。如果给出了这个参数,那么API应该返回200,并且把真正的状态码放到返回值里面(包装在信封里),例如:

 

  1. callback_function({
  2. status_code: 200,
  3. next_page: “https://..”,
  4. response: {
  5. … actual JSON response body …
  6. }
  7. })
callback_function({
  status_code: 200,
  next_page: "https://..",
  response: {
    ... actual JSON response body ... 
  }
})

 

 

同样为了支持无法方法返回头的API使用者,可以允许envelope=true这样的参数。

在post,put,patch上使用json作为输入

如果你认同我上面说的,那么你应该决定使用json作为所有的API输出格式,那么我们接下来考虑考虑API的输入数据格式。
很多的API使用url编码格式:就像是url查询参数的格式一样:单纯的键值对。这种方法简单有效,但是也有自己的问题:它没有数据类型的概念。这使得程序不得不根据字符串解析出布尔和整数,而且还没有层次结构–虽然有一些关于层次结构信息的约定存在可是和本身就支持层次结构的json比较一下还是不很好用。

当然如果API本身就很简单,那么使用url格式的输入没什么问题。但对于复杂的API你应该使用json。或者干脆统一使用json。
注意使用json传输的时候,要求请求头里面加入:Content-Type:applicatin/json.否则抛出415异常(unsupported media type)。

分页

分页数据可以放到“信封”里面,但随着标准的改进,现在我推荐将分页信息放到link header里面:http://tools.ietf.org/html/rfc5988#page-6。

使用link header的API应该返回一系列组合好了的url而不是让用户自己再去拼。这点在基于游标的分页中尤为重要。例如下面,来自github的文档

 

Link: <https://api.github.com/user/repos?page=3&per_page=100>; rel="next", 
<https://api.github.com/user/repos?page=50&per_page=100>; rel="last"

 

 

自动加载相关的资源

很多时候,自动加载相关资源非常有用,可以很大的提高效率。但是这却和RESTful的原则相背。为了如此,我们可以在url中添加参数:embed(或者expend)。embed可以是一个逗号分隔的串,例如:

 

GET /ticket/12embed=customer.name,assigned_user

 

 

对应的API返回值如下:

 

  1. {
  2. “id” : 12,
  3. “subject” : “I have a question!”,
  4. “summary” : “Hi, ….”,
  5. “customer” : {
  6. “name” : “Bob”
  7. },
  8. assigned_user: {
  9. “id” : 42,
  10. “name” : “Jim”,
  11. }
  12. }
{
  "id" : 12,
  "subject" : "I have a question!",
  "summary" : "Hi, ....",
  "customer" : {
    "name" : "Bob"
  },
  assigned_user: {
   "id" : 42,
   "name" : "Jim",
  }
}

 

 

值得提醒的是,这个功能有时候会很复杂,并且可能导致N+1 SELECT 问题

重写HTTP方法

有的客户端只能发出简单的GET 和POST请求。为了照顾他们,我们可以重写HTTP请求。这里没有什么标准,但是一个普遍的方式是接受X-HTTP-Method-Override请求头。

速度限制

为了避免请求泛滥,给API设置速度限制很重要。为此 RFC 6585 引入了HTTP状态码429(too many requests)。加入速度设置之后,应该提示用户,至于如何提示标准上没有说明,不过流行的方法是使用HTTP的返回头。

下面是几个必须的返回头(依照twitter的命名规则):

 

  • X-Rate-Limit-Limit :当前时间段允许的并发请求数
  • X-Rate-Limit-Remaining:当前时间段保留的请求数。
  • X-Rate-Limit-Reset:当前时间段剩余秒数

 

为什么使用当前时间段剩余秒数而不是时间戳?

时间戳保存的信息很多,但是也包含了很多不必要的信息,用户只需要知道还剩几秒就可以再发请求了这样也避免了clock skew问题

有些API使用UNIX格式时间戳,我建议不要那么干。为什么?HTTP 已经规定了使用 RFC 1123 时间格式

鉴权 Authentication

restful API是无状态的也就是说用户请求的鉴权和cookie以及session无关,每一次请求都应该包含鉴权证明。

通过使用ssl我们可以不用每次都提供用户名和密码:我们可以给用户返回一个随机产生的token。这样可以极大的方便使用浏览器访问API的用户。这种方法适用于用户可以首先通过一次用户名-密码的验证并得到token,并且可以拷贝返回的token到以后的请求中。如果不方便,可以使用OAuth 2来进行token的安全传输。

支持jsonp的API需要额外的鉴权方法,因为jsonp请求无法发送普通的credential。这种情况下可以在查询url中添加参数:access_token。注意使用url参数的问题是:目前大部分的网络服务器都会讲query参数保存到服务器日志中,这可能会成为大的安全风险。

注意上面说到的只是三种传输token的方法,实际传输的token可能是一样的。

缓存

HTTP提供了自带的缓存框架。你需要做的是在返回的时候加入一些返回头信息,在接受输入的时候加入输入验证。基本两种方法:

ETag:当生成请求的时候,在HTTP头里面加入ETag,其中包含请求的校验和和哈希值,这个值和在输入变化的时候也应该变化。如果输入的HTTP请求包含IF-NONE-MATCH头以及一个ETag值,那么API应该返回304 not modified状态码,而不是常规的输出结果。

Last-Modified:和etag一样,只是多了一个时间戳。返回头里的Last-Modified:包含了 RFC 1123 时间戳,它和IF-MODIFIED-SINCE一致。HTTP规范里面有三种date格式,服务器应该都能处理。

出错处理

就像html错误页面能够显示错误信息一样,API 也应该能返回可读的错误信息–它应该和一般的资源格式一致。API应该始终返回相应的状态码,以反映服务器或者请求的状态。API的错误码可以分为两部分,400系列和500系列,400系列表明客户端错误:如错误的请求格式等。500系列表示服务器错误。API应该至少将所有的400系列的错误以json形式返回。如果可能500系列的错误也应该如此。json格式的错误应该包含以下信息:一个有用的错误信息,一个唯一的错误码,以及任何可能的详细错误描述。如下:

 

  1. {
  2. “code” : 1234,
  3. “message” : “Something bad happened http://blog.jobbole.com/wp-includes/images/smilies/icon_sad.gif” alt=”:-(” class=”wp-smiley”> “,
  4. “description” : “More details about the error here”
  5. }
{
  "code" : 1234,
  "message" : "Something bad happened :-( ",
  "description" : "More details about the error here"
}

 

 

对PUT,POST,PATCH的输入的校验也应该返回相应的错误信息,例如:

 

  1. “code” : 1024,
  2. “message” : “Validation Failed”,
  3. “errors” : [
  4. {
  5. “code” : 5432,
  6. “field” : “first_name”,
  7. “message” : “First name cannot have fancy characters”
  8. },
  9. {
  10. “code” : 5622,
  11. “field” : “password”,
  12. “message” : “Password cannot be blank”
  13. }
  14. ]
  15. }
{
  "code" : 1024,
  "message" : "Validation Failed",
  "errors" : [
    {
      "code" : 5432,
      "field" : "first_name",
      "message" : "First name cannot have fancy characters"
    },
    {
       "code" : 5622,
       "field" : "password",
       "message" : "Password cannot be blank"
    }
  ]
}

 

 

HTTP 状态码

 

200 ok  - 成功返回状态,对应,GET,PUT,PATCH,DELETE.
 201 created  - 成功创建。
 304 not modified   - HTTP缓存有效。
 400 bad request   - 请求格式错误。
 401 unauthorized   - 未授权。
 403 forbidden   - 鉴权成功,但是该用户没有权限。
 404 not found - 请求的资源不存在
 405 method not allowed - 该http方法不被允许。
 410 gone - 这个url对应的资源现在不可用。
 415 unsupported media type - 请求类型错误。
 422 unprocessable entity - 校验错误时用。
 429 too many request - 请求过多。

JAVA – 锁介绍

在介绍锁之前我们先介绍一个线程不安全的例子,一个全局的list,开2个线程往里面插入数据,代码如下:

  1. package com.jvm.day6.lock.demo;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.List;  
  5.   
  6. /** 
  7.  * 测试都线程共享一个变量带来的现象 
  8.  * @Author:xuehan 
  9.  * @Date:2016年3月20日下午3:35:29 
  10.  */  
  11. class NumberAdd implements Runnable{  
  12.       
  13.     public static  List<Integer> numberList =new ArrayList<Integer>();  
  14.     public static int startNum;  
  15.     public NumberAdd(int startNum){  
  16.         this.startNum = startNum;  
  17.     }  
  18.     @Override  
  19.     public void run() {  
  20.         int count = 0;  
  21.         while(count < 1000000){  
  22.             numberList.add(count ++ );  
  23.             startNum = startNum + 2;  
  24.               
  25.         }  
  26.     }  
  27. }  
  28. public class Test{  
  29.     public static void main(String[] args) throws Exception {  
  30.         Thread t1 = new Thread(new NumberAdd(1));  
  31.         Thread t2 = new Thread(new NumberAdd(0));  
  32.         t1.start();  
  33.         t2.start();  
  34.         while(t1.isAlive() || t2.isAlive()){Thread.sleep(2);}  
  35.         System.out.println(“集合大小” + NumberAdd.numberList.size() );  
  36.         System.out.println( “最后一个值的大”  + NumberAdd.numberList.get(NumberAdd.numberList.size() – 1));  
  37.        for(int i = NumberAdd.numberList.size()  – 10 ;  i < NumberAdd.numberList.size() –1; i ++){  
  38.            System.out.println(NumberAdd.numberList.get(i));  
  39.        }  
  40.    
  41.     }  
  42. }  

 

 按照开始想的,集合里面应该有200万个数据了,结果却出现了数组越界的错误,为什么呢,这是因为ArrayList不是线程安全的,用来存放数据的elementData是共享的, 线程A往list里添加数据的时候刚验证大小通过,还没有插入,然后轮到线程B执行,线程B刚好插入了list该扩容的最后一个元素,然后list满了,线程A执行,A线程往集合里面插入元素,引起了数据越界。

 



 

 

jvm锁

每个对象都一个mark头,他的作用是:

Mark Word,对象头的标记,32位

描述对象的hash、锁信息,垃圾回收标记,年龄

指向锁记录的指针

指向monitor的指针

GC标记

偏向锁线程ID

 

偏向锁
jvm控制,可以设置jvm启动参数
大部分情况是没有竞争的,所以可以通过偏向来提高性能
所谓的偏向,就是偏心,即锁会偏向于当前已经占有锁的线程
将对象头Mark的标记设置为偏向,并将线程ID写入对象头Mark
只要没有竞争,获得偏向锁的线程,在将来进入同步块,不需要做同步
当其他线程请求相同的锁时,偏向模式结束
-XX:+UseBiasedLocking -jdk6需要手动打开
默认启用
在竞争激烈的场合,偏向锁会增加系统负担
偏向锁是系统自带的设置参数开启,java代码如下:
  1. package com.jvm.day6.lock;  
  2.   
  3. import java.util.List;  
  4. import java.util.Vector;  
  5.   
  6. /** 
  7.  *使用 偏向锁-XX:+UseBiasedLocking -XX:BiasedLockingStartupDelay=0 
  8.  * 不使用偏向锁-XX:-UseBiasedLocking 
  9.  * 根据测试下面代码使用偏向锁可提高150毫秒执行时间 150/2300,提高效率6%  
  10.  * @Author:xuehan 
  11.  * @Date:2016年3月19日下午12:06:15 
  12.  */  
  13. public class DeflectionLock {  
  14.         public static List<Integer> numberList =new Vector<Integer>();  
  15.         public static void main(String[] args) throws InterruptedException {  
  16.             System.out.println((int)‘l’);  
  17.             long begin=System.currentTimeMillis();  
  18.             int count=0;  
  19.             int startnum=0;  
  20.             while(count<10000000){  
  21.                 numberList.add(startnum);  
  22.                 startnum+=2;  
  23.                 count++;  
  24.             }  
  25.             long end=System.currentTimeMillis();  
  26.             System.out.println(end-begin);  
  27.   
  28.     }  
  29. }  
 根据我的写实偏向锁可以提高性能6%
轻量级锁 BasicObjectLock,这个锁是嵌入到线程栈中的,他有两部组成BasicLock和ptr to obj hold the lock,BasicLock里面存放着对象头,ptr to obj hold the lock为指向持有对象锁的指针
普通的锁处理性能不够理想,轻量级锁是一种快速的锁定方法。
如果对象没有被锁定
将对象头的Mark指针保存到锁对象中
将对象头设置为指向锁的指针(在线程栈空间中)

如果轻量级锁失败,表示存在竞争,升级为重量级锁(常规锁)

在没有锁竞争的前提下,减少传统锁使用OS互斥量产生的性能损耗

 

在竞争激烈时,轻量级锁会多做很多额外操作,导致性能下降

自旋锁
当竞争存在时,如果线程可以很快获得锁,那么可以不在OS层挂起线程,让线程做几个空操作(自旋)
JDK1.6中-XX:+UseSpinning开启
JDK1.7中,去掉此参数,改为内置实现
如果同步块很长,自旋失败,会降低系统性能
如果同步块很短,自旋成功,节省线程挂起切换时间,提升系统性能
 

上面的一些锁不是Java语言层面的锁优化方法

他们是内置于JVM中的获取锁的优化方法和获取锁的步骤

偏向锁可用会先尝试偏向锁

轻量级锁可用会先尝试轻量级锁

以上都失败,尝试自旋锁

再失败,尝试普通锁,使用OS互斥量在操作系统层挂起

 

我们可以从以下方面对锁进行优化

减少锁的时间

没必须放在同步块的代码尽量不要放在代码块里

减少锁的粒度

将大对象,拆成小对象,大大增加并行度,降低锁竞争

 

偏向锁,轻量级锁成功率提高

实现的例子如ConcurrentHashMap

使用若干个Segment :Segment<K,V>[] segments

Segment中维护HashEntry<K,V>

put操作时

先定位到Segment,锁定一个Segment,执行put

 

在减小锁粒度后, ConcurrentHashMap允许若干个线程同时进入

 

锁分离

根据功能进行锁分离

ReadWriteLock

读多写少的情况,可以提高性能



 
读写分离思想可以延伸,只要操作互不影响,锁就可以分离

LinkedBlockingQueue

队列

链表



 
锁粗化

通常情况下,为了保证多线程间的有效并发,会要求每个线程持有锁的时间尽量短,即在使用完公共资源后,应该立即释放锁。只有这样,等待在这个锁上的其他线程才能尽早的获得资源执行任务。但是,凡事都有一个度,如果对同一个锁不停的进行请求、同步和释放,其本身也会消耗系统宝贵的资源,反而不利于性能的优化

 

Java代码
  1. for(int i=0;i<1000;i++){  
  2.     synchronized(lock){}  
  3.           
  4. }  
  5. // 应该写成  
  6. synchronized(lock){  
  7.    for(int i =0; i < 1000; i ++){}  
  8. }  

 

这时候我们要增加锁的持有时间不要让请求和释放锁频繁的发生

 

锁消除

在java方法体里如果不是共享的变量不需要同步操作的,这时候jvm会自动的优化把锁去掉,如StingBuffer和Vector,使用锁消除

 

-server -XX:+DoEscapeAnalysis -XX:+EliminateLocks

关闭锁消除

 

-server -XX:+DoEscapeAnalysis -XX:-EliminateLocks

 

无锁

锁是悲观的操作

无锁是乐观的操作

无锁的一种实现方式

CAS(Compare And Swap),CAS是原子的

非阻塞的同步

CAS(V,E,N)

在应用层面判断多线程的干扰,如果有干扰,则通知线程重试,一般这样做会让程序变的复杂,但性能更加好。

Java 8系列之重新认识HashMap

转自:美团技术博客

HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的结构实现和功能原理。

Java为数据结构中的映射定义了一个接口java.util.Map,此接口主要有四个常用的实现类,分别是HashMap、Hashtable、LinkedHashMap和TreeMap,类继承关系如下图所示:

下面针对各个实现类的特点做一些说明:

(1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

(2) Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

通过上面的比较,我们知道了HashMap是Java的Map家族中一个普通成员,鉴于它可以满足大多数场景的使用条件,所以是使用频度最高的一个。下文我们主要结合源码,从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

搞清楚HashMap,首先需要知道HashMap是什么,即它的存储结构-字段;其次弄明白它能干什么,即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。

存储结构-字段

从结构实现来讲,HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,如下如所示。

这里需要讲明白两个问题:数据底层具体存储的是什么?这样的存储方式有什么优点呢?

(1) 从源码可知,HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组。我们来看Node[JDK1.8]是何物。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。

(2) HashMap就是使用哈希表来存储的。哈希表为解决冲突,可以采用开放地址法和链地址法等来解决问题,Java中HashMap采用了链地址法。链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。例如程序执行下面代码:

    map.put("美团","小美");

系统将调用”美团”这个key的hashCode()方法得到其hashCode 值(该方法适用于每个Java对象),然后再通过Hash算法的后两步运算(高位运算和取模运算,下文有介绍)来定位该键值对的存储位置,有时两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。

如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。

在理解Hash和扩容流程之前,我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知,构造函数就是对下面几个字段进行初始化,源码如下:

     int threshold;             // 所能容纳的key-value对极限 
     final float loadFactor;    // 负载因子
     int modCount;  
     int size;  

首先,Node[] table的初始化长度length(默认值是16),Load factor为负载因子(默认值是0.75),threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。

结合负载因子的定义公式可知,threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目,超过这个数目就重新resize(扩容),扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

size这个字段其实很好理解,就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数,具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159,Hashtable初始化桶大小为11,就是桶大小设计为素数的应用(Hashtable扩容后不能保证还是素数)。HashMap采用这种非常规设计,主要是为了在取模和扩容时做优化,同时为了减少冲突,HashMap定位哈希桶索引位置时,也加入了高位参与运算的过程。

这里存在一个问题,即使负载因子和Hash算法设计的再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。于是,在JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树。而当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。本文不再对红黑树展开讨论,想了解更多红黑树数据结构的工作原理可以参考http://blog.csdn.net/v_july_v/article/details/6105630

功能实现-方法

HashMap的内部功能实现很多,本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入展开讲解。

1. 确定哈希桶数组索引位置

不管增加、删除、查找键值对,定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,不用遍历链表,大大优化了查询的效率。HashMap定位数组索引位置,直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):

方法一:
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二:
static int indexFor(int h, int length) {  //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

这里的Hash算法本质上就是三步:取key的hashCode值、高位运算、取模运算

对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,模运算的消耗还是比较大的,在HashMap中是这样做的:调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙,它通过h & (table.length -1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

下面举例说明下,n为table的长度。

2. 分析HashMap的put方法

HashMap的put方法执行过程可以通过下图来理解,自己有兴趣可以去对比源码更清楚地研究学习。

>

①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

JDK1.8HashMap的put方法源码如下:

 1 public V put(K key, V value) {
 2     // 对key的hashCode()做hash
 3     return putVal(hash(key), key, value, false, true);
 4 }
 5 
 6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 7                boolean evict) {
 8     Node<K,V>[] tab; Node<K,V> p; int n, i;
 9     // 步骤①:tab为空则创建
10     if ((tab = table) == null || (n = tab.length) == 0)
11         n = (tab = resize()).length;
12     // 步骤②:计算index,并对null做处理 
13     if ((p = tab[i = (n - 1) & hash]) == null) 
14         tab[i] = newNode(hash, key, value, null);
15     else {
16         Node<K,V> e; K k;
17         // 步骤③:节点key存在,直接覆盖value
18         if (p.hash == hash &&
19             ((k = p.key) == key || (key != null && key.equals(k))))
20             e = p;
21         // 步骤④:判断该链为红黑树
22         else if (p instanceof TreeNode)
23             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
24         // 步骤⑤:该链为链表
25         else {
26             for (int binCount = 0; ; ++binCount) {
27                 if ((e = p.next) == null) {
28                     p.next = newNode(hash, key,value,null);
                        //链表长度大于8转换为红黑树进行处理
29                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
30                         treeifyBin(tab, hash);
31                     break;
32                 }
                    // key已经存在直接覆盖value
33                 if (e.hash == hash &&
34                     ((k = e.key) == key || (key != null && key.equals(k)))) 
35							break;
36                 p = e;
37             }
38         }
39         
40         if (e != null) { // existing mapping for key
41             V oldValue = e.value;
42             if (!onlyIfAbsent || oldValue == null)
43                 e.value = value;
44             afterNodeAccess(e);
45             return oldValue;
46         }
47     }

48     ++modCount;
49     // 步骤⑥:超过最大容量 就扩容
50     if (++size > threshold)
51         resize();
52     afterNodeInsertion(evict);
53     return null;
54 }

3. 扩容机制

扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。

我们分析下resize的源码,鉴于JDK1.8融入了红黑树,较复杂,为了便于理解我们仍然使用JDK1.7的代码,好理解一些,本质上区别不大,具体区别后文再说。

 1 void resize(int newCapacity) {   //传入新的容量
 2     Entry[] oldTable = table;    //引用扩容前的Entry数组
 3     int oldCapacity = oldTable.length;         
 4     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
 5         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
 6         return;
 7     }
 8  
 9     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
10     transfer(newTable);                         //!!将数据转移到新的Entry数组里
11     table = newTable;                           //HashMap的table属性引用新的Entry数组
12     threshold = (int)(newCapacity * loadFactor);//修改阈值
13 }

这里就是使用一个容量更大的数组来代替已有的容量小的数组,transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

 1 void transfer(Entry[] newTable) {
 2     Entry[] src = table;                   //src引用了旧的Entry数组
 3     int newCapacity = newTable.length;
 4     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
 5         Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
 6         if (e != null) {
 7             src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
 8             do {
 9                 Entry<K,V> next = e.next;
10                 int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
11                 e.next = newTable[i]; //标记[1]
12                 newTable[i] = e;      //将元素放在数组上
13                 e = next;             //访问下一个Entry链上的元素
14             } while (e != null);
15         }
16     }
17 } 

newTable[i]的引用赋给了e.next,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话),这一点和Jdk1.8有区别,下文详解。在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。

下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。其中的哈希桶数组table的size=2, 所以key = 3、7、5,put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1,即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4,然后所有的Node重新rehash的过程。

下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:

这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码,写的很赞,如下:

 1 final Node<K,V>[] resize() {
 2     Node<K,V>[] oldTab = table;
 3     int oldCap = (oldTab == null) ? 0 : oldTab.length;
 4     int oldThr = threshold;
 5     int newCap, newThr = 0;
 6     if (oldCap > 0) {
 7         // 超过最大值就不再扩充了,就只好随你碰撞去吧
 8         if (oldCap >= MAXIMUM_CAPACITY) {
 9             threshold = Integer.MAX_VALUE;
10             return oldTab;
11         }
12         // 没超过最大值,就扩充为原来的2倍
13         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
14                  oldCap >= DEFAULT_INITIAL_CAPACITY)
15             newThr = oldThr << 1; // double threshold
16     }
17     else if (oldThr > 0) // initial capacity was placed in threshold
18         newCap = oldThr;
19     else {               // zero initial threshold signifies using defaults
20         newCap = DEFAULT_INITIAL_CAPACITY;
21         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
22     }
23     // 计算新的resize上限
24     if (newThr == 0) {
25 
26         float ft = (float)newCap * loadFactor;
27         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
28                   (int)ft : Integer.MAX_VALUE);
29     }
30     threshold = newThr;
31     @SuppressWarnings({"rawtypes","unchecked"})
32         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
33     table = newTab;
34     if (oldTab != null) {
35         // 把每个bucket都移动到新的buckets中
36         for (int j = 0; j < oldCap; ++j) {
37             Node<K,V> e;
38             if ((e = oldTab[j]) != null) {
39                 oldTab[j] = null;
40                 if (e.next == null)
41                     newTab[e.hash & (newCap - 1)] = e;
42                 else if (e instanceof TreeNode)
43                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
44                 else { // 链表优化重hash的代码块
45                     Node<K,V> loHead = null, loTail = null;
46                     Node<K,V> hiHead = null, hiTail = null;
47                     Node<K,V> next;
48                     do {
49                         next = e.next;
50                         // 原索引
51                         if ((e.hash & oldCap) == 0) {
52                             if (loTail == null)
53                                 loHead = e;
54                             else
55                                 loTail.next = e;
56                             loTail = e;
57                         }
58                         // 原索引+oldCap
59                         else {
60                             if (hiTail == null)
61                                 hiHead = e;
62                             else
63                                 hiTail.next = e;
64                             hiTail = e;
65                         }
66                     } while ((e = next) != null);
67                     // 原索引放到bucket里
68                     if (loTail != null) {
69                         loTail.next = null;
70                         newTab[j] = loHead;
71                     }
72                     // 原索引+oldCap放到bucket里
73                     if (hiTail != null) {
74                         hiTail.next = null;
75                         newTab[j + oldCap] = hiHead;
76                     }
77                 }
78             }
79         }
80     }
81     return newTab;
82 }

在多线程使用场景中,应该尽量避免使用线程不安全的HashMap,而使用线程安全的ConcurrentHashMap。那么为什么说HashMap是线程不安全的,下面举例子说明在并发的多线程使用场景中使用HashMap可能造成死循环。代码例子如下(便于理解,仍然使用JDK1.7的环境):

public class HashMapInfiniteLoop {  

    private static HashMap<Integer,String> map = new HashMap<Integer,String>(20.75f);  
    public static void main(String[] args) {  
        map.put(5"C");  

        new Thread("Thread1") {  
            public void run() {  
                map.put(7, "B");  
                System.out.println(map);  
            };  
        }.start();  
        new Thread("Thread2") {  
            public void run() {  
                map.put(3, "A);  
                System.out.println(map);  
            };  
        }.start();        
    }  
} 

其中,map初始化为一个长度为2的数组,loadFactor=0.75,threshold=2*0.75=1,也就是说当put第二个key的时候,map就需要进行resize。

通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行;然后放开线程2的的断点,让线程2进行resize。结果如下图。

注意,Thread1的 e 指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。

线程一被调度回来执行,先是执行 newTalbe[i] = e, 然后是e = next,导致了e指向了key(7),而下一次循环的next = e.next导致了next指向了key(3)。

e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意:此时的key(7).next 已经指向了key(3), 环形链表就这样出现了。

于是,当我们用线程一调用map.get(11)时,悲剧就出现了——Infinite Loop。

HashMap中,如果key经过hash算法得出的数组索引位置全部不相同,即Hash算法非常好,那样的话,getKey方法的时间复杂度就是O(1),如果Hash算法技术的结果碰撞非常多,假如Hash算极其差,所有的Hash算法结果得出的索引位置一样,那样所有的键值对都集中到一个桶中,或者在一个链表中,或者在一个红黑树中,时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化,总体性能优于JDK1.7,下面我们从两个方面用例子证明这一点。

Hash较均匀的情况

为了便于测试,我们先写一个类Key,如下:

class Key implements Comparable<Key> {

    private final int value;

    Key(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(Key o) {
        return Integer.compare(this.value, o.value);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Key key = (Key) o;
        return value == key.value;
    }

    @Override
    public int hashCode() {
        return value;
    }
}

这个类复写了equals方法,并且提供了相当好的hashCode函数,任何一个值的hashCode都不会相同,因为直接使用value当做hashcode。为了避免频繁的GC,我将不变的Key实例缓存了起来,而不是一遍一遍的创建它们。代码如下:

public class Keys {

    public static final int MAX_KEY = 10_000_000;
    private static final Key[] KEYS_CACHE = new Key[MAX_KEY];

    static {
        for (int i = 0; i < MAX_KEY; ++i) {
            KEYS_CACHE[i] = new Key(i);
        }
    }

    public static Key of(int value) {
        return KEYS_CACHE[value];
    }
}

现在开始我们的试验,测试需要做的仅仅是,创建不同size的HashMap(1、10、100、……10000000),屏蔽了扩容的情况,代码如下:

   static void test(int mapSize) {

        HashMap<Key, Integer> map = new HashMap<Key,Integer>(mapSize);
        for (int i = 0; i < mapSize; ++i) {
            map.put(Keys.of(i), i);
        }

        long beginTime = System.nanoTime(); //获取纳秒
        for (int i = 0; i < mapSize; i++) {
            map.get(Keys.of(i));
        }
        long endTime = System.nanoTime();
        System.out.println(endTime - beginTime);
    }

    public static void main(String[] args) {
        for(int i=10;i<= 1000 0000;i*= 10){
            test(i);
        }
    }


在测试中会查找不同的值,然后度量花费的时间,为了计算getKey的平均时间,我们遍历所有的get方法,计算总的时间,除以key的数量,计算一个平均值,主要用来比较,绝对值可能会受很多环境因素的影响。结果如下:

通过观测测试结果可知,JDK1.8的性能要高于JDK1.7 15%以上,在某些size的区域上,甚至高于100%。由于Hash算法较均匀,JDK1.8引入的红黑树效果不明显,下面我们看看Hash不均匀的的情况。

Hash极不均匀的情况

假设我们又一个非常差的Key,它们所有的实例都返回相同的hashCode值。这是使用HashMap最坏的情况。代码修改如下:

class Key implements Comparable<Key> {

    //...

    @Override
    public int hashCode() {
        return 1;
    }
}

仍然执行main方法,得出的结果如下表所示:

从表中结果中可知,随着size的变大,JDK1.7的花费时间是增长的趋势,而JDK1.8是明显的降低趋势,并且呈现对数增长稳定。当一个链表太长的时候,HashMap会动态的将它替换成一个红黑树,这话的话会将时间复杂度从O(n)降为O(logn)。hash算法均匀和不均匀所花费的时间明显也不相同,这两种情况的相对比较,可以说明一个好的hash算法的重要性。

      测试环境:处理器为2.2 GHz Intel Core i7,内存为16 GB 1600 MHz DDR3,SSD硬盘,使用默认的JVM参数,运行在64位的OS X 10.10.1上。

(1) 扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容。

(2) 负载因子是可以修改的,也可以大于1,但是建议不要轻易修改,除非情况非常特殊。

(3) HashMap是线程不安全的,不要在并发的环境中同时操作HashMap,建议使用ConcurrentHashMap。

(4) JDK1.8引入红黑树大程度优化了HashMap的性能。

(5) 还没升级JDK1.8的,现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。

  1. JDK1.7&JDK1.8 源码。
  2. CSDN博客频道,HashMap多线程死循环问题,2014。
  3. 红黑联盟,Java类集框架之HashMap(JDK1.8)源码剖析,2015。
  4. CSDN博客频道, 教你初步了解红黑树,2010。
  5. Java Code Geeks,HashMap performance improvements in Java 8,2014。
  6. Importnew,危险!在HashMap中将可变对象用作Key,2014。
  7. CSDN博客频道,为什么一般hashtable的桶数会取一个素数,2013。

JAVA NIO基本使用

NIO中有几个核心对象:缓冲区(Buffer)、通道(Channel)、选择器(Selector)

缓冲区Buffer

缓冲区实际上是一个容器对象,更直接的说,其实就是一个数组,在NIO库中,所有数据都是用缓冲区处理的。在读取数据时,它是直接读到缓冲区中的; 在写入数据时,它也是写入到缓冲区中的;任何时候访问 NIO 中的数据,都是将它放到缓冲区中。而在面向流I/O系统中,所有数据都是直接写入或者直接将数据读取到Stream对象中。

import java.nio.IntBuffer;
 
public class TestIntBuffer {
	public static void main(String[] args) {
		// 分配新的int缓冲区,参数为缓冲区容量
		// 新缓冲区的当前位置将为零,其界限(限制位置)将为其容量。它将具有一个底层实现数组,其数组偏移量将为零。
		IntBuffer buffer = IntBuffer.allocate(8);
 
		for (int i = 0; i < buffer.capacity(); ++i) {
			int j = 2 * (i + 1);
			// 将给定整数写入此缓冲区的当前位置,当前位置递增
			buffer.put(j);
		}
 
		// 重设此缓冲区,将限制设置为当前位置,然后将当前位置设置为0
		buffer.flip();
 
		// 查看在当前位置和限制位置之间是否有元素
		while (buffer.hasRemaining()) {
			// 读取此缓冲区当前位置的整数,然后当前位置递增
			int j = buffer.get();
			System.out.print(j + "  ");
		}
 
	}
 
}

通道Channel

通道是一个对象,通过它可以读取和写入数据,当然了所有数据都通过Buffer对象来处理。我们永远不会将字节直接写入通道中,相反是将数据写入包含一个或者多个字节的缓冲区。同样不会直接从通道中读取字节,而是将数据从通道读入缓冲区,再从缓冲区获取这个字节。

使用NIO读取数据

在前面我们说过,任何时候读取数据,都不是直接从通道读取,而是从通道读取到缓冲区。所以使用NIO读取数据可以分为下面三个步骤: 
1. 从FileInputStream获取Channel 
2. 创建Buffer 
3. 将数据从Channel读取到Buffer中

import java.io.*;
import java.nio.*;
import java.nio.channels.*;
 
public class Program {
    static public void main( String args[] ) throws Exception {
        FileInputStream fin = new FileInputStream("c:\\test.txt");
        
        // 获取通道
        FileChannel fc = fin.getChannel();
        
        // 创建缓冲区
        ByteBuffer buffer = ByteBuffer.allocate(1024);
        
        // 读取数据到缓冲区
        fc.read(buffer);
        
        buffer.flip();
        
        while (buffer.remaining()>0) {
            byte b = buffer.get();
            System.out.print(((char)b));
        }
        
        fin.close();
    }
}

使用NIO写入数据

使用NIO写入数据与读取数据的过程类似,同样数据不是直接写入通道,而是写入缓冲区,可以分为下面三个步骤: 
1. 从FileInputStream获取Channel 
2. 创建Buffer 
3. 将数据从Channel写入到Buffer中

import java.io.*;
import java.nio.*;
import java.nio.channels.*;
 
public class Program {
    static private final byte message[] = { 83, 111, 109, 101, 32,
        98, 121, 116, 101, 115, 46 };
 
    static public void main( String args[] ) throws Exception {
        FileOutputStream fout = new FileOutputStream( "c:\\test.txt" );
        
        FileChannel fc = fout.getChannel();
        
        ByteBuffer buffer = ByteBuffer.allocate( 1024 );
        
        for (int i=0; i<message.length; ++i) {
            buffer.put( message[i] );
        }
        
        buffer.flip();
        
        fc.write( buffer );
        
        fout.close();
    }

选择器Selector注册和处理事件

NIO中实现非阻塞I/O的核心对象就是Selector,Selector就是注册各种I/O事件地 方,而且当那些事件发生时,就是这个对象告诉我们所发生的事件. 当有读或写等任何注册的事件发生时,可以从Selector中获得相应的SelectionKey,同时从 SelectionKey中可以找到发生的事件和该事件所发生的具体的SelectableChannel,以获得客户端发送过来的数据

使用NIO中非阻塞I/O编写服务器处理程序,大体上可以分为下面三个步骤:

1. 向Selector对象注册感兴趣的事件 
2. 从Selector中获取感兴趣的事件 
3. 根据不同的事件进行相应的处理

/*
 * 注册事件
 * */
protected Selector getSelector() throws IOException {
    // 创建Selector对象
    Selector sel = Selector.open();
    
    // 创建可选择通道,并配置为非阻塞模式
    ServerSocketChannel server = ServerSocketChannel.open();
    server.configureBlocking(false);
    
    // 绑定通道到指定端口
    ServerSocket socket = server.socket();
    InetSocketAddress address = new InetSocketAddress(port);
    socket.bind(address);
    
    // 向Selector中注册感兴趣的事件
    server.register(sel, SelectionKey.OP_ACCEPT); 
    return sel;
}

/*
 * 开始监听
 * */ 
public void listen() { 
    System.out.println("listen on " + port);
    try { 
        while(true) { 
            // 该调用会阻塞,直到至少有一个事件发生
            selector.select(); 
            Set<SelectionKey> keys = selector.selectedKeys();
            Iterator<SelectionKey> iter = keys.iterator();
            while (iter.hasNext()) { 
                SelectionKey key = (SelectionKey) iter.next(); 
                iter.remove(); 
                process(key); 
            } 
        } 
    } catch (IOException e) { 
        e.printStackTrace();
    } 
}

/*
 * 根据不同的事件做处理
 * */
protected void process(SelectionKey key) throws IOException{
    // 接收请求
    if (key.isAcceptable()) {
        ServerSocketChannel server = (ServerSocketChannel) key.channel();
        SocketChannel channel = server.accept();
        channel.configureBlocking(false);
        channel.register(selector, SelectionKey.OP_READ);
    }
    // 读信息
    else if (key.isReadable()) {
        SocketChannel channel = (SocketChannel) key.channel(); 
        int count = channel.read(buffer); 
        if (count > 0) { 
            buffer.flip(); 
            CharBuffer charBuffer = decoder.decode(buffer); 
            name = charBuffer.toString(); 
            SelectionKey sKey = channel.register(selector, SelectionKey.OP_WRITE); 
            sKey.attach(name); 
        } else { 
            channel.close(); 
        } 
        buffer.clear(); 
    }
    // 写事件
    else if (key.isWritable()) {
        SocketChannel channel = (SocketChannel) key.channel(); 
        String name = (String) key.attachment(); 
        
        ByteBuffer block = encoder.encode(CharBuffer.wrap("Hello " + name)); 
        if(block != null)
        {
            channel.write(block);
        }
        else
        {
            channel.close();
        }
 
     }
}

JAVA NIO的selector的实现原理 epoll

Java NIO的核心类库多路复用器Selector就是基于epoll的多路复用技术实现的 

相比select、poll系统调用,epoll有如下优点:

1.支持一个进程打开的socket描述符(FD)不受限制,仅受限于操作系统的最大文件句柄数。
select最大的缺陷是单个进程所打开的FD是有一定限制的,它由FD_SETSIZE设置,默认值是1024。可以选择修改这个宏后重新编译内核,但这对带来网络效率的下降。也可以选择多进程的方案(传统的Apache方案)来解决这个问题,但进程的创建成本,以及进程间的数据交换需要进行考虑。
epoll具体支持的FD上线值可以通过cat /proc/sys/fs/file-max查看,这个值和系统的内存关系比较大。

2.I/O效率不会随着FD数目的增加而线性下降。
当拥有一个很大的socket集合时,由于网络延时或者链路空闲,任一时刻只有少部分的socket是“活跃”的,但select/poll每次调用都会线性扫描全部的集合,导致效率线性下降。而epoll只会对活跃的socket进行操作-只有活跃的socket才会主动调用callback函数,所以只需要遍历那些被内核I/O事件异步唤醒而加入Ready队列的FD集合。

3.使用mmap加速内核与用户空间的消息传递
epoll通过内核和用户空间mmap同一块内存来实现的。mmap()系统调用允许存放在块设备上的文件或信息的一部分映射到进程的部分地址空间。

看到这里,或许会产生一个疑问,为什么内核要和用户空间进行消息传递呢?

下面我来进行深入解析:

首先,操作系统必须完成的两个主要目标:

1,与硬件部分交互

2,为运行在计算机系统上的应用程序(即所谓的用户程序)提供执行环境。

而现代操作系统是禁止用户程序直接与底层硬件进行交互的,或者禁止直接访问任意的物理地址。为此,硬件为CPU引入了至少两种不同的执行模式:用户程序的非特权模式和内核的特权模式。Unix把它们分别称为用户态(User Mode)和内核态(Kernel Mode)。所以,每个实际的文件I/O操作必须在内核态下进行。

cpu既可以运行在用户态,也可以运行在内核态。一些CPU可以有两种以上的执行状态,如Intel80x86微处理器有四种不同的执行状态。但是,所有标准的Unix内核都仅仅利用了内核态和用户态。

一个程序执行时,大部分时间都处在用户态,只有需要内核所提供的服务时才切换到内核态。当内核满足了用户程序的请求后,它让程序又回到用户态下。

然后,访问文件的模式有多种:

1,规范模式

规范模式下文件打开后,标志O_SYNC与O_DIRECT清0,而且它的内容是由系统调用read()和write()来存取。系统调用read()将阻塞调用进程,直到数据被拷贝进用户态地址空间。但系统调用write()不同,它在数据被拷贝到页高速缓存(延迟写)后就马上结束。

2,同步模式

同步模式下文件打开后,标志O_SYNC置1。这个标志只影响写操作(读操作总是会阻塞),它将阻塞调用进程,直到数据被有效的写入磁盘。

3,内存映射模式

内存映射模式下文件打开后,应用程序发出系统调用mmap()将文件映射到内存中。因此,文件就称为RAM中的一个字节数组,应用程序就可以直接访问数组元素,而不需用系统调用read()、write()或lseek()。

4,直接I/O模式

直接I/O模式下文件打开后,标志O_DIRECT置1。任何读写操作都将数据在用户态地址空间与磁盘间直接传送而不通过页高速缓存。

5,异步模式

异步模式下,文件的访问可以有两种方法,即通过一组POSIX API或Linux特有的系统调用来实现。所谓的异步模式就是数据的传输请求不阻塞调用进程,而是在后台执行,同时应用程序继续它的正常运行。

说道内存映射,就要谈谈操作系统的内存管理了。

以80X86微处理器为例,我们必须区分以下三种不同的地址:

逻辑地址,包含在机器语言指令中用来指定一个操作数或一条指令的地址。每一个逻辑地址都由一个段(segment)和偏移量(offset)组成。

线性地址,也称虚拟地址,是一个32位无符号整数,可以用来表示高达4GB的地址。

物理地址,用于内存芯片级内存单元寻址。

内存控制单元(MMU)通过一种称为分段单元的硬件电路把一个逻辑地址转换成线性地址;接着,第二个称为分页单元的硬件电路把线性地址转换成一个物理地址。

注:
Linux采用4KB页框大小作为标准的内存分配单元。

内存碎片的产生主要是由于请求内存的大小与分配给它的大小不匹配而造成的。一种典型的解决办法是提供按照几何分布的内存区大小,即内存区大小取决于2的幂而不取决于所存放的数据大小。这样,不管请求内存的大小是多少,都可以保证内存碎片小于50%。

内核使用一种新的资源-线性区,实现了对进程动态内存的推迟分配。当用户态进程请求动态内存时,并没有获得请求的页框,而仅仅获得对一个新的线性地址区间的使用权,而这一线性地址区间就成为进程地址空间的一部分。这一区间叫“线性区”。

进程的地址空间由允许进程使用的全部线性地址组成。内核通过所谓线性区的资源来表示线性地址区间,线性区是有起始线性地址、长度和一些访问权限来描述的。

内存映射,内核给这个进程分配一个新的线性区来映射这个文件。一个新建立的内存映射就是一个不包含任何页的线性区,当进程引用线性区中的一个地址时,缺页异常发生。

与进程地址空间有关的全部信息都包含在一个叫做内存描述符的数据结构中,类型为mm_struct。

Linux通过类型为vm_area_struct的对象实现线性区

进程所拥有的所有线性区是通过一个简单的链表按照内存地址升序链接在一起的,其中mmap字段指向链表中的第一个线性区描述符。当进程中的线性区很多时,Linux2.6使用红黑树来存储内存描述符。

进程的地址空间、它的内存描述符以及线性区链表三者之间的关系,如下图所示:

每个Unix进程都拥有一个特殊的线性区-堆,堆用于满足进程的动态内存请求。

For most operating systems, mapping a file into memory is more expensive than reading or writing a few tens of kilobytes of data via the usual read and write methods. From the standpoint of performance it is generally only worth mapping relatively large files into memory.

JDK1.7升级了NIO类库,升级后的NIO类库被称为NIO2.0。

NIO2.0正式提供了异步文件通道和异步套接字通道的实现。对应于Unix网络编程中的事件驱动I/O – AIO。它不需要通过多路复用器-Selector对注册的通道进行轮询即可实现异步读写,从而简化了NIO的编程模型。

转自https://blog.csdn.net/donsonzhang/article/details/46626273