Java集合框架和各实现类性能测试

Java语言集合框架提供一系列集合接口类 (collection interface)和实现类,满足对集合中元素对象的各种集合抽象操作。

1. 集合接口类Collection/List/Set/Map

下图显示了在包java.util.*中主要的核心集合接口类,

上图中的Collection/List/Set/Map等都是泛型接口,各自的定义和作用如下:

  • Collection是集合的顶层接口定义,其它的集合类都继承于Collection(除Map),这个接口定义了对集合元素的增删改查,及其提供interator用于循环整个集合中的元素列表等等。
  • Set是一个不能有重复元素的集合。
  • List是一个有序元素集合,有序是指按照加入/插入数组位置的顺序,集合中可以有重复的元素,可以认为List就是一个数组,访问时可以通过位置index直接访问元素。
  • Map是对键值对(key/value)元素的集合,集合中不能有重复的key。
  • Queue/Deque是一个提供能够进行队列操作的集合,比如FIFO(先进先出)/ LIFO(后进先出)。
  • SortedSet/SortedMap是一个按照元素进行升序排列的集合,集合中的元素排序取决于Comparator的实现。

2. 集合实现类和工具类

集合的实现类很多,JDK中提供的实现类都在java.util.*包中,其中List/Set/Map有如下几个实现类,

  • List
    • ArrayList/LinkedList/Vector
  • Map
    • HashMap/LinkedHashMap/TreeMap/WeakHashMap
    • Hashtable/ConcurrentHashMap
  • Set
    • HashSet/LinkedHashSet/TreeSet

集合的工具类Collections/Arrays提供一些集合的复制、比较、排序和转换操作,

  • Utilities
    • Collections/Arrays

上述各个实现类和接口类的关系见下图,

3. 集合实现类的特点和数据结构

下面以表格形式列出各个实现类的特点和区别,方便进行对比,其中不同的数据结构决定了各个集合实现类的不同性能特点,详细的数据结构描述见后面注解。

集合接口 集合实现类 是否按插入顺序存放 是否按有序存放(1) 是否可以存放重复元素 是否线程安全 数据结构特性描述
List ArrayList Yes No Yes No 基于动态数组的数据结构,注2
LinkedList Yes No Yes No 基于双向链表的数据结构,查询慢,插入快,注3。
Vector Yes No Yes Yes* Deprecated,注4。
Map HashMap No No Yes No 基于哈希表的元素数据离散分布,注5。
LinkedHashMap No No Yes No 基于哈希表的元素数据离散分布,除此之外集合元素数据之间有双向链表指针,注6。
TreeMap No Yes Yes No 基于红黑树的数据结构,元素需要提供Comparator实现,用于有序存放,注7。
WeakHashMap No No Yes No
Hashtable No No Yes Yes 基于哈希表的元素数据分散分布,通过对象锁实现线程安全
ConcurrentHashMap No No Yes Yes 通过lock实现线程安全,在多线程环境中比Hashtable有更好的并发性能
Set HashSet No No No No 底层使用HashMap实现
LinkedHashSet Yes No No No 底层使用LinkedHashMap实现
TreeSet No Yes No No 底层使用TreeMap实现,元素需要提供Comparator实现,用于有序存放

注1:元素是否按有序存放,是指集合中元素根据Comparator进行比较后升序排列。

注2:ArrayList是基于动态数组的数据结构,数据插入时,会导致整个后端数据的往后移动一位,所以插入速度慢,但是根据位置索引可以直接访问元素数据,所以通过位置索引查询数据速度会很快。

注3:LinkedList是基于双向链表的数据结构,插入快,但是查询会比较慢。另外LinkedList支持getFirst/getLast/removeFirst/removeLast/addFirst/addLast操作,可以方便实现FIFO/LIFO队列操作。双向链表的数据结构如下图所示,

注4:Vector由于其在所有的get/set上进行了synchronize,导致难于在并发编程发挥作用,在很多时候可以使用List list = Collections.synchronizedList(new ArrayList())方法取代,目前不建议使用Vector来用于线程安全的编程。

