HashSet与ArrayList包含性能

处理大量数据时，我经常发现自己在做以下事情：

HashSet set = new HashSet (); //Adding elements to the set ArrayList list = new ArrayList (set); 

类似于“转储”列表中集的内容。 我通常这样做，因为我添加的元素通常包含我想要删除的重复项，这似乎是一种删除它们的简单方法。

只考虑到这个目标（避免重复）我也可以写：

 ArrayList list = new ArrayList (); // Processing here if (! list.contains(element)) list.add(element); //More processing here 

因此无需将该集“转储”到列表中。 但是，在插入每个元素之前我会做一个小的检查（我假设HashSet也这样做）

这两种可能性中的任何一种显然更有效吗？

Answer 1

该集合将提供更好的性能（ O(n) vs O(n^2)列表），这是正常的，因为集合成员资格（ contains操作）是集合的目的 。

与列表的O(n) O(1)相比， HashSet包含是O(1) ，因此如果您经常需要运行contains则不应使用列表。

Answer 2

ArrayList使用数组来存储数据。 ArrayList.contains将具有O（n）复杂度。 因此，基本上一次又一次地在数组中搜索将具有O(n^2)复杂度。

HashSet使用散列机制将元素存储到各自的存储桶中。 对于长列表值， HashSet的操作会更快。 它将到达O(1)的元素。

Answer 3

如果你不需要列表，我只会使用一个Set，这是自然集合，如果顺序无关紧要，你想忽略重复。

你可以做到这两件事，你需要一个没有重复的列表。

 private Set set = new HashSet<>(); private List list = new ArrayList<>(); public void add(String str) { if (set.add(str)) list.add(str); } 

这样，列表将只包含唯一值，保留原始插入顺序，操作为O（1）。

Answer 4

我做了一个测试所以请检查结果：

对于HashSet，TreeSet，ArrayList和LinkedList中的SAME STRING项，以下是结果

1. 50.000 UUID
   • 搜索项目：e608c7d5-c861-4603-9134-8c636a05a42b（索引25.000）
   • hashSet.contains（item）？ TRUE 0 ms
   • treeSet.contains（item）？ TRUE 0 ms
   • arrayList.contains（item）？ 是2毫秒
   • linkedList.contains（item）？ TRUE 3毫秒
2. 5.000.000 UUID
   • 搜索项目：61fb2592-3186-4256-a084-6c96f9322a86（索引25.000）
   • hashSet.contains（item）？ TRUE 0 ms
   • treeSet.contains（item）？ TRUE 0 ms
   • arrayList.contains（item）？ 是1毫秒
   • linkedList.contains（item）？ 是2毫秒
3. 5.000.000 UUID
   • 搜索项目：db568900-c874-46ba-9b44-0e1916420120（索引号2.500.000）
   • hashSet.contains（item）？ TRUE 0 ms
   • treeSet.contains（item）？ TRUE 0 ms
   • arrayList.contains（item）？ TRUE 33毫秒
   • linkedList.contains（item）？ 是65毫秒

基于以上结果，使用数组列表与集合没有大的区别。 也许您可以尝试修改此代码并将String替换为您的Object ，然后查看差异……

  public static void main(String[] args) { Set hashSet = new HashSet<>(); Set treeSet = new TreeSet<>(); List arrayList = new ArrayList<>(); List linkedList = new LinkedList<>(); List base = new ArrayList<>(); for(int i = 0; i<5000000; i++){ if(i%100000==0) System.out.print("."); base.add(UUID.randomUUID().toString()); } System.out.println("\nBase size : " + base.size()); String item = base.get(25000); System.out.println("SEARCHED ITEM : " + item); hashSet.addAll(base); treeSet.addAll(base); arrayList.addAll(base); linkedList.addAll(base); long ms = System.currentTimeMillis(); System.out.println("hashSet.contains(item) ? " + (hashSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms"); System.out.println("treeSet.contains(item) ? " + (treeSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms"); System.out.println("arrayList.contains(item) ? " + (arrayList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms"); System.out.println("linkedList.contains(item) ? " + (linkedList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms"); } 

Answer 5

您可以向列表本身添加元素。 然后，去重复 –

 HashSet hs = new HashSet<>(); // new hashset hs.addAll(list); // add all list elements to hashset (this is the dedup, since addAll works as a union, thus removing all duplicates) list.clear(); // clear the list list.addAll(hs); // add all hashset elements to the list 

如果你只需要一个带有重复数据删除的集合，你也可以在另一个集合上使用addAll（），这样它就只有唯一的值。