java - 随机/随机比较器

Question

是否有任何方法可以模拟 Collections.shuffle 的行为，而不使比较器容易受到排序算法实现的影响，从而保证结果的安全？

我的意思是不违反类似的契约(Contract)等..

Answer 1

在不违反契约的情况下实现真正的“洗牌比较器”是不可能的。 Comparator 合约的一个基本方面是结果可重现，因此特定 Comparator 实例的顺序必须固定。

当然，您可以使用洗牌操作预先初始化该固定排序，并创建一个比较器来准确建立该排序。例如

List<ElementType> ordering=new ArrayList<>(list);
Collections.shuffle(ordering);

list.sort(Comparator.comparingInt(ordering::indexOf));

虽然有点无意义。很明显，此比较器不得用于包含不在排序列表中的元素的集合。

<小时/>

或者，您可以使用首先没有排序的值的稳定属性作为排序标准，例如哈希码。这可以通过稳定但可随机的转换来增强，例如

public static Comparator<String> randomOrder() {
    ThreadLocalRandom r = ThreadLocalRandom.current();
    int x = r.nextInt(), y = r.nextInt(), z = r.nextInt();
    boolean b = r.nextBoolean();
    return Comparator.comparingInt((String s) -> Integer.reverse((s.hashCode()&x)^y))
      .thenComparingInt(s -> s.length()^z)
      .thenComparing(b? Comparator.naturalOrder(): Comparator.reverseOrder());
}

List<String> list=Arrays.asList("hello", "now", "shuffle", "this", "!");
list.sort(randomOrder());
System.out.println(list);
list.sort(randomOrder());
System.out.println(list);

关键点是每个 Comparator 实例代表一个随机选择但固定的顺序，我们创建一个新的 Comparator 实例来请求不同的顺序。因此，没有Comparator违反契约(Contract)。

请注意，这个Comparator看起来有点复杂，因为它必须关心可能的哈希冲突。它将诉诸 length 属性(也是随机的)，然后对于具有相同哈希码和长度的 String ，它将简单地回退到自然顺序或相反顺序，即不太可能被注意到，因为它只影响这些不常见对的关系。

如果您为没有冲突的值创建这样的比较器(例如 Integer 实例)或覆盖定义相等性的值的所有属性(例如，x 和 y，Point)，比较器看起来会简单得多。