java - 按值对并发哈希映射进行排序

Question

我是java新手。我想按值对并发哈希映射进行排序。我在这里找到了一种方法 - 按值对并发映射条目进行排序

有没有更简单的方法呢？有人可以用一个例子来解释吗？

谢谢。

Answer 1

另一种解决方案是切换到使用ConcurrentSkipListMapJava 6 中添加的。引用 Javadocs：

此类实现 SkipLists 的并发变体，为 containsKey、get、put 和 remove 操作及其变体提供预期的平均 log(n) 时间成本。插入、删除、更新和访问操作由多个线程安全地并发执行。迭代器是弱一致的，返回的元素反映了在迭代器创建时或之后的某个时刻映射的状态。它们不会抛出 ConcurrentModificationException，并且可以与其他操作同时进行。升序键排序视图及其迭代器比降序视图更快。

SkipLists 是平衡树的概率替换。它们与O树相同，但通常它们的实现要简单得多。如果您的大多数操作都是哈希表查找（O(1)根据定义），那么您会看到对于合适的表大小的性能有所不同，但如果您需要经常进行排序，这可能是一个更好的解决方案。

我只希望 Java 提供这种出色数据结构的非并发版本。

Answer 2

根据您的用例，我将创建另一个表示您的数据结构的类，该类由哈希图和一个列表组成，用于维护值的顺序。

更多细节在这里：
按值排序 Map<Key, Value> (Java)
按值排序 HashMap
http://www.coderanch.com/t/382750/java/java/Sorting-HashMap-values

您还可以扩展 ConcurrentHashMap 以覆盖 entrySet 和 keySet 方法，以按值的顺序返回条目/键。

public class OrderedValueHashMap<K,V extends Comparable<V>> extends ConcurrentHashMap<K, V> {

@Override
public Set<Map.Entry<K, V>> entrySet() {
    Set<Map.Entry<K, V>> orderedValueEntrySet = new TreeSet<Map.Entry<K,V>>(new Comparator<Map.Entry<K,V>>() {

        @Override
        public int compare(java.util.Map.Entry<K, V> o1,
                java.util.Map.Entry<K, V> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });
    orderedValueEntrySet.addAll(super.entrySet());
    return orderedValueEntrySet;
}

@Override
public Set<K> keySet() {
    Set<K> orderedKeySet = new LinkedHashSet<K>();
    for(Map.Entry<K, V> e : entrySet()) {
        orderedKeySet.add(e.getKey());
    }
    return orderedKeySet;
}

}

如果您经常调用方法 keySet/entrySet ，则上述解决方案不是最佳的，因为它会在每次调用时对条目进行排序。您可能希望缓存这些结果以避免在地图的内部状态未更改时重新计算。

上面的示例运行如下：

public static void main(String[] args) {
    ConcurrentHashMap<String,Integer> map = new OrderedValueHashMap<String,Integer>();
    map.put("a", 3);
    map.put("b", 7);
    map.put("c", 1);
    map.put("q", 2);

    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        System.out.println(entry);
    }

    for (String key : map.keySet()) {
        System.out.println(key);
    }

}

输出：

c=1
q=2
a=3
b=7
c
q
a
b

Answer 3

有没有更简单的方法呢？

据我所知，没有。

当然，没有办法对并发哈希映射进行就地排序。CHM 本质上是无序的，因此您必须将条目放入不同的数据结构中以表示条目的有序性。

如果您告诉我们您的要求是什么，也许我们可以提出替代策略。