注5:HashMap基于哈希表的元素数据离散分布,是指数据按照一定规则进行离散,比如数值按16取模,各自落入不同的子集合,因此数据元素排列插入后无序,见下图所示,

注6:LinkedHashMap在集合元素数据之间有双向链表指针,数据的删除和插入快,数据元素排列后无序,见下图所示,

注7:TreeMap基于红黑树(近平衡二叉树)的数据结构,这个数据结构最大的特点是各个元素数据达到平衡分布,最远和最近叶子节点离根节点距离相差不超1,使得元素的查找和插入速度达到O(log N)级别。

4. 集合实现类的插入操作

我们可以尝试为各个集合实现类进行插入数据操作,然后查看数据元素在集合中的数据排列,下面主要观察数据排列是否有序,是否按照插入顺序排列。通过观察,可以更加深入地了解各个实现类的数据结构和特性。

List的数据插入

下面的代码新建了三个List实现类实例,然后依次插入10个随机数,最后打印出列表数据。

List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new LinkedList<>();
List<Integer> list3 = new Vector<>();

for (int i = 0; i < 10; i++) {
 //产生一个随机数,并将其放入List中
 int value = (int) (Math.random() * 100);
 App.logMessage("第 " + i + " 次产生的随机数为:" + value);
 list1.add(value);
 list2.add(value);
 list3.add(value);
}

App.logMessage("ArrayList:" + list1);
App.logMessage("LinkedList:" + list2);
App.logMessage("Vector:" + list3);

结果如下,请观察元素插入和排列顺序,

第 0 次产生的随机数为:41
第 1 次产生的随机数为:68
第 2 次产生的随机数为:62
第 3 次产生的随机数为:4
第 4 次产生的随机数为:18
第 5 次产生的随机数为:38
第 6 次产生的随机数为:97
第 7 次产生的随机数为:9
第 8 次产生的随机数为:19
第 9 次产生的随机数为:1
ArrayList:[41, 68, 62, 4, 18, 38, 97, 9, 19, 1]
LinkedList:[41, 68, 62, 4, 18, 38, 97, 9, 19, 1]
Vector:[41, 68, 62, 4, 18, 38, 97, 9, 19, 1]

可以看到,各个List的数据元素排列和插入顺序一致,这也是由于动态数组的数据结构带来的特性。

Set的数据插入

下面的代码新建了三个Set实现类实例,然后依次插入10个随机数,最后打印出列表数据。

Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new LinkedHashSet<>();
Set<Integer> set3 = new TreeSet<>();

for (int i = 0; i < 10; i++) {
 //产生一个随机数,并将其放入Set中
 int value = (int) (Math.random() * 100);
 App.logMessage("第 " + i + " 次产生的随机数为:" + value);
 set1.add(value);
 set2.add(value);
 set3.add(value);
}

App.logMessage("HashSet:" + set1);
App.logMessage("LinkedHashSet:" + set2);
App.logMessage("TreeSet :" + set3);

结果如下,请观察元素插入和排列顺序,

第 0 次产生的随机数为:51
第 1 次产生的随机数为:86
第 2 次产生的随机数为:24
第 3 次产生的随机数为:66
第 4 次产生的随机数为:76
第 5 次产生的随机数为:59
第 6 次产生的随机数为:13
第 7 次产生的随机数为:34
第 8 次产生的随机数为:89
第 9 次产生的随机数为:21
HashSet:[66, 34, 51, 21, 86, 24, 89, 59, 76, 13]
LinkedHashSet:[51, 86, 24, 66, 76, 59, 13, 34, 89, 21]
TreeSet :[13, 21, 24, 34, 51, 59, 66, 76, 86, 89]

可以看到,HashSet/LinkedHashSet无序,TreeSet按大小依次排列。这是由于HashSet/LinkedHashSet/TreeSet底层实现用的是HashMap/LinkedHashMap/TreeMap,因此继承了各自的特点。

Map的数据插入

