What data structure best mixes strengths of dictionary and list

A question I asked recently left me wondering about the following:

What is the data structure to store a collection (key, value) pairs such that:

• its elements are ordered
• d[key] -> val has complexity O(dict)
• d(index) -> (key, val) has complexity O(list)
• provides reverse lookup d{val} -> (index, key) with complexity O(dict)
• uses the least possible s开发者_Go百科torage

When I type O(type) I mean the same complexity for the operation as data structure type.

For instance, if the ordered collection is:

c = {key_1:val_1, key_2:val_2, key_3:val_3}

I'd like to obtain

 c[key_1] # returns val_1, as in a dictionary
 c(1)     # returns val_2, as in a list
 c{val_3} # returns (2, key_3) as in a sort of "indexed dictionary"

You're asking for O(1) look-ups by key and index as well as O(1) value look-ups. You can do this by maintaining a hash data-structure for the key/values, a second hash structure for the reverse lookup and, a list data structure for the ordered list->key mappings. You'll still have O(n) insertations and deletions, though, and your space complexity will be 3 times what it normally would be.

If you're willing to compromise on speed, you can save on space, there are plenty of set data structures based on trees (TreeSet in Java for example), whose operations have complexity log(n).

It's always a trade off

You've not mentioned insertion cost, which is also an important concern. You could do this with a dictionary lexically ordered, and handle lookups using a binary search (which is log(n)). You'd need to maintain two such structures however, one going key->val and one going val->key, so the insertion cost is going to be double, and the need to insert elements in the middle puts that at O(n) (i.e., the same as for a list).

I had the same problem. So I took the source code of java.util.TreeMap and wrote IndexedTreeMap. It implements my own IndexedNavigableMap:

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

The implementation is based on updating node weights in the red-black tree when it is changed. Weight is the number of child nodes beneath a given node, plus one - self. For example when a tree is rotated to the left:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight simply updates weights up to the root:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

And when we need to find the element by index here is the implementation that uses weights:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Also comes in very handy finding the index of a key:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    if (e.left != null) {
        index += getWeight(e.left);
    }
    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

You can find the result of this work at http://code.google.com/p/indexed-tree-map/