Java - 哪种集合在性能方面最适合这种情况？

我正在写一个需要从文件中读取字符串并将它们存储在某个数据结构中的类。我应该使用以下几点：Java - 哪种集合在性能方面最适合这种情况？

该文件将包含多达数百个字符串（它们需要存储在一个结构中，不能流）。
条目需要按特定顺序存储。
一旦排序，集合将不会被修改（它不一定是不可变的，但我知道它不会被修改）。
我需要多次遍历集合。
如果在集合中有重复条目，则只能存储其中的一个。

以下answer（和其他人）说，一个ArrayList是更好，如果我只需要，因为它读取速度更快排序一次，但如果我用一个ArrayList那么我将不得不确保他们手工是唯一的。

来源

2014-07-17 Adam

您可以将它们始终放置在“Set”中，这将不允许重复，然后将它们移动到ArrayList中以供后续使用。 – forgivenson

可以使用TreeSet。它是一个集合，所以它不会存储重复的条目。它在插入时直接对条目进行排序。基本操作需要log(n)时间。因此，总体时间要求类似于首先插入列表，然后使用排序算法。

来源

2014-07-17 12:42:59 Jack

阅读怎么样？ TreeSet的成本是否更高？ – Adam

对TreeSet的随机元素的单一访问将具有O（log n）复杂性 - 这比使用O（1）从ArrayList访问元素更糟糕。但是，迭代时，整体复杂性应该更好（理想情况下整个迭代过程的O（n））。这假定迭代器实现足够聪明，不会再为每一个next（）调用从树的顶部开始搜索。但是，我没有在TreeSet JavaDocs中找到关于此事的任何声明。 – Jack

如果您可以在插入时对元素进行排序，请考虑TreeSet（如果需要，可以使用自定义比较器）。如果没有，看起来你可能需要两种结构：

用于初始填充和排序的ArrayList。
之后，一个LinkedHashSet为了确保奇点，同时保持秩序。

来源

2014-07-17 12:41:20 Ray

与ArrayList相比，LinkedHashSet在迭代集合方面有什么优势？ – Adam

你可能想使用LinkedHashSet，这是一个：

Hash table and linked list implementation of the Set interface, with predictable iteration order

...

This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet, without incurring the increased cost associated with TreeSet.

来源

2014-07-17 12:41:39

如果您可以随时进行排序：将字符串插入到Set（最好是HashSet，我假设），然后将它们泄漏到ArrayList并进行排序。

来源

2014-07-17 12:44:19 Elazar

鉴于TreeSet在插入时对它们进行排序，是不是比排序ArrayList更快？ – Adam

这取决于你是否想要原始排序ciretiria。如果是这样，你可能是对的。请注意，ArrayList比其他集合具有更好的局部性，因此排序应该更快一些。 – Elazar

我做了TreeSet与ArrayList插入/性能的基准测试。显然，ArrayList表现更好，但是，拥有一百万条独特记录，完整迭代时间为279毫秒并不是那么糟糕。

如果你的情况是微不足道的，我会坚持TreeSet。否则，在将元素插入到ArrayList之前，您将被迫重新轮询并手动检查重复项。

import java.util.ArrayList; 
import java.util.Iterator; 
import java.util.TreeSet; 

public class TestTreeSetVsArrayList { 
    public static int ENTRIES = 10000000; 

    public static void main(String[] args) { 
     TreeSet<String> treeSet = new TreeSet<String>(); 
     ArrayList<String> arrayList = new ArrayList<String>(10000); 
     long l = System.currentTimeMillis(); 
     for (int i = 0; i < TestTreeSetVsArrayList.ENTRIES; i++) { 
      treeSet.add("String"+i); 
     } 
     System.out.println("treeset insertion time: "+ (System.currentTimeMillis()-l)); 
     l = System.currentTimeMillis(); 
     for (int i = 0; i < TestTreeSetVsArrayList.ENTRIES; i++) { 
      treeSet.add("String"+i); 
     } 
     System.out.println("arraylist insertion time: "+ (System.currentTimeMillis()-l)); 

     Iterator<String> iter; 
     iter = treeSet.iterator(); 
     l = System.currentTimeMillis(); 
     while(iter.hasNext()) { 
      iter.next(); 
     } 
     System.out.println("treeset iteration time: "+ (System.currentTimeMillis()-l)); 

     iter = arrayList.iterator(); 
     l = System.currentTimeMillis(); 
     while(iter.hasNext()) { 
      iter.next(); 
     } 
     System.out.println("arraylist iteration time: "+ (System.currentTimeMillis()-l)); 

    } 

}

在我的电脑的结果是：

TreeSet的插入时间：11350

ArrayList中插入时间：3583

TreeSet的迭代次数：279

的ArrayList迭代时间：0

来源

2014-07-17 13:31:05

Java - 哪种集合在性能方面最适合这种情况？

回答

相关问题