4kingRAS 最近的时间轴更新
4kingRAS

4kingRAS

V2EX 第 123229 号会员,加入于 2015-06-20 17:32:00 +08:00
推上看到的一道题
  •  1   
    Java  •  4kingRAS  •  13 天前  •  最后回复来自 4kingRAS
    7
    4kingRAS 最近回复了
    去国外申一年的硕士
    6 天前
    回复了 heheda11 创建的主题 程序员 如何定义`重复造轮子`
    造的轮子用起来与别人的轮子一点优势都没有就是重复了,优势也有很多种,包括性能,成本,扩展性等
    又或者,你是在学习状态,那不可避免要造轮子
    12 天前
    回复了 taozhi8833998 创建的主题 酷工作 心好累的招聘贴。。。。阿里云
    有 p5 吗?
    12 天前
    回复了 dfkjgklfdjg 创建的主题 职场话题 有一个关于“内卷”的疑惑请教各位
    想象一个湖,不断有水进来,但是没有水流走,就会卷成漩涡。
    这种时候就两条路,湖变大湖,或者变成河,让水流走
    大量 1 个,巨量 2 个 ,海量 3 个
    13 天前
    回复了 auto 创建的主题 程序员 找工作迷惑,怎么谈薪资?
    @auto 不给不一定过不了,还是看你底气足不足,如果你只有拿 offer 都很困难就必须给。
    13 天前
    回复了 4kingRAS 创建的主题 Java 推上看到的一道题
    @4kingRAS 回复怎么删除啊,好蠢
    13 天前
    回复了 4kingRAS 创建的主题 Java 推上看到的一道题
    回来填坑了,确实是好题,不过自己想不出来。看了别人的豁然开朗。
    **下面是我的理解:**

    首先我们知道,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 里装可变对象,更深入的思考是当你的程序是建立在假设一些极小概率事情不可能发生的时候,要小心。因为某些时候极小概率事件会集中发生。
    15 天前
    回复了 4kingRAS 创建的主题 Java 推上看到的一道题
    低估这道题了,本来想着能重写 compareTo 或者 equals 这种简单思路。后来看到有个大佬做出来,是制造碰撞,我贴出原链接,研究透了说说,或者有大佬看懂的说说。

    twitter.com/quydxnguyen/status/1402151079635308544
    成都要是什么都有,什么都好的话早就不是那个房价了
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1294 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 55ms · UTC 17:50 · PVG 01:50 · LAX 10:50 · JFK 13:50
    ♥ Do have faith in what you're doing.