unique key-value-pair collection

Question

Is there any structure that allows BOTH of these operations:

• collection.TryGetValue(TKey, out TValue)
• collection.TryGetKey(TValue, out TKey)

In a better time than O(n)?

My problem:

I basically need to be able to retrieve key's value or value's key really fast, without duplicating the memory (so two dictionaries are out of question).

Very important note: all the keys are unique and all the values are unique. Having this information I feel it should be possible to accomplish this task in a better time than just O(1) for .TryGetValue and O(n) for .TryGetKey.

EDIT:

In my case, I have a mapping between strings and ints. There are ~650,000 key-value pairs of texts and their IDs. So I basically want to get the string with a specific ID but also the ID of a certain string.

Answer 1

To get better than O(n) you will need to use a 2nd dictionary. However as you mentioned you are using structs and are concerned about memory usage with a 2nd dictionary having a duplicate copy of the struct.

One way around this is box the struct value inside a object then share the boxed object in the two dictionaries. If you use inherit from DictionaryBase this is actually quite easy to implement.

public sealed class TwoWayDictionary<TKey, TValue> : DictionaryBase
{
    Hashtable reverseLookup = new Hashtable();

    public void Add(TKey key, TValue value)
    {
        this.Dictionary.Add(key, value);
    }

    public void Remove(TKey key)
    {
        this.Dictionary.Remove(key);
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        object lookup = Dictionary[key];
        if (lookup == null)
        {
            value = default(TValue);
            return false;
        }
        else
        {
            value = (TValue)lookup;
            return true;
        }
    }

    public bool TryGetKey(TValue value, out TKey key)
    {
        object lookup = reverseLookup[value];
        if (lookup == null)
        {
            key = default(TKey);
            return false;
        }
        else
        {
            key = (TKey)lookup;
            return true;
        }
    }

    //If OnInsertComplete or OnSetComplete raises a exception DictionaryBase will 
    // roll back the operation it completed.
    protected override void OnInsertComplete(object key, object value)
    {
        reverseLookup.Add(value, key);
    }

    protected override void OnSetComplete(object key, object oldValue, object newValue)
    {
        if(reverseLookup.Contains(newValue))
            throw new InvalidOperationException("Duplicate value");
        if(oldValue != null)
            reverseLookup.Remove(oldValue);
        reverseLookup[newValue] = key;
    }

    protected override void OnRemoveComplete(object key, object value)
    {
        reverseLookup.Remove(value);
    }
}

The Dictionary and reverseLookup dictionaries will share the same references so it will have a smaller memory footprint than using two strongly typed dictionaries with large structs.

Without writing a full Dictionary<TKey, TValue> implementation that usees two internal bucket collections for keys and values and two linked lists for the chains off of the buckets I don't think you can get much better results.