Hashset

简介集合，这个概念有点模糊。 广义上来讲，java中的集合是指java.util包下面的容器类，包括和Collection及Map相关的所有类。中义上来讲，我们一般说集合特指java集合中的Collection相关的类，不包含Map相关的类。狭义上来讲，数学上的集合是指不包含重复元素的容器，即集合中不存在两个相同的元素，在java里面对应Set。具体怎么来理解还是要看上下文环境。比如，面试别人让你说下java中的集合，这时候肯定是广义上的。 再比如，下面我们讲的把另一个集合中的元素全部添加到Set中，这时候就是中义上的。 HashSet是Set的一种实现方式，底层主要使用HashMap来确保元素不重复。 源码分析属性 // 内部使用HashMap private transient HashMap<E,Object> map; // 虚拟对象，用来作为value放到map中 private static final Object PRESENT = new Object();构造方法public HashSet() { map = new HashMap<>();}public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c);}public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor);}public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity);}// 非public，主要是给LinkedHashSet使用的HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor);}构造方法都是调用HashMap对应的构造方法。 ...

前言今天，我们来探讨一个实际中不常用但却比较有意思的问题。它能帮助你理解 “HashSet中的键值是唯一的，不可重复的” 这句话的真正含义，也考验你对问题的思考深度。注：实际应用中，我们一般是用 ArrayList 集合来存储相同的字符串的，不会用 HashSet 来存。我们平时都看到或听说 HashSet 是不能用来存放重复的字符串的，是真的存放不了吗？如果面试问你这个问题，你能给出解决方案吗？2. 参考解答先给出参考解答，然后我们再来分析为什么。 解答：虽然我们不能用 HashSet 来存放 String 类型重复的字符串，但我们可以用 HashSet 来存储 StringBuilder 类型重复的字符串呀。public class HashSetTest { public static void main(String[] args){ // 用 HashSet 来存放 String 类型的重复的字符串会发生什么？ HashSet<String> hs1 = new HashSet<>(); String s1 = new String(“aaa”); String s2 = new String(“aaa”); String s3 = new String(“aaa”); hs1.add(s1); hs1.add(s2); hs1.add(s3); System.out.println(“hs1:"+hs1); // 重复的字符串是存不进去的 // 用 HashSet 来存放 StringBuilder 类型的重复的字符串又会发生什么？ HashSet<StringBuilder> hs2 = new HashSet<>(); StringBuilder sb1 = new StringBuilder(“aaa”); StringBuilder sb2 = new StringBuilder(“aaa”); StringBuilder sb3 = new StringBuilder(“aaa”); hs2.add(sb1); hs2.add(sb2); hs2.add(sb3); System.out.println(“hs2:"+hs2); // 咦，结果发现重复的字符串也能存进去了 // 那为什么呢？我们来打印一个各个对象的hashCode看一下 System.out.println(“s1的hashCode:"+s1.hashCode()); System.out.println(“s2的hashCode:"+s2.hashCode()); System.out.println(“s3的hashCode:"+s3.hashCode()); System.out.println(“sb1的hashCode:"+sb1.hashCode()); System.out.println(“sb2的hashCode:"+sb2.hashCode()); System.out.println(“sb3的hashCode:"+sb3.hashCode()); }}输出结果：hs1:[aaa]hs2:[aaa, aaa, aaa]s1的hashCode:96321s2的hashCode:96321s3的hashCode:96321sb1的hashCode:356573597sb2的hashCode:1735600054sb3的hashCode:21685669从打印结果来看，我们是不能用 HashSet 来存放 String 类型的重复字符串的(如hs1)，但我们是可以用HashSet来存放 StringBuilder 类型的重复字符串。3. 为什么？从打印的 hashCode 来看，String 类型，相同字符串的不同 String 对象哈希值是一样的。而对于 StringBuilder 类型，相同字符串的不同对象哈希值是不同的。要知道这个问题的答案，我们首先得了解 Java 虚拟机是如何判断两个对象是否相同的。那 Java 虚拟机是如何判断两个对象是否相同的呢？参考解答：Java 虚拟机会先判断两个对象的 hashCode 是否相同，如果 hashCode 不同，则说明肯定是两个不同的对象了；如果 hashCode 相同再通过 equals() 方法进行进一步比较，如果 equals 方法返回 true，则说明两个对象是相同的，如果equals方法返回 false 说明两个对象不同。具体验证思路如果你感兴趣，请查看: 你有没有想过: Java 虚拟机是如何判断两个对象是否相同的？判断的流程是什么？那为什么相同字符串的不同 String 对象哈希值是一样的，而且还被虚拟机判断为相同的对象了呢？因为 String 类复写了 Object 类的 hashCode() 和 equals() 方法，并实现了自己的 hashCode 值生成算法和 equals 的比较规则，具有相同字符串内容的不同 String 对象在初始化时生成的 hashCode 值是一样的，并且 String 类 equals() 方法比较的是两个字符串的内容，而不是内存地址值，这两个条件同时成立， 这就使 Java 虚拟机把具有相同内容的不同 String 对象判断为相同的对象了，就不会存入 HashSet 集合中。而 StringBuilder 为什么就可以呢？它相同内容的不同对象的哈希值值为什么是不同的？查看 StringBuilder 类的源码你会发现，因为 StringBuilder 并没有复写 Object 类的 hashCode() 方法和 equals() 方法，StringBuilder 用的是父类 Object 类的 hashCode 生成算法，也就是用 native 层的 hashCode 生成算法，很大概率产生的哈希值是不一样的，即使产生了一样的哈希值，Object 类的 equals() 方法比较的是两个对象的内存地址，而不是两个对象的内容，这就使 Java 虚拟机把具有相同内容的 StringBuilder 对象判断为不同的对象，就可以存入 HashSet 集合中了。

ProblemA sequence X_1, X_2, …, X_n is fibonacci-like if:n >= 3X_i + X_{i+1} = X_{i+2} for all i + 2 <= nGiven a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)Example 1:Input: [1,2,3,4,5,6,7,8]Output: 5Explanation:The longest subsequence that is fibonacci-like: [1,2,3,5,8].Example 2:Input: [1,3,7,11,12,14,18]Output: 3Explanation:The longest subsequence that is fibonacci-like:[1,11,12], [3,11,14] or [7,11,18].Note:3 <= A.length <= 10001 <= A[0] < A[1] < … < A[A.length - 1] <= 10^9(The time limit has been reduced by 50% for submissions in Java, C, and C++.)Solutionclass Solution { public int lenLongestFibSubseq(int[] A) { Set<Integer> set = new HashSet<>(); for (int a: A) set.add(a); int max = 2; for (int i = 0; i < A.length-1; i++) { for (int j = i+1; j < A.length; j++) { int a1 = A[i], a2 = A[j]; int curMax = 2; while (set.contains(a1+a2)) { curMax++; int temp = a1; a1 = a2; a2 = temp+a2; } max = Math.max(max, curMax); } } return max == 2 ? 0 : max; }} ...

背景上午刚到公司，准备开始一天的摸鱼之旅时突然收到了一封监控中心的邮件。心中暗道不好，因为监控系统从来不会告诉我应用完美无 bug，其实系统挺猥琐。打开邮件一看，果然告知我有一个应用的线程池队列达到阈值触发了报警。由于这个应用出问题非常影响用户体验；于是立马让运维保留现场 dump 线程和内存同时重启应用，还好重启之后恢复正常。于是开始着手排查问题。分析首先了解下这个应用大概是做什么的。简单来说就是从 MQ 中取出数据然后丢到后面的业务线程池中做具体的业务处理。而报警的队列正好就是这个线程池的队列。跟踪代码发现构建线程池的方式如下：ThreadPoolExecutor executor = new ThreadPoolExecutor(coreSize, maxSize, 0L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue<Runnable>());; put(poolName,executor);采用的是默认的 LinkedBlockingQueue 并没有指定大小（这也是个坑），于是这个队列的默认大小为 Integer.MAX_VALUE。由于应用已经重启，只能从仅存的线程快照和内存快照进行分析。内存分析先利用 MAT 分析了内存，的到了如下报告。其中有两个比较大的对象，一个就是之前线程池存放任务的 LinkedBlockingQueue，还有一个则是 HashSet。当然其中队列占用了大量的内存，所以优先查看，HashSet 一会儿再看。由于队列的大小给的够大，所以结合目前的情况来看应当是线程池里的任务处理较慢，导致队列的任务越堆越多，至少这是目前可以得出的结论。线程分析再来看看线程的分析，这里利用 fastthread.io 这个网站进行线程分析。因为从表现来看线程池里的任务迟迟没有执行完毕，所以主要看看它们在干嘛。正好他们都处于 RUNNABLE 状态，同时堆栈如下：发现正好就是在处理上文提到的 HashSet，看这个堆栈是在查询 key 是否存在。通过查看 312 行的业务代码确实也是如此。这里的线程名字也是个坑，让我找了好久。定位分析了内存和线程的堆栈之后其实已经大概猜出一些问题了。这里其实有一个前提忘记讲到：这个告警是凌晨三点发出的邮件，但并没有电话提醒之类的，所以大家都不知道。到了早上上班时才发现并立即 dump 了上面的证据。所有有一个很重要的事实：这几个业务线程在查询 HashSet 的时候运行了 6 7 个小时都没有返回。通过之前的监控曲线图也可以看出：操作系统在之前一直处于高负载中，直到我们早上看到报警重启之后才降低。同时发现这个应用生产上运行的是 JDK1.7 ，所以我初步认为应该是在查询 key 的时候进入了 HashMap 的环形链表导致 CPU 高负载同时也进入了死循环。为了验证这个问题再次 review 了代码。整理之后的伪代码如下：//线程池private ExecutorService executor;private Set<String> set = new hashSet();private void execute(){ while(true){ //从 MQ 中获取数据 String key = subMQ(); executor.excute(new Worker(key)) ; }}public class Worker extends Thread{ private String key ; public Worker(String key){ this.key = key; } @Override private void run(){ if(!set.contains(key)){ //数据库查询 if(queryDB(key)){ set.add(key); return; } } //达到某种条件时清空 set if(flag){ set = null ; } } }大致的流程如下：源源不断的从 MQ 中获取数据。将数据丢到业务线程池中。判断数据是否已经写入了 Set。没有则查询数据库。之后写入到 Set 中。这里有一个很明显的问题，那就是作为共享资源的 Set 并没有做任何的同步处理。这里会有多个线程并发的操作，由于 HashSet 其实本质上就是 HashMap，所以它肯定是线程不安全的，所以会出现两个问题：Set 中的数据在并发写入时被覆盖导致数据不准确。会在扩容的时候形成环形链表。第一个问题相对于第二个还能接受。通过上文的内存分析我们已经知道这个 set 中的数据已经不少了。同时由于初始化时并没有指定大小，仅仅只是默认值，所以在大量的并发写入时候会导致频繁的扩容，而在 1.7 的条件下又可能会形成环形链表。不巧的是代码中也有查询操作（contains()）,观察上文的堆栈情况：发现是运行在 HashMap 的 465 行，来看看 1.7 中那里具体在做什么：已经很明显了。这里在遍历链表，同时由于形成了环形链表导致这个 e.next 永远不为空，所以这个循环也不会退出了。到这里其实已经找到问题了，但还有一个疑问是为什么线程池里的任务队列会越堆越多。我第一直觉是任务执行太慢导致的。仔细查看了代码发现只有一个地方可能会慢：也就是有一个数据库的查询。把这个 SQL 拿到生产环境执行发现确实不快，查看索引发现都有命中。但我一看表中的数据发现已经快有 7000W 的数据了。同时经过运维得知 MySQL 那台服务器的 IO 压力也比较大。所以这个原因也比较明显了：由于每消费一条数据都要去查询一次数据库，MySQL 本身压力就比较大，加上数据量也很高所以导致这个 IO 响应较慢，导致整个任务处理的就比较慢了。但还有一个原因也不能忽视；由于所有的业务线程在某个时间点都进入了死循环，根本没有执行完任务的机会，而后面的数据还在源源不断的进入，所以这个队列只会越堆越多！这其实是一个老应用了，可能会有人问为什么之前没出现问题。这是因为之前数据量都比较少，即使是并发写入也没有出现并发扩容形成环形链表的情况。这段时间业务量的暴增正好把这个隐藏的雷给揪出来了。所以还是得信墨菲他老人家的话。总结至此整个排查结束，而我们后续的调整措施大概如下：HashSet 不是线程安全的，换为 ConcurrentHashMap同时把 value 写死一样可以达到 set 的效果。根据我们后面的监控，初始化 ConcurrentHashMap 的大小尽量大一些，避免频繁的扩容。MySQL 中很多数据都已经不用了，进行冷热处理。尽量降低单表数据量。同时后期考虑分表。查数据那里调整为查缓存，提高查询效率。线程池的名称一定得取的有意义，不然是自己给自己增加难度。根据监控将线程池的队列大小调整为一个具体值，并且要有拒绝策略。升级到 JDK1.8。再一个是报警邮件酌情考虑为电话通知????。HashMap 的死循环问题在网上层出不穷，没想到还真被我遇到了。现在要满足这个条件还是挺少见的，比如 1.8 以下的 JDK 这一条可能大多数人就碰不到，正好又证实了一次墨菲定律。同时我会将文章更到这里，方便大家阅读和查询。https://crossoverjie.top/JCSprout/你的点赞与分享是对我最大的支持 ...