HashSet 和 Set 有什么区别? [英] What's the difference between HashSet and Set?

问题描述

看到像

Set<Record> instances = new HashSet<Record>();

我想知道 Hashset 是否是一种特殊的集合.它们之间有什么区别吗?

I am wondering if Hashset is a special kind of set. Any difference between them?

推荐答案

Set 代表一个通用的值集".TreeSet 是元素排序(并因此排序)的集合，HashSet 是元素未排序或排序的集合.

A Set represents a generic "set of values". A TreeSet is a set where the elements are sorted (and thus ordered), a HashSet is a set where the elements are not sorted or ordered.

HashSet 通常比 TreeSet 快很多.

TreeSet 通常实现为红黑树(参见 http://en.wikipedia.org/wiki/Red-black_tree - 我没有验证 sun/oracle 的 TreeSet 的实际实现，而 HashSet 使用 Object.hashCode() 在数组中创建索引.红黑树的访问时间是 O(log(n)) 而 HashSet 的访问时间范围从常数时间到最坏情况(每个项目都有相同的 hashCode)，您可以在其中获得线性搜索时间 O(n).

A TreeSet is typically implemented as a red-black tree (See http://en.wikipedia.org/wiki/Red-black_tree - I've not validated the actual implementation of sun/oracle's TreeSet), whereas a HashSet uses Object.hashCode() to create an index in an array. Access time for a red-black tree is O(log(n)) whereas access time for a HashSet ranges from constant-time to the worst case (every item has the same hashCode) where you can have a linear search time O(n).

这篇关于HashSet 和 Set 有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！