下面的代码新建了五个Map实现类实例,然后依次插入10个随机数(随机数为key),最后打印出列表数据。

Map map1 = new HashMap();
Map map2 = new TreeMap();
Map map3 = new LinkedHashMap();
Map map4 = new WeakHashMap();
Map map5 = new Hashtable();
Map map6 = new ConcurrentHashMap();

for (int i = 0; i < 10; i++) {
 //产生一个随机数,并将其放入map中
 int value = (int) (Math.random() * 100);
 App.logMessage("第 " + i + " 次产生的随机数为:" + value);
 if (!map1.containsKey(value)){
 map1.put(value, i);
 map2.put(value, i);
 map3.put(value, i);
 map4.put(value, i);
 map5.put(value, i);
 map6.put(value, i);
 }
}

App.logMessage("产生的随机数为key,index为value");
App.logMessage("HashMap:" + map1);
App.logMessage("TreeMap:" + map2);
App.logMessage("LinkedHashMap:" + map3);
App.logMessage("WeakHashMap:" + map4);
App.logMessage("Hashtable:" + map5);
App.logMessage("ConcurrentHashMap:" + map5);

结果如下,请观察元素插入和排列顺序,

第 0 次产生的随机数为:48
第 1 次产生的随机数为:86
第 2 次产生的随机数为:81
第 3 次产生的随机数为:19
第 4 次产生的随机数为:90
第 5 次产生的随机数为:74
第 6 次产生的随机数为:55
第 7 次产生的随机数为:29
第 8 次产生的随机数为:89
第 9 次产生的随机数为:65
产生的随机数为key,index为value
HashMap:{48=0, 81=2, 65=9, 19=3, 86=1, 55=6, 89=8, 90=4, 74=5, 29=7}
TreeMap:{19=3, 29=7, 48=0, 55=6, 65=9, 74=5, 81=2, 86=1, 89=8, 90=4}
LinkedHashMap:{48=0, 86=1, 81=2, 19=3, 90=4, 74=5, 55=6, 29=7, 89=8, 65=9}
WeakHashMap:{90=4, 74=5, 89=8, 29=7, 65=9, 55=6, 81=2, 86=1, 48=0, 19=3}
Hashtable:{90=4, 89=8, 65=9, 19=3, 86=1, 81=2, 55=6, 29=7, 74=5, 48=0}
ConcurrentHashMap:{90=4, 89=8, 65=9, 19=3, 86=1, 81=2, 55=6, 29=7, 74=5, 48=0}

可以看到,TreeMap按key大小升序排列,LinkedHashMap按value大小升序排列,其它无序。

集合实现类的性能比较

为了比较各个集合实现类的性能,对各个集合实现类进行如下三个操作,

  • 插入:在集合中插入0-N个数据元素,N为指定性能测试要达到的数组大小
  • 查询:在集合中一一查询0-N个数据元素,N为指定性能测试的数组大小,换句话说轮询集合中所有元素
  • 删除:在集合中一一删除0-N个数据元素,N为指定性能测试的数组大小,换句话说删除集合中所有元素

测试数组大小分别为1万、5万、10万、15万,线性倍增,然后观察各个集合实现类在不同数组大小下的性能表现。

注:在Map中查询分别添加了通过key/value查询的测试。

测试环境:Java版本为1.8.0_111,主机环境:Win7 SP1 x64, intel i5-6600K 4 cores 3.5GHz CPU, 16G memory。

可以看到,

  • List集合实现类在插入、查询、删除操作上,随着数组变大有明显的性能开销增加,性能开销的增加倍数超过数组大小的增加倍数。
  • Map集合实现类在通过value查询性能开销很大,在实际编程中,尽量避免此类操作
  • 表中有些操作时间开销都在10毫秒内,随着数组倍增,性能表现不错,这些操作可以在编程中多加利用。

测试程序代码

演示代码仓库地址:https://gitee.com/pphh/blog,可以通过如下git clone命令获取仓库代码,

git clone git@gitee.com:pphh/blog.git

