推上看到的一道题

这跟 Stringbuilder 无关，就是 HashSet 的特性

插个眼，等思路。

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

twitter.com/quydxnguyen/status/1402151079635308544

我理看错了，楼主的理解是对的，最终就是重写 haset 中的 object，即 sb 的 equals 方法。但 sb 的 equals 不好重写

/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
* class), else 0.
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}

hashmap 的这段代码, 如果 key instance Comparable,那么红黑树是按 Comparable 排序的.而 stringbuilder 的 equals 和 hashcode 是不可变的,但 compareTo 是可变的.

The main conclusion from this puzzle: never use mutable objects as Map keys. You may get unpredictable results, even with HashMap.

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

首先我们知道，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 里装可变对象，更深入的思考是当你的程序是建立在假设一些极小概率事情不可能发生的时候，要小心。因为某些时候极小概率事件会集中发生。

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