代码之家 › 专栏 › 技术社区 › Eltorrooo

为什么哈希集中的顺序从未改变?[副本]

shuffle hashset collections random java

-2

Eltorrooo · 技术社区 · 7 年前

我在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时,返回的哈希代码可能会导致对元素进行排序。

但这里我使用字符串,输出是:

[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]

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

3 回复 | 直到 7 年前

gargkshitiz 7 年前

HashSet使用计算出的哈希代码以带扣的方式放置这些字符串。

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

话虽如此,实际的hashCode()实现已经从一个JVM版本更改为另一个版本和/或从一个JVM供应商更改为另一个JVM供应商。因此,不要完全依赖它,即使它在您的案例中似乎以可预测的方式运行。

字符串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. */

yelliver 7 年前

哈希集顺序不受保证

这不完全正确,什么顺序?如果 本机订单 (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]

你看到了吗?没有字母顺序!

JB Nizet 7 年前

这是对其他答案和评论的补充,但OP似乎仍然不理解,所以我将尝试给出一个示例。

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

(注意,这是一种简化:HashSet比它更复杂,可以在某些条件下开始使用树)。

将元素添加到哈希集时,将根据元素的哈希代码以确定性方式选择存储该元素的bucket。

因此,假设HashSet有7个桶b1到b7。

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

假设用于选择存储桶的确定性函数返回

b1代表A
b2代表B
b3代表C

因此,您将拥有如下结构

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

迭代时,哈希集不会随机迭代。它将简单地从一个存储桶转到另一个存储桶,并始终打印A、B、C。由于选择存储桶的函数是确定性的,因此无论插入顺序如何,A、B和C始终分别存储在b1、b2和b3中。

这就是为什么你总是得到同样的订单。

现在,假设A、B和C具有相同的哈希代码。或者至少,用于根据哈希代码查找A、B和C的存储桶的函数的结果返回了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:哈希集可以按照它想要的方式对其元素进行排序,因此您不应该依赖哈希集中元素的顺序。只需直接使用您的列表,因为它是无序的,并且提供了排序保证。