从大型 Set 中获取重复项的最佳性能方法是什么？

Question

我有一个很大的Set，其中包含许多单词，例如：

“aaa，cCc，dDD，AAA，bbB，BBB，AaA，CCc，...”

我想对集合中的所有重复单词进行分组，忽略单词的大小写敏感性，然后将它们保存在 Vector> 或其他内容中，因此每个Vector 项将包含一组相似的单词，如下所示：

Vector: aaa, AAA, AaA, ...

矢量：cCc、CCc、...

矢量：bbB、BBB、 ...

我关心性能，因为这个集合包含很多单词。

Answer 1

我将创建一个 HashMap>哈希映射。
接下来，对于集合中的每个“字符串”

if (!hashMap.containsKey(string.toLowerCase()){
     Vector v = new Vector();
     v.add(string);
      hashMap.put(string.toLowerCase(), v);
} else { 
     hashMap.get(string.toLowerCase()).add(string);
}

最后，如果需要，创建一个向量向量，或者使用 hashmap.valueSet()

Answer 2

如果您可以选择 Set 实现，则可以将 TreeSet 与 Comparator 一起使用，比较忽略大小写的字符串。然后您将能够迭代排序列表并轻松对重复项进行分组。

Answer 3

这会迭代输入集一次，我怀疑您能否获得比这更快的速度。将 ArrayList 替换为 LinkedList 可能会以局部性换取更少的复制，这可能会提高性能，但我对此表示怀疑。这是代码：

Set<String> input = new HashSet<String>(Arrays.asList(
    "aaa", "cCc", "dDD", "AAA", "bbB", "BBB", "AaA", "CCc"));

Map<String, List<String>> tmp = new HashMap<String, List<String>>();

for (String s : input) {
    String low = s.toLowerCase();
    List<String> l = tmp.get(low);

    if (l == null) {
        l = new ArrayList<String>();
        tmp.put(low, l);
    }

    l.add(s);
}

final List<List<String>> result = new ArrayList<List<String>>(tmp.values());

Answer 4

如果您真正关心性能，您就不会使用Vector。至于排序问题，一种解决方案是使用 TreeMap 或 TreeSet 对象并创建一个 Comparator 来执行您想要的相等（排序） 。

实例化可以是：

new TreeMap<String,LinkedList<String>>(new Comparator<String>() {

   // comparator here

});

用法：

LinkedList<String> entry = map.get(nextKey);
if (entry == null) {
  entry = new LinkedList<String>()
  map.put(nextKey, entry);
}
entry.add(nextKey);