上述测试程序代码样例在文件路径171117_java_collection\demo中。

参考资料

Json Web Token的介绍和最佳实践

1. 什么是JSON Web Token

JSON Web Token是一个开放的、行业规范(RFC7519)的方法,用于通信双方进行可靠的数据传输。它规定了一种紧凑的数据格式,将要传输的数据以JSON对象方式的组织,然后进行编码和签名,转化成为Token。

JSON Web Token包含三部分信息数据,

Header.Payload.Signature

其中,

  • Header:数据头部,声明Token类型和加密算法(比如HMAC SHA256或者RSA)
  • Payload:数据的信息体,包含了要传输的信息体
  • Signature:数据的数字签名,用于对数据进行校验来源可靠性和不被篡改

在三部分中,header/payload都是公开信息,JSON对象数据格式,使用Base64方式进行编码,这意味着header/payload可以被任何人进行解码和阅读,所以不要在header/payload放入敏感信息。

一个Token样例为,
eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJzdWIiOiIxMjM0NTY3ODkwIiwibmFtZSI6IkpvaG4gRG9lIiwiYWRtaW4iOnRydWV9.TJVA95OrM7E2cBab30RMHrHDcEfxjoYZgeFONFh7HgQ

其中,

Header Base64编解码 {"alg":"HS256","typ":"JWT"}
Payload Base64编解码 {"sub":"1234567890","name":"John Doe","admin":true}
Signature HS256签名算法 HS256(eyJhb……RydWV9, secret)

注:签名算法中的eyJhb……RydWV9为Base64编码后的Header.Payload

2. 应用场景

JWT一般用在如下两个场景,

  • 认证:这是最常用JWT应用场景,用于用户登录后,后端服务器颁发一个带有时效性的JWT token给前端应用,然后前端应用在后续的请求中使用该Token进行访问后端资源。
  • 信息交换:由于JWT对数据进行了签名,信息不能被篡改,可以可靠地在通信双方进行数据信息交换。

下图简单描绘了JWT在认证场景的使用流程,

使用方法

JWT的使用方法包括:签发、解码、校验,

  • 签发:用于对信息进行签名,然后颁发给使用方,供后续进行认证和信息交换
  • 解码:对JWT的信息体解码,获取信息,一般用在不进行校验的场合,比如在浏览器端
  • 校验:对JWT的校验,确认信息的来源可靠性和不被篡改、时效不过期

目前已经有如下语言的支持,

  • Java
  • Node.js
  • JavaScript
  • Microsoft .NET、.NET RT(Windows 8.1 and Windows Phone 8.1)
  • Python
  • Perl
  • Ruby
  • Go
  • Lua
  • Scala
  • Object-C
  • Swift
  • PHP

等等。

下面主要介绍JavaScript/Node.Js/Java三种语言对Jwt的签发、校验、解码的代码实现,这三种语言分别代表着web客户端/web服务器端/后端服务。

1) JavaScript

下面使用jwt-decode类库在web客户端(浏览器端)对token进行解码操作。

点击这里下载jwt-token.js脚本。

在HTML页面中引入上面的JavaScript脚本,下面为简单的解码演示,

<script type="text/javascript" src="jwt-token.js"></script>
<script>

    let jwtToken = "eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJzdWIiOiIxMjM0NTY3ODkwIiwibmFtZSI6IkpvaG4gRG9lIiwiYWRtaW4iOnRydWV9.TJVA95OrM7E2cBab30RMHrHDcEfxjoYZgeFONFh7HgQ";
    let payload = jwtToken.split('.')[1];
    let payloadInfo = JSON.parse(jwt.base64urldecode(payload));

    for (let key in payloadInfo) {
        console.log(key + ": " + payloadInfo[key]);
    }

</script>
2) Node.js

下面使用Node Auth0类库在nodejs的web服务器端进行token的签发和校验
安装命令,从npm中安装jsonwebtoken
npm install jsonwebtoken

签发

