Дедупликация значений HashMap

Question

Мне интересно, если кто-нибудь знает хороший способ удалить дубликаты значений в LinkedHashMap? У меня есть LinkedHashMap с парами String и List<String>. Я хотел бы удалить дубликаты через ArrayList. Это должно улучшить некоторую последующую обработку.

Единственное, о чем я могу думать, - это вести журнал обработанных значений, пока я перебираю HashMap, а затем через ArrayList и проверяю, не сталкивался ли я ранее со значением. Похоже, что этот подход будет ухудшать производительность по мере роста списка. Есть ли способ предварительной обработки HashMap для удаления дубликатов из значений ArrayList?

Для иллюстрации ... если у меня есть String1> List1 (a, b, c) String2> List2 (c, d, e) Я хотел бы удалить «c», чтобы не было дубликатов в списках в HashMap.

Answer 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 позволяет нам сохранить исходный ключ хеша при этом.Добавьте геттеры и сеттеры или дженерики по мере необходимости.Это также изменит оригинальную карту и списки в ней на месте.Я также думаю, что производительность для этого должна быть O (n).

Answer 2

Я полагаю, что создание второй HashMap, которая может быть отсортирована по значениям (по алфавиту, по номерам), а затем выполните один проход по отсортированному списку, чтобы проверить, эквивалентен ли текущий узел следующему узлу, если он есть, удалите следующий и оставьте инкремент таким же, чтобы он оставался с тем же индексом в этом отсортированном списке.

Или, когда вы добавляете значения, вы можете проверить, содержит ли оно это значение.

Answer 3

Как уже отмечали другие, вы можете проверить значение при добавлении, но, если вам нужно сделать это после факта:

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]}

Answer 4

Итак, чтобы уточнить ... По сути, у вас есть 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, в которой хранятся значения списка, и мы удаляем неуникальные значения при добавлении списка на карту.Это также дает вам дополнительное преимущество, зная, в каком списке находится значение.

Answer 5

Использование Гуава :

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

, который должен сохранять порядок значений и сохранять их уникальными. Если вы можете использовать ListMultimap<K, V> для своего результата - что вы, вероятно, можете - тогда пойти на это, в противном случае вы, вероятно, просто можете привести uniqueLists.asMap() к Map<K, List<V>> (с некоторым злоупотреблением обобщениями, но с гарантированной безопасностью типов ).

Answer 6

Я предполагаю, что вам нужны уникальные элементы (содержащиеся в ваших списках), а не уникальные списки.

Если вам не нужна связь между ключом карты и элементами в связанном списке, просто добавьте все элементыиндивидуально к набору.

Если вы добавите все списки в набор, он будет содержать уникальные объекты списков, а не уникальные элементы списков, поэтому вам придется добавлять элементы по отдельности.

(вы можетеконечно, используйте addAll, чтобы сделать это проще)