2

我想知道是否有人知道删除重复值的好方法LinkedHashMap？我有一LinkedHashMap对String和List<String>。我想删除ArrayList's 中的重复项。这是为了改进一些下游处理。

我能想到的唯一一件事是在我迭代时保留处理过的值的日志，HashMap然后通过ArrayList并检查我以前是否遇到过一个值。这种方法似乎会随着列表的增长而降低性能。有没有办法预处理HashMap从ArrayList值中删除重复项？

为了说明......如果我有 String1>List1 (a, b, c) String2>List2 (c, d, e) 我想删除“c”，这样HashMap中的列表就没有重复项。

4

6 回答 6

1

我相信创建第二个 HashMap，可以按值排序（按字母顺序，数字顺序），然​​后对排序列表进行一次扫描，检查当前节点是否等同于下一个节点，如果是，删除下一个，并保持增量不变，因此它将保持在该排序列表的相同索引处。

或者，当您添加值时，您可以检查它是否已经包含该值。

于 2012-01-31T22:16:44.787 回答
1

鉴于您的澄清，您想要这样的东西：

class KeyValue {
    public String key;
    public Object value;

    KeyValue(String key, Object value) {
        this.key = key;
        this.value = value;
    }

    public boolean equals(Object o) {
        // boilerplate omitted, only use the value field for comparison
    }

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

public void deduplicate() {
    Map<String, List<Object>> items = new HashMap<String, List<Object>>();
    Set<KeyValue> kvs = new HashSet<KeyValue>();

    for (Map.Entry<String, List<Object>> entry : items.entrySet()) {
        String key = entry.getKey();
        List<Object> values = entry.getValue();
        for (Object value : values) {
            kvs.add(new KeyValue(key, value));
        }
        values.clear();
    }

    for (KeyValue kv : kvs) {
        items.get(kv.key).add(kv.value);
    }
}

使用集合将删除重复值，并且KeyValue让我们在这样做的同时保留原始哈希键。根据需要添加 getter 和 setter 或泛型。这也将修改原始地图和其中的列表。我也认为这方面的表现应该是 O(n)。

于 2012-01-31T22:33:59.583 回答
0

正如其他人所指出的，您可以在添加时检查该值，但是，如果您必须在事后执行此操作：

static public void removeDups(Map<String, List<String>> in) {
        ArrayList<String> allValues = new ArrayList<String>();
        for (List<String> inValue : in.values())
           allValues.addAll(inValue);
        HashSet<String> uniqueSet = new HashSet<String>(allValues);

        for (String unique : uniqueSet)
            allValues.remove(unique);

        // anything left over was a duplicate
        HashSet<String> nonUniqueSet = new HashSet<String>(allValues);

        for (List<String> inValue : in.values())
           inValue.removeAll(nonUniqueSet);

     }


     public static void main(String[] args) {
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        map.put("1", new ArrayList(Arrays.asList("a", "b", "c", "a")));
        map.put("2", new ArrayList(Arrays.asList("d", "e", "f")));
        map.put("3", new ArrayList(Arrays.asList("a", "e")));

        System.out.println("Before");
        System.out.println(map);

        removeDups(map);
        System.out.println("After");
        System.out.println(map);

     }

产生一个输出

Before
{3=[a, e], 2=[d, e, f], 1=[a, b, c, a]}
After
{3=[], 2=[d, f], 1=[b, c]}
于 2012-01-31T22:57:55.277 回答
0

我假设您需要独特的元素（包含在您的列表中）而不是独特的列表。

如果您不需要 Map 的键与其关联列表中的元素之间的关联，只需将所有元素单独添加到 Set 中。

如果将所有列表添加到集合中，它将包含唯一的列表对象，而不是列表的唯一元素，因此您必须单独添加元素。

（当然，您可以使用它addAll来简化此操作）

于 2012-01-31T22:17:32.567 回答
0

使用番石榴：

Map<Value, Key> uniques = new LinkedHashMap<Value, Key>();
for (Map.Entry<Key, List<Value>> entry : mapWithDups.entrySet()) {
  for (Value v : entry.getValue()) {
    uniques.put(v, entry.getKey());
  }
}
ListMultimap<K, V> uniqueLists = Multimaps.invertFrom(Multimaps.forMap(uniques), 
  ArrayListMultimap.create());
Map<K, List<V>> uniqueListsMap = (Map) uniqueLists.asMap(); // only if necessary

这应该保持值的顺序，并保持它们的唯一性。如果你可以使用 aListMultimap<K, V>作为你的结果——你可能可以——那么就去做吧，否则你可能只是强制uniqueLists.asMap()转换为 a Map<K, List<V>>（滥用泛型，但保证类型安全）。

于 2012-01-31T22:18:52.877 回答
0

所以，澄清一下......你基本上有K，[V1...Vn]并且你想要所有V的唯一值？

public void add( HashMap<String, List> map, HashMap<Objet, String> listObjects, String key, List values)
{
    List uniqueValues= new List();
    for( int i  = 0; i < values.size(); i++ ) 
    {
        if( !listObjects.containsKey( values.get(i) ) )
        {
            listObjects.put( values.get(i), key );
            uniqueValues.add( values.get(i) );
        }
    }
    map.put( key, uniqueValues);
}

本质上，我们有另一个 HashMap 来存储列表值，并在将列表添加到映射时删除非唯一值。这还为您提供了额外的好处，即知道值出现在哪个列表中。

于 2012-01-31T22:32:57.493 回答