4kingRAS

去国外申一年的硕士

造的轮子用起来与别人的轮子一点优势都没有就是重复了，优势也有很多种，包括性能，成本，扩展性等
又或者，你是在学习状态，那不可避免要造轮子

有 p5 吗？

想象一个湖，不断有水进来，但是没有水流走，就会卷成漩涡。
这种时候就两条路，湖变大湖，或者变成河，让水流走

大量 1 个，巨量 2 个 ，海量 3 个

@auto 不给不一定过不了，还是看你底气足不足，如果你只有拿 offer 都很困难就必须给。

@4kingRAS 回复怎么删除啊，好蠢

回来填坑了，确实是好题，不过自己想不出来。看了别人的豁然开朗。
**下面是我的理解：**

首先我们知道，HashSet 里面是一个 HashMap ，`set.contains(sb)` 最终执行的是 HashMap 的 contains 方法。通常情况下 contains 方法会先比较 hashCode，再调用 `equals()`。

StringBuilder 在 **内容改变后（如 append ），它的 hashCode 是不会变的**，而 StringBuilder 也没有 override `equals()` 也就是说如果不做什么改动，两次 print 都会打印 true 。

而 StringBuilder 是个 final 类，没法继承重写，怎么办？

V2 的 Java 人我想八股文都背得滚瓜烂熟了吧，都知道 Java 8 以后，hash 冲突会形成链表，超过 8 个会变成红黑树，而红黑树在比较的时候会用 `compareTo` 而不是 equals 。如果用 `compareTo` 可以看到 StringBuilder 的 `compareTo` 实现是有比较内容的。

所以， `sb.append("oops");` 执行后，HashMap 在红黑树中比较就会返回 false 。

整个思路现在就很明朗了，就是制造大量的 hashCode 相同的 StringBuilder，从而在 HashMap 中他们会都放在一个 bucket 里，并形成红黑树，调用`set.contains(sb)` 时，就会调用 `compareTo`

具体的解法很多，以 Tagir 的代码为例，比较好懂：

```java
List<StringBuilder> list = Stream.generate(() -> {
while (true) {
StringBuilder sb = new StringBuilder("a");
int hc = sb.hashCode();
if (((hc ^ (hc >>> 16)) & 0x3F) == 0) {
return sb;
}
}
}).limit(40)
.sorted(Comparator.comparingInt(Object::hashCode))
.toList();
```

首先要想办法制造 hash 冲突的 StringBuilder，比较朴素的办法就是 while 循环里不断的 new

`((hc ^ (hc >>> 16)) & 0x3F)` 这段其实就是 hashMap 源码里的 `hash()`，0x3F 即 63, 是 hashMap 里树化后的最小长度：

`static final int MIN_TREEIFY_CAPACITY = 64;`

```java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```

让 hash 等于 0 是为了让他们落在第一个 bucket 里。

构造这 40 个之后排序一下，之所以是 40 个，跟树化有关，要保证这 40 个 StringBuilder 恰好落在同一个 bucket 里并形成红黑树。

```java
StringBuilder sb = Stream.generate(StringBuilder::new)
.dropWhile(b -> Collections.binarySearch(list, b,
Comparator.comparingInt(Object::hashCode)) < 0)
.findFirst().get();
```

构造 sb 很简单，不断 new 一个 StringBuilder，找到 hash 碰撞的那一个 即可。

完事，当第二次执行 `set.contains(sb)` 时，因为会调用 compareTo，而内容已经变化，所以会返回错误的值。

另一个高手的解法：

大同小异，都是大量生成，然后找碰撞，其他解法思路一样，只是找碰撞的方式不同。不过都很值得学习。

```java
List<StringBuilder> list = IntStream.range(0, 10_000_000)
.mapToObj(i -> new StringBuilder(0))
.filter(s -> ((s.hashCode() ^ s.hashCode() >>> 16) & 0xfff) == 0)
.sorted(Comparator.comparingInt(Object::hashCode))
.collect(Collectors.toList());

StringBuilder sb = list.remove(IntStream.range(1, list.size())
.filter(i -> list.get(i).hashCode() == list.get(i - 1).hashCode())
.findFirst()
.orElseThrow());
```

如五楼所说，永远不要在 hashmap 里装可变对象，更深入的思考是当你的程序是建立在假设一些极小概率事情不可能发生的时候，要小心。因为某些时候极小概率事件会集中发生。

低估这道题了，本来想着能重写 compareTo 或者 equals 这种简单思路。后来看到有个大佬做出来，是制造碰撞，我贴出原链接，研究透了说说，或者有大佬看懂的说说。

twitter.com/quydxnguyen/status/1402151079635308544