Java中的HashSets如何工作？

Question

可能重复:
Java hashmap如何工作？

有人可以向我解释一下java中的HashSets是如何工作的以及为什么它们比使用ArrayLists更快？

Answer 1

A HashSet实际上是HashMap值始终相同的位置.

HashMap在许多地方描述了作品的方式(它也被称为"哈希表").简而言之:它生成键(对象)的哈希值并将它们放入表中.然后,每次查找密钥时,都会计算其哈希值,并直接引用表中的桶.这意味着您只需一个操作(最佳情况)即可访问地图.

在HashSet简单地包含了钥匙,因此.contains(..)是O(1).那remove(..)是唯一的操作a HashSet比a 更快ArrayList(即O(n)).迭代是一样的,加法是一样的.

Answer 2

首先,HashSet不像ArrayList是一个集:它不能包含重复,同时ArrayList可以-所以他们是专门为不同的目的.它也不保证订购 - 再次,不像列表.

第二个 - a HashSet建立在哈希表数据结构上,允许O(1)元素的查找时间.

需要注意的是很多时候,一个HashSet是慢那么ArrayList-如果你想重复上例如元素-通常做在ArrayList会更快然后在HashSet[因为散列坏高速缓存性能,除其他原因外]