Sorted hash table (map, dictionary) data structure design

Question

Here's a description of the data structure:

It operates like a regular map with get, put, and remove methods, but has a sort method that can be called to sorts the map. However, the map remembers its sorted structure, so subsequent calls to sort can be much quicker (if the structure doesn't change too much between calls to sort).

For example:

• I call the put method 1,000,000 times.
  
• I call the sort method.
  
• I call the put method 100 more times.
  
• I call the sort method.
  

The second time I call the sort method should be a much quicker operation, as the map's structure hasn't changed much. Note that the map doesn't have to maintain sorted order between calls to sort.

I understand that it might not be possible, but I'm hoping for O(1) get, put, and remove operations. Something like TreeMap provides guaranteed O(log(n)) time cost for these operations, but always maintains a sorted order (no sort method).

So what's the design of this data structure?

Edit 1 - returning the top-K entries

Alhough I'd enjoy hearing the answer to the general case above, my use case has gotten more specific: I don't need the whole thing sorted; just the top K elements.

Data structure for efficiently returning the top-K entries of a hash table (map, dictionary)

Thanks!

Answer 1

For "O(1) get, put, and remove operations" you essentially need O(1) lookup, which implies a hash function (as you know), but the requirements of a good hash function often break the requirement to be easily sorted. (If you had a hash table where adjacent values mapped to the same bucket, it would degenerate to O(N) on lots of common data, which is a worse case you typically want a hash function to avoid.)

I can think of how to get you 90% of the way there. Set up a hashtable alongside a parallel index that is sorted. The index has a clean part (ordered) and a dirty part (unordered). The index would map keys to the values (or references to the values stored in the hashtable - whichever suits you in terms of performance or memory use). When you add to the hashtable, the new entry is pushed onto the back of the dirty list. When you remove from the hashtable, the entry is nulled/removed from the clean and dirty parts of the index. You can sort the index, which sorts the dirty entries only, then merges them into the already sorted 'clean' part of the index. And obviously you can iterate over the index.

As far as I can see, this gives you the O(1) everywhere except on the remove operation and is still fairly simple to implement with standard containers (at least as provided by C++, Java, or Python). It also gives you the "second sort is cheaper" condition by only needing to sort the dirty index entries and then letting you do an O(N) merge. The cost of all this is obviously extra memory for the index and extra indirection when using it.

Answer 2

Why exactly do you need a sort() function ?
What do you perhaps want and need is a Red-Black Tree.

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

These trees are automatically sorting your input by a comparator you give. They are complex, but have excellent O(n) characteristics. Couple your tree entries as key with a hash map as dictionary and you get your datastructure.

In Java it is implemented as TreeMap as instance of SortedMap.

Answer 3

What you're looking at is a hashtable with pointers in the entries to the next entry in sorted order. It's a lot like the LinkedHashMap in java except that the links are tracking a sort order rather than the insertion order. You can actually implement this totally by wrapping a LinkedHashMap and having the implementation of sort transfer the entries from the LinkedHashMap into a TreeMap and then back into a LinkedHashMap.

Here's an implementation that sorts the entries in an array list rather than transferring to a tree map. I think the sort algorithm used by Collection.sort will do a good job of merging the new entries into the already sorted portion.

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());
        }

    }

}