所以我有一个自定义类class,它将有一组其他自定义类Students。所以它看起来像这样:
public class Class {
private Set<Student> students;
// other methods
}
现在,我将添加和删除集合中的许多学生,并且我还将更改集合中已经存在的学生的许多私有字段。
问题:我应该使用什么数据结构来最好地实现这一点?既然我将更改集合Student中Student对象的属性(从而更改哈希代码),我应该使用ArrayList吗?
当涉及到ArrayList
和HashSet
的行为时,它们是完全不同的类。
ArrayList
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(...)
我应该使用什么数据结构来最好地实现这一点?既然我将更改集合Student中Student对象的属性(从而更改哈希代码),我应该使用ArrayList吗?
如果set元素的哈希代码可能会更改,那么您不应该使用HashSet
。(如果你这样做,数据结构将被破坏,集合中的元素很容易丢失。)
但我怀疑您是否也应该使用ArrayList
,因为如果hashcode()
对对象的更改敏感,那么equals(Object)
很可能也是。这意味着contains(...)
和类似的方法将无法找到对象。
我认为您应该使用Map
类型,并使用"学生标识符"作为密钥。
(您也可以覆盖hashcode
和equals
,这样相等意味着两个对象具有相同的id。但这会使equals(Object)
在其他用途上毫无用处。)
如果您的代码中有重复的数据,则应使用ArrayList,否则您可以使用如下所示的哈希集因此,如果您的代码不需要重复的值,那么使用Set而不是list,因为该集合将提供更好的性能(对于列表,O(n)vs O(n^2)),这很正常,因为避免重复是集合的目的。
ArrayList
public static void main(String[]args){
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
}
哈希集
public static void main(String[]args){
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
}
这取决于情况。当你谈论学生时,一定有一些像id或rollno这样的东西是独一无二的。如果是,则覆盖hashcode方法并根据其id实现hashcode。然后,更改student的任何其他属性都不会对哈希代码产生影响。
选择Set或List完全取决于您的要求。阅读此链接,它将澄清Set和list之间的区别
集合和列表之间有什么区别
如果在Set中使用对象,则可以尝试覆盖哈希代码和equals方法,以便控制唯一性。
Set的javadoc说
注意:如果将可变对象用作集合,则必须格外小心元素如果对象的更改方式会影响equals比较,而对象是集合中的一个元素这是一个特例禁止是指不允许集合包含自身作为一个元素。
因此,如果要使用HashSet
,如果使hashCode()
和equals()
基于不可变字段,那么就不会有这个问题。例如,为每个实例使用一个唯一的studentID。
根据您的要求,我认为最好的结构应该是Map。Set实际上在底层使用了内部的Map结构,您还需要注意equals方法重写,以便更好地查找。set和arraylist查找目标对象需要一些查找算法,所以它的效率不如您预期的那么高(尤其是在非常大的收集情况下)。即使映射也会浪费一些空间,但如果您的ID是某种基元类型,则可以考虑Trove库中映射实现的基元类型。
问题:我应该使用什么数据结构来最好地实现这一点?由于我将更改集合中Student对象的属性学生(从而更改哈希代码)我应该使用ArrayList吗相反
当然,如果您要更改hashCode或equals使用的值,则不可能使用HashMap或HashSet。
你是说你想删除和添加很多。问题是,你是想按顺序还是随机(基于索引)来做。如果按顺序添加、删除,那么最好的选择就是LinkedList。如果随机访问对象,那么ArrayList的效率会高得多。
当对象的equals
方法的结果将更改时,不应使用Set
。如果你通过一个稳定的唯一身份证号码来识别学生,而equals
只是检查该身份证,那么使用Set
就可以了。
请注意,HashSet
将使用hashCode
进行索引和比较,而hashCode
应包含用于确定equals
的那些字段。
对于像HashSet
这样的散列集合,密钥应该是immutable
。Hashset在内部使用哈希来决定存储对象的bucket。此外,在检索对象时,它将使用哈希来查找对象桶。如果在存储后更改对象,它可能会更改对象的哈希代码,Set可能无法检索到正确的对象。如果在将对象添加到集合后仍需要更改对象,则使用哈希集合不是一个好选择。选择Arraylist
,但请注意,使用ArrayList
,您将失去快速检索所需学生的优势,就像使用Set一样。