let jwt = require('jsonwebtoken');
let token = jwt.sign({name: 'John'}, 'secret', { algorithm: 'HS256', expiresIn: '1d', issuer: 'pphh'});

校验

let jwt = require('jsonwebtoken');
let info = jwt.verify(token, 'secret');
console.log(info.name) // John

解码

let info = jwt.decode(token, {complete: true});
console.log(info.header);
console.log(info.payload);
3) Java

下面使用Java Auth0类库来进行token的签发和校验。

在Maven项目中添加依赖项,

<dependency>
<groupId>com.auth0</groupId>
<artifactId>java-jwt</artifactId>
<version>3.2.0</version>
</dependency>

签发

try {
    Algorithm algorithm = Algorithm.HMAC256("secret");
    String token = JWT.create()
                      .withIssuer("auth0")
                      .sign(algorithm);
} catch (UnsupportedEncodingException exception){
    //UTF-8 encoding not supported
} catch (JWTCreationException exception){
    //Invalid Signing configuration / Couldn't convert Claims.
}

校验

String token = "eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXUyJ9.eyJpc3MiOiJhdXRoMCJ9.AbIJTDMFc7yUa5MhvcP03nJPyCPzZtQcGEp-zWfOkEE";
try {
    Algorithm algorithm = Algorithm.HMAC256("secret");
    JWTVerifier verifier = JWT.require(algorithm)
                              .withIssuer("auth0")
                              .build(); //Reusable verifier instance
    DecodedJWT jwt = verifier.verify(token);
} catch (UnsupportedEncodingException exception){
    //UTF-8 encoding not supported
} catch (JWTVerificationException exception){
    //Invalid signature/claims
}

解码

String token = "eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXUyJ9.eyJpc3MiOiJhdXRoMCJ9.AbIJTDMFc7yUa5MhvcP03nJPyCPzZtQcGEp-zWfOkEE";
try {
    DecodedJWT jwt = JWT.decode(token);
} catch (JWTDecodeException exception){
    //Invalid token
}

更多语言和JWT类库使用,请参考官方网站和样例。

最佳实践

  1. 在JWT信息体Payload中不要包括敏感信息,若一定要,可以尝试使用JSON Web Encryption 。
  2. 一定要添加Token过期时间expiration time (exp claim) ,用于时效性检查。
  3. 不建议以无签名算法的方式(签名算法为none)来颁发JWT token,这个有安全风险,会导致攻击者绕过某些JWT类库的校验,具体可以查看该资料
  4. 建议使用HTTPS来传输JWT token信息,在最大程度保证信息在传输过程中的安全性,防止被中间人截取。
  5. 确保签名密钥只能让颁发者和使用者知道,尽可能使用非对称加密算法来颁发Token(比如RSA算法)。
  6. 如果担心重放攻击(replay attacks),可以尝试设置jti声明(JWT ID Claim),该声明将使得每个JWT token拥有唯一的ID,使其可以只使用一次,可以用来防止重放攻击。
  7. 在浏览器端,token可以存放到sessionStorage/localStorage,但注意XSS(跨站点脚本)攻击;还有一种方法是token放到了Cookie中,建议为其加上HttpOnly和Secure标记,HttpOnly保证JavaScript无法获取该Cookie,而Secure标记将保证该Cookie信息只能通过Https传输,但注意Cookie的方式可能会引起CSRF(跨站请求伪造)攻击。

演示项目

admin demo项目代码中有一一使用上述的JWT token颁发、校验、解码方法,

  1. 在前端项目admin-front中,通过jwt-decode解析JWT token来获取登录用户账号。
  2. 在前端项目admin-front中,在配置文件webpack.config.js中有提供/test/auth接口,通过jsonwebtoken颁发JWT token。
  3. 在后端项目admin-server中,在UserService中,通过com.auth0.jwt.JWT来颁发JWT token。
  4. 在后端项目admin-server中,在JwtFilter中,通过com.auth0.jwt.JWT来校验用户登录token。

具体可以获取项目代码查看。

