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

阅读更多

Java中的SPI机制

SPI 全称为 (Service Provider Interface) ,是Java 1.6之后内置的一种服务提供发现机制。SPI可以通过配置来替换服务(或者说interface)的实现;比如java.sql.Driver接口,可以很轻松的从MySQL切换到MongoDB实现。

问题的核心在于,如何根据interface查找对应的实现。

SPI的实现

Java 1.6中,开发者只需要在META-INF/services下添加文件,即可切换、修改对应interface的实现。文件名为实现的接口,文件内容为N个实现的类名,按行分隔。比如:

$ cat src/main/resources/META-INF/services/com.robberphex.Plugin
com.robberphex.impl.PluginImpl1
com.robberphex.impl.PluginImpl2

使用起来,主要就是ServiceLoader类

ServiceLoader loader = ServiceLoader.load(Plugin.class);
for (Plugin plugin : loader) {
System.out.println(plugin.getClass().getCanonicalName());
}

要注意的是,ServiceLoader#load方法是CallerSensitive的,即load的时候用的是调用者的类加载器。

Java 9

Java 9之后,由于模块化的引入,所以SPI机制也做了扩展:除了原有的通过META-INF/services来注册服务外,还可以通过module中的provides…with语句来注册服务:

阅读更多

Java的类/实例初始化过程

昨天看到群里面有人分享了一道题目,我答错了,于是趁机了解了下Java的类/对象初始化过程:

程序的输出见文章最后

程序A主要考察的是类实例初始化。简单验证了下,类实例初始化过程如下:

  • 父类实例初始化
  • 构造块/变量初始化(按照文本顺序执行)
  • 构造函数

程序B考察的则是类初始化。类初始化的过程如下:

  • 父类初始化
  • static变量初始化/static块(按照文本顺序执行)

但是我们必须做到_面向接口编程,而不是面向实现编程(Program to an ‘interface’, not an ‘implementation’)_。

于是就得看看_Java Language Specification_了。其中类初始化过程如下:

  1. 每个类都有一个初始化锁LC,进程获取LC(如果没有获取到,就一直等待)
  2. 如果C正在被其他线程初始化,释放LC并等待C初始化完成
  3. 如果C正在被本线程初始化,即_递归初始化_,释放LC
  4. 如果C已经被初始化了,释放LC
  5. 如果C处于erroneous状态,释放LC并抛出异常NoClassDefFoundError
  6. 否则,将C标记为正在被本线程初始化,释放LC;然后,初始化那些final且为基础类型的类成员变量
  7. 初始化C的父类SC和各个接口SI_n(按照implements子句中的顺序来) ;如果SC或SIn初始化过程中抛出异常,则获取LC,将C标记为erroneous,并通知所有线程,然后释放LC,然后再抛出同样的异常。
  8. 从classloader处获取assertion是否被打开
  9. 接下来,按照文本顺序执行类变量初始化和静态代码块,或接口的字段初始化,把它们当作是一个个单独的代码块。
  10. 如果执行正常,获取LC,标记C为已初始化,并通知所有线程,然后释放LC
  11. 否则,如果抛出了异常E。若E不是Error,则以E为参数创建新的异常ExceptionInInitializerError作为E。如果因为OutOfMemoryError导致无法创建ExceptionInInitializerError,则将OutOfMemoryError作为E。
  12. 获取LC,将C标记为erroneous,通知所有等待的线程,释放LC,并抛出异常E。
阅读更多

JVM如何获取当前容器的资源限制

最近同事说到Java的 ParallelGCThreads 参数,我翻了下jdk8的代码,发现 ParallelGCThreads 的参数默认值如下:

  • 如果cpu核心数目少于等于8,则GC线程数量和CPU数一致
  • 如果cpu核心数大于8,则前8个核,每个核心对应一个GC线;其他核,每8个核对应5个GC线程

但是被提醒,发现即使在分配4核的容器上,GC线程数也为38。然后就想到应该和容器的资源限制有关——jvm可能无法觉察到当前容器的资源限制。

翻了下代码,发现最新版本的java是能感知容器的资源限制的,就按照jdk版本再翻了下代码:

线上的jdk(jdk8u144)

写一个sleep 1000s的程序,用于查看JVM的线程数量:

1
./jdk1.8.0_144/bin/java -XX:+UseG1GC -XX:+ParallelRefProcEnabled Main 

然后查看GC线程数目:

1
2
$ jstack $pid | grep 'Parallel GC Threads' | wc -l
38

一算就知道物理机器有56个核心(8+(56-8)*5/8=38)

阅读更多

StringBuffer,StringBuilder以及String

今天在网上闲逛,看见 @姚冬 的一个回答

他提到的问题也很有深度,然后思考了下,想评论来着。然而评论区太小,写不下,所以单独写在这儿。

基本上可以当作快问快答来读…

为什么java中的string不以\0结尾?

  • \0结尾在很大程度上要求程序员写规范的代码,如果写出了不规范的代码,那么很容易就内存越界了。
  • 另外,string的内部存储是char[],而为了内存安全,java数组本来就有一个length属性,这时以\0结尾就是一个多余的设计了。
  • String的内部存储也只能是char[]了,如果是其他的方式,比如通过native内部放一个c风格的数组,那么java代码中的char[]和string的转换就要很多内存拷贝操作了。
  • 而C语言设计成\0结尾,是为了减少抽象层,让C语言更加贴近硬件

(在语言设计中,)字符串的长度放哪里,放到起始指针的位置,还是起始指针的前面 ?

  • Java中,String的length也就是数组的length,JLS也只是说明了arraylength字节码,没有规定如何实现
  • 不过Hot Spot的实现是,先元数据,再长度,再具体的内容(比如char[])

如果放前面,那么字符串起始指针和内存块起始不一致怎么解决

Java不存在这个问题,我觉得。元数据和length字段都在实际数组之前呢。Java中,访问任何对象之前都要再多一次跳转,跳过元数据(和length)。

字符串拼接的时候把源串复制到目标串结尾,那么目标串剩余内存不够怎么办,重新分配要多一次赋值,频繁拼接性能有问题怎么办

阅读更多