13

所以我有一个自定义类 Class，它将有一组另一个自定义类学生。所以它看起来像这样：

public class Class {
    private Set<Student> students;

    // other methods
}

现在，我将在学生集中添加和删除许多学生，并且我还将更改学生集中已经存在的学生的许多私人领域。

问题：我应该使用什么数据结构来最好地实现这一点？由于我将更改 set student 中 Student 对象的属性（从而更改哈希码），我应该改用 ArrayList 吗？

4

9 回答 9

18

当涉及到它们的行为时ArrayList，HashSet它们是完全不同的类。

数组列表

  • ArrayList不验证重复项。
  • get()是O(1)

  • contains()是O(n)，但您可以完全控制条目的顺序。

                          get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(1)      O(1)

  • 不是线程安全的，要使其线程安全，您必须使用Collections.synchronizedList(...)

哈希集

  • HashSet确保没有重复。

  • 为您提供一种O(1) contains()方法，但不保留顺序。

                          add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table
  • 不是线程安全的，要使其线程安全，您必须使用Collections.synchronizedSet(...)
于 2016-09-22T06:12:55.707 回答
7

我应该使用什么数据结构来最好地实现这一点？由于我将更改 set student 中 Student 对象的属性（从而更改哈希码），我应该改用 ArrayList 吗？

如果集合元素的哈希码可能会更改，那么您不应该使用HashSet. （如果你这样做了，数据结构将被破坏，并且集合中的元素很可能会丢失。）

但我怀疑您是否应该使用ArrayList其中任何一个，因为如果hashcode()对对象的更改敏感，那么equals(Object)很可能也是如此。这意味着contains(...)类似的方法将无法找到对象。

我认为您应该使用一种Map类型，并使用“学生标识符”作为键。

（您也可以覆盖hashcode，equals因此相等意味着两个对象具有相同的 id。但这equals(Object)对于其他目的毫无用处。）

于 2013-08-01T04:14:10.340 回答
3

如果您的代码中有重复数据，那么您应该使用 ArrayList 否则您可以使用如下所示的 hashset 因此，如果您的代码不需要重复值，则使用 Set 而不是 list 因为 set 将提供更好的性能（O（ n) vs O(n^2) 对于列表），这是正常的，因为避免重复是集合的目的。

数组列表

公共静态无效主要（字符串[]参数）{

ArrayList arr =new ArrayList();
arr.add("Hello");
arr.add("is");
arr.add("Hello");
System.out.println(arr);  //As we are using Arraylist therefore 
                          //the duplicate elements are allowed therefore
                          //"Hello" is not removed in the output

}

哈希集

公共静态无效主要（字符串[]参数）{

HashSet arr =new HashSet();
arr.add("Hello");
arr.add("is");
arr.add("Hello");
System.out.println(arr);  //As we are using Hashset therefore 
                          //the duplicate elements removed therefore
                          //"Hello" is removed in the output

}

于 2018-04-15T19:56:22.827 回答
2

这取决于。当您谈论学生时，必须有像 id 或 rollno 这样的东西是独一无二的。如果是，则覆盖 hashcode 方法并根据他们的 id 实现 hashcode。然后通过更改 student 的任何其他属性对哈希码没有影响。

选择 Set 或 List 完全取决于您的要求。阅读此链接，它将阐明
Set 和 List 之间的区别 Set 和 List 有什么区别？

如果您在 Set 中使用对象，那么您可以尝试覆盖hashcode 和 equals 方法，以便控制唯一性。

于 2013-08-01T04:09:07.943 回答
1

QUESTION: What data structure should I use to best implement this? Since I will be changing the property of the Student objects in set student (thereby changing the hashcodes) should I use an ArrayList instead?

Definitely if you are gonna to change values used by hashCode or equals it is not possible to use HashMap or HashSet.

You are saying that you want to remove and add a lot. The question is if you want to do it sequntially or randomly(based on index). If you add, remove sequentially then definitely the best choice is LinkedList. If you access objects randomly then ArrayList is much more efficient.

于 2013-08-01T18:06:59.687 回答
1

Set的 javadoc说

注意：如果将可变对象用作集合元素，则必须非常小心。如果对象的值以影响等于比较的方式更改，而对象是集合中的一个元素，则不指定集合的​​行为。此禁令的一个特殊情况是不允许集合包含自身作为元素。

因此，如果您要使用 a HashSetif you make hashCode()and equals()based with inmutable fields 那么您将不会遇到此问题。例如，为每个实例使用唯一的 studentID。

于 2013-08-01T04:13:31.630 回答
1

根据您的要求，我认为最好的结构应该是 Map。Set 实际上底层使用内部的 Map 结构，并且您还需要注意 equals 方法的覆盖以更好地查找。而 set 和 arraylist 查找目标对象需要一些查找算法，因此它没有您预期的那么高效（尤其是在非常大的集合情况下）。即使是map也会浪费一些空间，但是如果你的ID是某种原始类型，你可以考虑在Trove库中实现map的原始类型。

于 2013-08-01T04:18:28.803 回答
0

对于诸如 的散列集合HashSet，键应该是immutable。Hashset 在内部使用散列来决定存储对象的桶。并且在检索对象时，它将使用散列来查找对象桶。如果您在存储后更改对象，则可能会更改对象的哈希码，并且 Set 可能无法检索到正确的对象。如果即使在将对象添加到集合之后仍需要更改对象，那么使用散列集合不是一个好的选择。而是选择Arraylist，但请注意，ArrayList您将失去快速检索所需学生的优势，就像使用 Set 一样。

于 2013-08-01T04:01:55.017 回答
0

Set当对象的equals方法的结果会改变时，您不应该使用 a 。如果您通过稳定的唯一 ID 号识别学生，并且equals只检查该 ID，那么使用 aSet就可以了。

请注意，这HashSet将hashCode用于索引和比较，并且hashCode应该准确地包含那些用于确定的字段equals。

于 2013-08-01T04:02:37.390 回答