admin demo代码仓库地址:https://gitee.com/pphh/simple-admin,可以通过如下git clone命令获取仓库代码,

git clone git@gitee.com:pphh/simple-admin.git

参考资料

探索性测试和机器学习

最近在研究如何做项目的测试,在我们平常的项目中,有功能性测试,回归测试,集成测试,为了提供测试效率和控制质量,会尽可能的做自动化测试,但最近的研究和这些测试有点不一样,我们准备尝试下做一种探索性测试,最好能够让机器一边学习一边帮我们测试,我们所需要的就是做一些假设性输入即可。

智能探索性测试

探索性测试(explortary test),一般没有计划好的测试步骤,没有预设的测试目标,只有对测试结果的普遍期望,这个和随机性测试(ad-hoc)相同,不一样的地方是,探索性测试是在对测试的产品并不十分了解,是根据测试者的经验和一些测试常识来做一些测试,一边学习,一边不断的测试新功能。

人的学习能力是很强的,所以很多时候探索性测试被认为是只有人可以胜任这个工作,但是大家可能忽略的一点是,测试需要很强的重复执行能力,在这个方面,人是远远无法和机器相比的。假如我们能够让机器拥有人类的学习能力,那么是不是可以让机器帮我们做探索性测试。

举个例子,在web测试中,如果我们能够让机器能够识别一个链接,点击后期望是打开一个页面,是不是可以让机器帮我们测试网页上的所有链接?在移动应用中,如果我们能够让机器识别一个按钮,点击之后期望应用没有运行异常,可能还会弹出一个对话框,如果点击对话框的“关闭”按钮,那么对话框应该可以关闭;甚至可以这样,机器可以点击“确定”按钮,机器记录下所发生的一些事件,那么当一次点击这个按钮时,机器是否就可以判断点击同样按钮的事件?

我们想这是完全可以做到的,现在的机器学习理论已经可以让我们好好对探索性测试做些工作,我们可以给机器输入一些预设条件,然后机器就可以自己学习摸索,然后自动帮我们做测试工作,出现异常能够报告出来,任何测试如果能够被自动化,就应该自动化,探索性测试也不例外,我们现在欠缺的可能就是一个智能的机器了。

机器学习算法

要让机器能够变得智能化,我们需要让机器能够自我学习和判断,这样才能自主开展探索性测试工作。让我们先从几个简单的机器学习算法说起。

邻近算法

这是一个简单的算法,其原理是,选取一个事物的特征项,每个特征项都可以量化,有量化的值,比如一个长方形的有两个特征项:长和宽,我们以(x,y)来表示,那么任何一个长方形都有这两个值,邻近算法就是比较两个长方形的特征项值的坐标距离,如果离的近,说明这两个长方形就是同一事物。

概率算法

这个算法和邻近算法不一样的是,其根据每个特征项的概率综合起来判断事物的归类,这里面有不同的概率组合算法,我们不在文章里展开。

举个例子来说,小米相机上自带有识别人脸,其会判断年龄和性别,在这个过程中,就有一个机器判断过程,那么机器如何判断年龄和性别么?一个人的脸上有很多特征项,有头发,眼睛,鼻梁,眉毛,嘴巴,皮肤,以判断性别来说,头发是一个很重要的特征项,头发长有90%的可能是女性,皮肤白有60%可能是女性,那么两者加起来判断可能有96%的可能为女性,这个是条件概率得到的判断,如果有更多的特征概率,则判断会更准确。

一个简单的实现

在我们的项目中,我们以一个web网页为基础,希望获取到网页上所有图片类型并加以归类,开发语言用的是Python。

代码地址:https://git.oschina.net/pphh/machinelearning.git

算法步骤,

1. 读取训练样本数据,建立数据模型,获取k值,k值是判断目标数据类型的个数。

2. 输入目标数据,计算和样本数据特征值的坐标距离。

3. 获取k个最近距离的样本数据,并根据样本数据的类型来决定目标数据的类型。假如k为3,如果有两个以上的样本数据表明同一类型A,则目标数据就可以判断类型A。