сортировка одновременных записей карты по значению

ProgramBox

сортировка одновременных записей карты по значению

Post author:admin
Запись опубликована:2 мая, 2023
Post category:Вопросы по программированию

#java #sorting #collections #concurrency

#java #сортировка #Коллекции #параллелизм

Вопрос:

Есть ли какой-либо способ создать потокобезопасную реализацию Map , которая поддерживает сортировку записей по значению? Я знаю, что могу создать потокобезопасный Map такой

 ConcurrentMap<String, Double> rankings = new ConcurrentHashMap<String, Double>();

И затем я могу отсортировать записи по значению, передав их в служебный метод, подобный этому:

 public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
        @Override
        public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
            return (o1.getValue()).compareTo(o2.getValue());
        }
    });

    Map<K, V> result = new LinkedHashMap<K, V>();
    for (Map.Entry<K, V> entry : list) {
        result.put(entry.getKey(), entry.getValue());
    }
    return resu<
}

Но то, что я ищу, — это потокобезопасный, Map который поддерживает записи, отсортированные по значению, так что мне не нужно вызывать метод, подобный приведенному выше, после каждой вставки / удаления, чтобы сохранить записи, отсортированные по значению. Я предполагаю, что я ищу реализацию, которая сочетает в себе поведение ConcurrentHashMap и LinkedHashMap , но пока не нашел ни одной.

ConcurrentSkipListMap почти обеспечивает то, что я хочу, но, похоже, он поддерживает сортировку только по значению ключа.

1. В вашем случае использования вы можете ограничить проблему уникальными значениями, или вы иногда получаете повторяющиеся значения? Если у вас есть повторяющиеся значения, есть ли у вас дополнительные ограничения на сортировку?

2. Также, пожалуйста, уточните — вы хотели отсортировать или упорядочить ? LinkedHashMap выдает упорядоченную, но не отсортированную.

3. гм ….. в чем разница между отсортированными и упорядоченными?

4. @Dilum При необходимости я мог бы исключить возможность дублирования значений карты

5. Предположим, вы добавляете «три», «два», «один» в таком порядке в пустой LinkedHashSet . Если вы выполните итерацию по элементам, они вернутся в том же порядке. Это упорядочено — они возвращаются некоторым предсказуемым, значимым образом. Если вы добавили то же самое в набор деревьев, используя компаратор по умолчанию, они будут возвращены как «один», «три», «два». Еще раз предсказуемо и осмысленно, но также отсортировано , поскольку порядок вставки не имеет значения. Если бы вы добавляли элементы в HashSet, порядок элементов не был бы предсказуемым.

Ответ №1:

Рассмотрите возможность создания составной структуры данных для этого. На высоком уровне выполните следующее.

Сначала реализуйте Map.Entry для сохранения пар ключ-значение. Порядок пары будет сначала по значению, а затем по ключу.

 private static class InternalEntry<K extends Comparable<K>,
                                   V extends Comparable<V>>
        implements Comparable<InternalEntry<K, V>>,
                   Map.Entry<K, V> {
    private final K _key;
    private final V _val;

    InternalEntry(K key, V val) {
        _key = key;
        _val = val;
    }

    public K getKey() {
        return _key;
    }

    public V getValue() {
        return _val;
    }

    public V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public int compareTo(InternalEntry<K, V> o) {
        int first = _val.compareTo(o._val);
        if (first != 0) {
            return first;
        }
        return _key.compareTo(o._key);
    }
}

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

Но эта карта не поддерживает эффективный поиск значения по ключу. Для достижения этой цели представьте другую карту, которая сопоставляет ключи с записями.

Составная структура выглядит следующим образом:

 class OrderedByValue<K extends Comparable<K>, V extends Comparable<V>> {
    private final Map<InternalEntry<K, V>, Boolean> _ordering = 
        new TreeMap<InternalEntry<K, V>, Boolean>();

    private final Map<K, InternalEntry<K, V>> _lookup = 
        new HashMap<K, InternalEntry<K, V>>();

    public V put(K key, V val) {
        InternalEntry<K, V> entry = new InternalEntry<K, V>(key, val);
        InternalEntry<K, V> old = _lookup.put(key, entry);
        if (old == null) {
            _ordering.put(entry, Boolean.TRUE);
            return null;
        }
        _ordering.remove(old);
        _ordering.put(entry, Boolean.TRUE);
        return old.getValue();
    }

    @SuppressWarnings({"unchecked"})
    public Iterable<Map.Entry<K, V>> entrySet() {
        Iterable entries = Collections.unmodifiableSet(_ordering.keySet());
        return (Iterable<Map.Entry<K, V>>) entries;
    }
}

Обратите внимание, что я не предоставил весь необходимый код для реализации полной карты — дайте мне знать, если вам понадобится помощь с другими методами.

Вам также необходимо выполнить некоторый специальный код в реализации сравнения InternalEntry, если необходимо поддерживать нулевые ключи / значения.