HashMap的初始容量设置

先说结论

知道大小的情况下,new HashMap的时候这么写:

1
HashMap<Integer, String> map = Maps.newHashMapWithExpectedSize(expectedSize);

正文

Java中的HashMap大家都很熟悉,其底层使用了Node数组来存储Map中的数据。但是如果存储的数据太多,空间不够,就需要扩容这个数组来存储新的数据了。

扩容的实现可以看下java.util.HashMap#resize函数,基本上就是将数组中的内容逐个复制到新数组中。

扩容操作的时间复杂度是O(n),空间复杂度是O(n),还需要计算对象的hash。在平常编码中,如果我们提前知道map的大小,就应该指定初始容量,避免发生扩容。

《阿里巴巴开发手册》中也有这么一条建议:

于是,很多开发者(包括刚开始的我),就这么写:

阅读更多

如何以string方式查看heapdump中的byte数组

昨天,线上OOM,dump下来hprof文件,里面有两个大数组:

从表象上来看,和thrift导致的oom是一样的:

但是问题是,这种情况是怎么出现的呢?

找了好几种办法,没有头绪。

最后发现,把这个byte数组转成string就看到了thrift服务端的错误信息。

当时为了快速解决问题,是直接将前60个byte手抄到java代码中,然后转成string输出。

但是,不能一直都这么干,所以就看了下如何方便的将heapdump中的byte[]输出为string。

查了半天,发现OQL没有这样的功能,但是VisualVM倒是可以间接的做这事:

阅读更多

不正确使用Thrift Client导致的OOM问题排查

最近线上有一个多线程的任务,会调用几个Thrift服务。 上线后观察到这个脚本在执行一段时间后,会有好几次Full GC,然后就会报OOM错误。

那就先下载heap dump(推荐压缩后,使用rz下载到本地),使用VisualVM分析。首先切换到Objects页面,看下是否有大对象:

heapdump-Objects

可以看到,有两个byte数组占用了大量内存,也可以看到这个对象是在Java栈上的,接下来就是要找谁在使用这个变量。

右击该对象,点击Select in Threads:

可以看到是名为rebuilder-9的线程,再查看这个线程的调用栈:

再结合readStringBody的代码:

阅读更多

lambda表达式导致arthas无法redefine的问题

作为一个从PHP转Java的人,发现alibaba的arthas很好用。通过arthas的redefine命令,可以像PHP一样,不用重新发布,就可以改变程序行为(前提是不改变类结构,不改变方法签名)。

但是用多了,发现很多时候,我们就改了几行代码,甚至有的时候就添加了一行日志,就无法redefine了。提示

redefine error! java.lang.UnsupportedOperationException: class redefinition failed: attempted to add a method

它提示我们新增加方法,那我们就看看是不是新增加了方法。通过javap来查看定义的方法:

老的类:

新的类:

对比之后发现,新的类,即本地编译的类,其中的lambda对应的方法名都是lambda$getAllCity$0这样的。

阅读更多

LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

每层括号里面的东西需要反转一次。即在在偶数层括号里面的字符是正序的,在奇数层括号里面的字符是逆序的。然后拼成结果。

例子:

“(abcd)”
反转之后就是:
cdba

“(u(love)i)”
love不反转,u,love,i三个反转,答案为:
iloveu

思路

网上有人直接用栈存储,每一个元素代表当前层级括号中的字符串,如果遇到括号关闭,将当前层级字符串反转再append到上一级的字符串中。

但是,括号层级一多,字符串反转的次数就非常多了。而且很多反转都是没有必要的。

其实直接递归就好,或者说分治:

每个括号内部都算作独立的子问题,如果正序,直接逐个append,逆序则反向append;如果遇到括号,则继续分治。

阅读更多

从fastjson漏洞谈防御式编程

最近,fastjson又爆出一个漏洞,在解析特殊字符的时候,直接OOM:

首先分析一下整体流程:

在scanString时,会直接读取两个字符:

而在next方法中,每次读取都会将bp的值加一(即使没有从输入中读取字符):

1
2
3
4
5
6
public final char next() {
int index = ++bp;
return ch = (index >= this.len ? //
EOI //
: text.charAt(index));
}

在处理完x之后,继续解析剩下的字符。由于没有更多字符了,所以读到的总是EOI,然后进入如下分支:

1
2
3
4
5
6
7
if (ch == EOI) {
if (!isEOF()) {
putChar((char) EOI);
continue;
}
throw new JSONException("unclosed string : " + ch);
}

本来到这一步,isEOF应该是true了,但是isEOF是这样的:

阅读更多

LeetCode双周赛-第七场

总是抽不出时间参加LeetCode周日上午的周赛,最近发现有周六晚上10点半的双周赛,就参加了两把。这次是第七场

第一题:

题意

一个只有一行的键盘,随机有26个字母,给定单词,先移动到对应的单词,然后输入第一个字母,再移动,再输入第二个字母,以此类推。问输入这个单词需要移动多长。

题解

题目难度easy,直接模拟就好:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int calculateTime(String keyboard, String word) {
int res = 0;
int index = 0;
int[] map = new int[128];
for (int i = 0; i < keyboard.length(); i++) {
map[keyboard.charAt(i)] = i;
}
for (char ch : word.toCharArray()) {
int newIndex = map[ch];
res += Math.abs(newIndex - index);
index = newIndex;
}
return res;
}
}

第二题:

题意

设计文件系统,有两种操作:create、get。

