java - 这种情况该用什么数据结构？-PHP中文网问答

文章专题 AI工具学习下载问答源码最近更新

PHP

会员中心讲师中心微信公众号

java - 这种情况该用什么数据结构？

大家讲道理 2017-04-17 11:39:08

[Java讨论组]

464

目前的数据以 K-V 对的形式存在一个 Map 里，需要用到的操作如下：
1. 对于某个外来数据，检查是否存在在 map 中，这一点 HashMap 可以实现。
2. 根据 key 来获取并修改 map 中的数据，这一点 HashMap 也可以实现。
3. 按照 value 的值来做 TopN，我就是在这里遇到点麻烦，HashMap 实现有些复杂。

我不知道有没有其他数据结构更适合做这个工作，有什么好的建议吗？
P.S. 第3点的操作相对1、2来说没有那么频繁。
P.S.S. 语言是 Java。

大家讲道理

光阴似箭催人老，日月如移越少年。

全部回复(4)

迷茫2017-04-17 11:41:08 4楼

可以用TreeSet

class MyMap<K, V> {
  class Element implements Comparalble<Element> {
    private K key;
    private V value;
    public int compareTo(Element e) {
      var c = value.compareTo(e.value); 
      return c == 0 ? key.compareTo(e.key) : c;
    }
  }

  Map<K, V> map = new HashMap<K, V>();
  SortedSet<Element> set = new TreeSet<Element>();

  void put(K key, V value) {
    map.put(key, v);
    set.add(new Element(key, value);
  }
  void update(K key, V newValue) {
    V oldValue = map.put(key, newValue);
    if (oldValue != null) {
      set.remove(new Element(key, oldValue));
    }
    set.add(new Element(key, newValue));
  }
  Element[] topN(int n) {
    Element[] ret = new Element[n];  
    int i = 0;
    for(Element e : set) {
        ret[i++] = e;
        if (i >= n) {
            break;
        }
    } 
    return ret;
  }
}