为什么我的 HashSet 中的顺序永远不会改变？

Question

我将字符串（长句）与 HashSet 一起使用，我试图在每次程序运行时将它们打乱顺序以获得随机句子，但这并没有发生

public class testshuffle {

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            run();
        }
    }

    public static void run() {
        ArrayList<String> list = new ArrayList<>();
        Set<String> set = new HashSet<>();
        list.add("Alexandria And Mimy are good people");
        list.add("Bob And Alexandria are better than Mimy");
        list.add("Camelia And Johanness are better than Bob And Alexandria");

        shuffle(list, ThreadLocalRandom.current());
        set.addAll(list);
        System.out.println(set);
    }
}

我知道无法保证 HashSet 顺序。使用 Integer 或 Double 时，返回的 hashCode 可能会导致对元素进行排序。

但这里我使用的是字符串，输出是：

[Alexandria And Mimy are good people, Bob And Alexandria are better than Mimy, Camelia And Johanness are better than Bob And Alexandria]
[Alexandria And Mimy are good people, Bob And Alexandria are better than Mimy, Camelia And Johanness are better than Bob And Alexandria]
[Alexandria And Mimy are good people, Bob And Alexandria are better than Mimy, Camelia And Johanness are better than Bob And Alexandria]
[Alexandria And Mimy are good people, Bob And Alexandria are better than Mimy, Camelia And Johanness are better than Bob And Alexandria]
[Alexandria And Mimy are good people, Bob And Alexandria are better than Mimy, Camelia And Johanness are better than Bob And Alexandria]
[Alexandria And Mimy are good people, Bob And Alexandria are better than Mimy, Camelia And Johanness are better than Bob And Alexandria]
[Alexandria And Mimy are good people, Bob And Alexandria are better than Mimy, Camelia And Johanness are better than Bob And Alexandria]
.
.
.
[Alexandria And Mimy are good people, Bob And Alexandria are better than Mimy, Camelia And Johanness are better than Bob And Alexandria]

请不要将此标记为重复，因为这与我在此处找到的案例不同

Answer 1

HashSet order is not guaranteed

这不完全正确，什么命令？如果native order (1<2, a < b)，则为真。但是当放入HashSet时，它有自己的顺序基于元素的hashcode，这意味着如果所有元素都有唯一的hashcode，你运行 1000次，顺序总是一样的！

如果你把代码改成这样：

    list.add("Alexandria");
    list.add("Bob");
    list.add("Camelia");

结果是：

[Bob, Camelia, Alexandria]
[Bob, Camelia, Alexandria]
[Bob, Camelia, Alexandria]

看到了吗？没有字母顺序！

Answer 2

HashSet 使用计算的 hashCodes 以桶的方式放置这些字符串。

根据 String hashCode() 约定，两个相等的字符串在同一 JVM 中将具有相同的哈希码。这意味着只要字符串不改变，哈希码就不会改变。

话虽如此，实际的 hashCode() 实现已从一个 JVM 版本更改为另一个 and/or 从一个 JVM 供应商到另一个。因此，即使在您的情况下它看起来以可预测的方式运行，也不要完全依赖它。

String hashCode() JavaDoc:

/** * Returns a hash code for this string. The hash code for a * {@code String} object is computed as * <blockquote><pre> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] * </pre></blockquote> * using {@code int} arithmetic, where {@code s[i]} is the * <i>i</i>th character of the string, {@code n} is the length of * the string, and {@code ^} indicates exponentiation. * (The hash value of the empty string is zero.) * * @return a hash code value for this object. */

Answer 3

这是对其他答案和评论的补充，但OP似乎还是不明白，所以我会尝试举个例子。

HashSet 的结构是一个桶数组。一个桶包含集合中的 0 个、1 个或多个元素。如果一个桶中有超过 1 个元素，那么它们将存储在该桶内的链表中。

（注意，这是一种简化：HashSet 比它更复杂，在某些条件下可以开始使用树）。

将元素添加到 HashSet 时，将根据元素的 hashCode 确定性地选择存储该元素的存储桶。

所以，假设 HashSet 有 7 个桶 b1 到 b7。

假设您将 3 个元素 A、B 和 C 添加到 HashSet。

假设用于选择桶的确定性函数returns

A 的 b1
b2 为 B
b3 为 C

因此您将拥有类似

的结构

 [
   b1 -> A,
   b2 -> B,
   b3 -> C,
   b4 -> <empty>
   b5 -> <empty>
   b6 -> <empty>
   b7 -> <empty>
 ]

迭代时，HashSet不会随机迭代。它会简单地从一个桶到另一个桶，并且总是打印 A，然后是 B，然后是 C。由于选择桶的函数是确定性的，所以无论插入什么，A、B 和 C 总是分别存储在 b1、b2 和 b3 中订单是。

这就是为什么您总是得到相同的订单。

现在，假设A、B、C的hashCode相同。或者至少，用于根据 hashCode 为 A、B 和 C returns 查找存储桶的函数的结果与 A、B 和 C 的相同存储桶：b3.

如果你插入 A，然后是 B，然后是 C，你将得到

 [
   b1 -> <empty>,
   b2 -> <empty>,
   b3 -> A -> B -> C
   b4 -> <empty>
   b5 -> <empty>
   b6 -> <empty>
   b7 -> <empty>
 ]

但是如果你插入 C，然后是 B，然后是 A，你会得到

 [
   b1 -> <empty>,
   b2 -> <empty>,
   b3 -> C -> B -> A
   b4 -> <empty>
   b5 -> <empty>
   b6 -> <empty>
   b7 -> <empty>
 ]

并且在迭代HashSet时，顺序会因此而不同，具体取决于插入顺序。

TL;DR：HashSet 可以自由地按照它想要的方式对其元素进行排序，因此您不应依赖 HashSet 中元素的顺序。只需直接使用您的列表，因为它已被打乱，并提供排序保证。

为什么我的 HashSet 中的顺序永远不会改变？

why the order in my HashSet never changes?

java

random

collections

shuffle

hashset