0

我尝试使用HashSet从ArrayList<StringBuilder>.

例如这里是一个ArrayList，每一行都是一个StringBuilder对象。

"u12e5 u13a1 u1423"
"u145d"
"u12e5 u13a1 u1423"
"u3ab4 u1489"

我想得到以下信息：

"u12e5 u13a1 u1423"
"u145d"
"u3ab4 u1489"

我目前的实现是：

static void removeDuplication(ArrayList<StringBuilder> directCallList) {
    HashSet<StringBuilder> set = new HashSet<StringBuilder>();
    for(int i=0; i<directCallList.size()-1; i++) {
        if(set.contains(directCallList.get(i)) == false)
            set.add(directCallList.get(i));
    }   
    StringBuilder lastString = directCallList.get(directCallList.size()-1);
    directCallList.clear();
    directCallList.addAll(set);
    directCallList.add(lastString);
}

ArrayList但随着规模的增长，性能变得越来越差。这个实现有什么问题吗？或者在性能方面你有更好的吗？

4

5 回答 5

9

StringBuilder 没有实现 equals() 或 hashcode()。两个 StringBuilder 仅当它们是完全相同的对象时才相等，因此将它们添加到 HashSet 不会排除两个具有相同内容的不同 StringBuilder 对象。

您应该将 StringBuilders 转换为 String 对象。

此外，您应该在构造函数中使用“初始容量”初始化 HashSet。如果您正在处理大量对象，这将有助于提高速度。

最后，在添加对象之前不必在哈希集上调用 contains()。只需将您的字符串添加到集合中，集合就会拒绝重复项（并将返回 false）。

于 2012-10-15T17:05:15.197 回答
2

让我们分析您的方法以找到可以改进的地方：

static void removeDuplication(ArrayList<StringBuilder> directCallList) {
    HashSet<StringBuilder> set = new HashSet<StringBuilder>();
    for(int i=0; i<directCallList.size()-1; i++) {
        if(set.contains(directCallList.get(i)) == false)
            set.add(directCallList.get(i));
    }

这个 for 循环对ArrayList. 对于手头的任务，这似乎是不可避免的。但是，由于HashSet每个项目只能包含一项，因此该if语句是多余的。HashSet.add()再次进行完全相同的检查。

    StringBuilder lastString = directCallList.get(directCallList.size()-1);

我不明白需要lastString从您的列表中获取然后添加它。如果您的循环正常工作，它应该已经被添加到HashSet.

    directCallList.clear();

根据列表的实现，这O(n)可能需要很长时间，因为它可能需要访问列表中的每个元素。

    directCallList.addAll(set);

同样，这需要O(n)时间。如果没有重复项，则set包含原始项目。

    directCallList.add(lastString);

这条线似乎是一个逻辑错误。您将添加一个String已经存在set并添加到directCallList. }

所以总的来说，这个算法需要O(n)时间，但有一个常数因子3。如果你能减少这个因素，你就可以提高性能。一种方法是简单地创建一个新的ArrayList，而不是清除现有的。

此外，如果您使用正确的构造函数并返回没有重复项removeDuplication()，则可以在一行中编写此函数：ArrayList

static List<StringBuilder> removeDuplication(List<StringBuilder> inList) {
    return new ArrayList<StringBuilder>(new HashSet<StringBuilder>(inList));
}

当然，这仍然没有解决StringBuilder其他人指出的问题。

于 2012-10-15T17:09:00.140 回答
1

所以你有一些其他的选择，但我喜欢我的解决方案简短、简单、中肯。我已将您的方法更改为不再操纵参数，而是返回一个新的List. 我用 aSet<String>查看每个的内容StringBuilder是否已经包含并返回唯一String的 s。我还使用了 for each 循环而不是按索引访问。

static List<StringBuilder> removeDuplication(List<StringBuilder> directCallList) {
    HashSet<String> set = new HashSet<String>();
    List<StringBuilder> returnList = new ArrayList<StringBuilder>();
    for(StringBuilder builder : directCallList) {
        if(set.add(builder.toString())
            returnList.add(builder);
    }   
    return returnList;
}
于 2012-10-15T17:20:41.453 回答
0

正如 Sam 所说，StringBuider不会覆盖hashCode，equals因此Set不会正常工作。

我认为答案是将 Builder 包装在一个只执行一次 toString 的对象中：

class Wrapper{
   final String string;
   final StringBuilder builder;

   Wrapper(StringBuilder builder){
      this.builder = builder;
      this.string = builder.toString();
   }

   public int hashCode(){return string.hashCode();}

   public boolean equals(Object o){return string.equals(o);}
}     


 public Set removeDups(List<StringBuilder> list){
    Set<Wrapper> set = ...;
    for (StringBuilder builder : list)
       set.add(new Wrapper(builder));

    return set;
 }

removeDups可以更新该方法以从集合中提取构建器并返回List<StringBuilder>

于 2012-10-15T17:05:51.813 回答
0

如前所述，StringBuilders 不会覆盖Object#equals并且不是Comparable.

尽管使用 StringBuilders 连接您的字符串是可行的方法，但我建议您完成连接后，您应该在列表中存储基础字符串( stringBuilder.toString()) 而不是 StringBuilders。

然后删除重复项变成一行：

Set<String> set = new HashSet<String>(list);

或者更好的是，如果您不需要知道有重复，则直接将字符串存储在集合中。

于 2012-10-15T17:10:43.510 回答