8

下面是数据结构的描述：

它的操作类似于带有 、 和 方法的常规地图get，put但remove有一个sort可以调用的方法来对地图进行排序。但是，地图会记住它的排序结构，因此对排序的后续调用会更快（如果结构在调用之间没有太大变化sort）。

例如：

  • 我调用该put方法 1,000,000 次。
  • 我称之为sort方法。
  • 我再调用该put方法 100 次。
  • 我称之为sort方法。

我第二次调用该sort方法应该是一个更快的操作，因为地图的结构没有太大变化。请注意，地图不必在调用sort.

我知道这可能是不可能的，但我希望 O(1) get, put, 和remove操作。TreeMap之类的东西为这些操作提供了有保证的 O(log(n)) 时间成本，但始终保持排序顺序（无sort方法）。

那么这个数据结构的设计是怎样的呢？

编辑 1 - 返回前 K 个条目

虽然我很喜欢听到上面一般案例的答案，但我的用例变得更加具体：我不需要对整个事情进行排序；只是前K个元素。

用于有效返回哈希表（映射、字典）的前 K个条目的数据结构

谢谢！

4

6 回答 6

8

对于“O(1) 获取、放置和删除操作”，您基本上需要 O(1) 查找，这意味着哈希函数（如您所知），但是好的哈希函数的要求通常会破坏易于排序的要求. （如果你有一个哈希表，其中相邻的值映射到同一个桶，它会在很多公共数据上退化为 O(N)，这是你通常希望哈希函数避免的更糟糕的情况。）

我能想到如何让你到达那里的 90%。在已排序的并行索引旁边设置一个哈希表。索引有一个干净的部分（有序）和一个脏的部分（无序）。索引会将键映射到值（或对存储在哈希表中的值的引用 - 在性能或内存使用方面适合您）。当您添加到哈希表时，新条目被推到脏列表的后面。当您从哈希表中删除时，该条目将从索引的干净和脏部分中删除/删除。您可以对索引进行排序，它只对脏条目进行排序，然后将它们合并到索引中已经排序的“干净”部分。显然你可以迭代索引。

据我所知，除了删除操作之外，这在任何地方都为您提供了 O(1)，并且使用标准容器（至少 C++、Java 或 Python 提供）实现起来仍然相当简单。它还为您提供“第二次排序更便宜”的条件，只需对脏索引条目进行排序，然后让您进行 O(N) 合并。所有这一切的代价显然是索引的额外内存和使用它时的额外间接性。

于 2010-01-05T16:25:38.640 回答
4

为什么你需要一个 sort() 函数？
您可能想要和需要的是一棵红黑树。

http://en.wikipedia.org/wiki/Red-black_tree

这些树会通过您提供的比较器自动对您的输入进行排序。它们很复杂，但具有出色的 O(n) 特性。将您的树条目作为键与作为字典的哈希映射结合起来，您就可以获得数据结构。

在 Java 中，它被实现为 TreeMap 作为 SortedMap 的实例。

于 2010-01-26T22:32:50.720 回答
1

我不知道是否有名称，但您可以将每个项目的当前索引存储在哈希中。

也就是说，你有一个HashMap< Object, Pair( Integer, Object ) > 和一个List<Object>对象

当你put，添加到列表的尾部或头部，并使用你的数据和插入索引插入到 hashmap 中。这是O(1).

当你 时get，从 hashmap 中提取并忽略索引。这是O(1).

当你 时remove，你从地图中拉出。获取索引并从列表中删除。这是O(1)

当你sort，只需对列表进行排序。在排序期间更新映射中的索引，或者在排序完成后更新。这不会影响O(nlgn)排序，因为它是一个线性步骤。O(nlgn + n) == O(nlgn)

于 2010-01-05T16:25:10.497 回答
1

有序字典

Python 的最新版本（2.7、3.1）具有“有序字典”，听起来就像您所描述的那样。

如PEP 372中所述，官方 Python“有序字典”实现受到先前 3rd-party 实现的启发。

参考：

于 2010-01-20T01:51:24.037 回答
1

您正在查看的是一个哈希表，其中条目中的指针按排序顺序指向下一个条目。它很像 java 中的 LinkedHashMap，只是链接跟踪的是排序顺序而不是插入顺序。实际上，您可以通过包装 LinkedHashMap 并让排序实现将条目从 LinkedHashMap 传输到 TreeMap 中，然后再返回到 LinkedHashMap 来完全实现这一点。

这是一个对数组列表中的条目进行排序而不是转移到树形图中的实现。我认为 Collection.sort 使用的排序算法可以很好地将新条目合并到已经排序的部分中。

public class SortaSortedMap<K extends Comparable<K>,V> implements Map<K,V> {

    private LinkedHashMap<K,V> innerMap;

    public SortaSortedMap() {
        this.innerMap = new LinkedHashMap<K,V>();
    }

    public SortaSortedMap(Map<K,V> map) {
        this.innerMap = new LinkedHashMap<K,V>(map);
    }

    public Collection<V> values() {
        return innerMap.values();
    }

    public int size() {
        return innerMap.size();
    }

    public V remove(Object key) {
        return innerMap.remove(key);
    }

    public V put(K key, V value) {
        return innerMap.put(key, value);
    }

    public Set<K> keySet() {
        return innerMap.keySet();
    }

    public boolean isEmpty() {
        return innerMap.isEmpty();
    }

    public Set<Entry<K, V>> entrySet() {
        return innerMap.entrySet();
    }

    public boolean containsKey(Object key) {
        return innerMap.containsKey(key);
    }

    public V get(Object key) {
        return innerMap.get(key);
    }

    public boolean containsValue(Object value) {
        return innerMap.containsValue(value);
    }

    public void clear() {
        innerMap.clear();
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        innerMap.putAll(m);
    }

    public void sort() {
        List<Map.Entry<K,V>> entries = new ArrayList<Map.Entry<K,V>>(innerMap.entrySet());
        Collections.sort(entries, new KeyComparator());
        LinkedHashMap<K,V> newMap = new LinkedHashMap<K,V>();
        for (Map.Entry<K,V> e: entries) {
            newMap.put(e.getKey(), e.getValue());
        }
        innerMap = newMap;
    }

    private class KeyComparator implements Comparator<Map.Entry<K,V>> {

        public int compare(Entry<K, V> o1, Entry<K, V> o2) {
            return o1.getKey().compareTo(o2.getKey());
        }

    }

}
于 2010-01-20T04:39:40.843 回答
0

我不知道具有这种确切行为的数据结构分类，至少在 Java 集合（或非线性数据结构类）中没有。也许你可以实现它，它以后将被称为RudigerMap.

于 2010-01-05T16:01:20.373 回答