阅读更多

AsyncHttpClient对Cookie的控制太不灵活了

业务上遇到一个坑,java服务代理了一个接口到upstream,原样转发请求数据和头部。但是代理之后的结果总是莫名其妙的多了一个Cookie,比如是Set-Cookie: ticket=t1

业务上用一个静态的AsyncHttpClient来做代理,也没有做特殊处理,基本上就是如下的代码逻辑:

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
import org.asynchttpclient.*;

import java.io.IOException;
import java.util.concurrent.ExecutionException;

class Main {
private static AsyncHttpClient httpClient;

static {
DefaultAsyncHttpClientConfig.Builder builder = new DefaultAsyncHttpClientConfig.Builder();

httpClient = new DefaultAsyncHttpClient(builder.build());
}

public static void main(String[] args) throws ExecutionException, InterruptedException, IOException {
BoundRequestBuilder builder = httpClient.prepareGet(
"https://httpbin.org/cookies/set/ticket/val1"
);
builder.resetCookies();
builder.execute().get();

BoundRequestBuilder builder2 = httpClient.prepareGet(
"https://httpbin.org/cookies"
);
builder2.resetCookies();
Response res2 = builder2.execute().get();
System.out.println(res2.getResponseBody());
}
}

当时为了防止Cookie问题,特意加上了resetCookies。

首先是查看ticket Cookie的来源,发现upstream在客户端请求带上ticket Cookie的时候,会返回Set-Cookie: ticket=<val> 这个应该就是多余Cookie的来源了。

但是,即使客户端不带Cookie,java服务这边也会返回Set-Cookie字段。这个问题,排查之后发现问题在于resetCookies只能reset本次请求的Cookie,而客户端的Cookie,则不能清除。

即,某次请求,upstream返回了Set-Cookie: ticket=val,那么,以后的代理请求中,都会带上这个Cookie,那么最终用户也会拿到Set-Cookie字段……

从上述代码的运行结果也可以看出:

1
2
3
4
5
{
"cookies": {
"ticket": "val1"
}
}

即,async-http-client没有一个request级别的Cookie控制,只能全局控制Cookie存储。这个问题也有人反馈给了async-http-client

阅读更多

如何恢复Firefox会话中的url

昨天升级到了macOS Catalina 10.15 Beta (19A526h),发现Firefox无法打开了…

不得以,只能看下如何在不打开Firefox的情况下,将会话中打开的url拿出来。

首先,得找到Profile的问题,参考 https://support.mozilla.org/en-US/kb/profiles-where-firefox-stores-user-data 找到位置,将Profile目录下的sessionstore-backups文件夹拷出来。

其中,recovery.jsonlz4文件即为会话的恢复信息,但是这个文件不是标准的lz4压缩文件,得使用特殊的工具来解压,在 https://github.com/avih/dejsonlz4 下载dejsonlz4源码,编译。

通过命令将jsonlz4解压成json:

./dejsonlz4 /path/to/recovery.jsonlz4 /path/to/output/recovery.json

接下来就是探索这个recovery.json的内容了,很简单:

  • jq keys查看这个json文件中的顶级key,比如cat recovery.json | jq keys
  • 查看某一个节点可以通过.来引用,比如jq '.[0].entrys'就是查看第零个元素中的entrys属性

最终,可以通过如下命令输出会话中所有的url:

1
jq -r '.windows[].tabs[].entries[].url' recovery.json 
阅读更多

(据说)华为的一道面试题

刷微博,看到一道面试题:

先说一下思路

默认题意为不能取重复的数字

总体来说,就是从可行解空间[1,1]~[20,20]中,逐步过滤,找到最终答案的过程。说一下过滤步骤:

  1. 首先A不确定两个数字,所以两数之和sum满足:4<=sum<=38
  2. 其次B也不确定,所以两数之积的分解方式可能有多种(本来以为可以用质因子个数>2来判别的,但是后来发现还要考虑两数在1到20之间)
  3. A知道数字了,所以sum的所有分解方式中,只有一个是让B不能确定的,即i+j=sum,切i*j的分解方式不止一种
  4. 这一步比较难:B知道乘积prod,对于prod分解的所有可能,都能得到其和sum,如果sum的所有分解中,只有一个是让B不能确定的;而且prod的分解只有一个是满足此关系的。则当前的prod,以及对应的让B不能确定的prod分解,即为所求解。

1和2很容易理解。3的话,如果sum的诸多分解方式中,都能被B确定,即ij只能唯一分解,那B就不会说不知道数字了。如果sum的诸多分解方式中,有多个不能被B确定,那A在第三步就不能确定数字了,因为A不确定B是在哪一组ij中。

4,B知道乘积prod,假设可以分解为 I_n, J_n 。对于每一组 I_n, J_n:

和为sum=I_n+J_n,且A知道这个sum,这时B推测sum可以分解为i_n+j_n:
  由于3的结论,所以sum对应的i_n*j_n的分解不唯一的情况只有一个
  如果sum对应的i_n*j_n分解不唯一的情况为0个,那么B在第二步就可以猜出
  如果sum对应的i_n*j_n分解不唯一的情况多于1个,那么A在第三步就猜不出来了
在所有的 I_n, J_n 中,满足如上条件的只有一个
如果都满足上述条件的多于一个,那么B在最后一步就无法确定哪一组I_n,J_n是正确答案了

当然,第四步也是在第三步的结果上过滤的

阅读更多