Fastest way to retrieve record from dictionary contains 1 million records

Question

I have a dictionary which contains one million of records; the key is numeric and its value is a string. I want to retrieve key from collection using its value.

My application running in multi-threaded environment.

So, what is the fastest way to do so?

Welcome to SO. you've asked for the fastest but shown nothing you tried. SO doesnt write your code for you, questions with nothing shown tend to get closed. If you have code, codereview maybe the better place to ask this — BugFinder, Feb 13 '19 at 09:00
Possible duplicate of [get dictionary key by value](https://stackoverflow.com/questions/2444033/get-dictionary-key-by-value) — default locale, Feb 13 '19 at 09:08
Are there duplicate values in the dictionary? Are you wanting to retrieve only one key or will you need to retrieve more than one? — Enigmativity, Feb 13 '19 at 09:11
Too many unclear aspects. Is your collection going to be accessed from different threads ? Is your collection going to be mutated ? If yes what is the ratio of expected reads and writes for the collection ? — Dmytro Mukalov, Feb 13 '19 at 09:15
Note: "running in multi-threaded environment" is ambiguous; is that "multiple threads that both read and write"? "multiple threads that read, only one thread ever writes"? "multiple threads that read, the data is never changed once constructed", etc; it *really, really* matters — Marc Gravell, Feb 13 '19 at 09:25

dumetrulo · Answer 1 · 2019-02-13T09:30:32.307

2

Your question gives the impression that your dictionary has a one-to-one mapping between keys and values. If that is the case, and if the dictionary does not change very often, and if you need to retrieve the key for a value more than occasionally, the fastest way will be to build a reverse dictionary where the values in the original dictionary are the keys, and the keys are the values. This is some work up-front but will be much faster afterwards:

var revDict = new Dictionary<string, int>();
foreach (var kvp in yourDict) revDict[kvp.Value] = kvp.Key;

EDIT: Or perhaps using LINQ:

var revDict = yourDict.ToDictionary(kvp => kvp.Value, kvp => kvp.Key);

edited Feb 13 '19 at 09:30

answered Feb 13 '19 at 09:15

dumetrulo

1,993
9
11

No idea why this was downvoted; this is a good answer, especially in that it explains the caveats (one-to-one, and all the *and* etc). And once the construction overhead is paid, this will indeed be the fastest way of looking up the key from a value. – Marc Gravell Feb 13 '19 at 09:21
1

Side note: if it was me, I'd use `.Add(kvp.Value, kvp.Key)` instead of the indexer; this will act to enforce the assumption that the data is one-to-one, rather than silently handling duplicated values. – Marc Gravell Feb 13 '19 at 09:23
1

@MarcGravell - I respect your opinion, but don't you think that because the question is lacking in detail - especially around the multi-threading - then any answer is premature and potentially misleading for future readers. Can you help my understanding please? – Enigmativity Feb 13 '19 at 09:30
@Enigmativity on the contrary; precisely *because* we have limited context, IMO this is a fine answer; you're right in that it doesn't explicitly discuss some scenarios that the questions doesn't specify (for example, how to synchronize if it is being mutated at runtime) - but... that's kinda part-and-parcel of the nature of Q&A. If the question is revised to show a more nuanced context, then sure: the answers may also need to be revised. – Marc Gravell Feb 13 '19 at 09:35

score 1 · Answer 2 · answered Feb 13 '19 at 09:46

If I can assume that you have a bi-directional one-to-one mapping with the keys and values AND that you'll be accessing the and updating the dictionary from multiple threads then I suggest you should create a thread-safe bi-directional dictionary.

public class Map<T1, T2>
{
    private object _gate = new object();
    private Dictionary<T1, T2> _forward = new Dictionary<T1, T2>();
    private Dictionary<T2, T1> _reverse = new Dictionary<T2, T1>();

    public Map()
    {
        this.Forward = new Indexer<T1, T2>(_gate, _forward);
        this.Reverse = new Indexer<T2, T1>(_gate, _reverse);
    }

    public class Indexer<T3, T4>
    {
        private object _gate;
        private Dictionary<T3, T4> _dictionary;
        public Indexer(object gate, Dictionary<T3, T4> dictionary)
        {
            _dictionary = dictionary;
            _gate = gate;
        }
        public T4 this[T3 index]
        {
            get { lock (_gate) { return _dictionary[index]; } }
            set { lock (_gate) { _dictionary[index] = value; } }
        }
    }

    public void Add(T1 t1, T2 t2)
    {
        lock (_gate)
        {
            _forward.Add(t1, t2);
            _reverse.Add(t2, t1);
        }
    }

    public Indexer<T1, T2> Forward { get; private set; }
    public Indexer<T2, T1> Reverse { get; private set; }
}

You'd use it like this:

var map = new Map<int, string>();

map.Add(42, "Life");

Console.WriteLine(map.Forward[42]);
Console.WriteLine(map.Reverse["Life"]);

That outputs:

Life
42

slight edge case you may want to consider: in `Add`, you should check whether `_reverse` *already has* an entry keyed with `t2` *before* you `_forward.Add`, because if the first `Add` succeeds and the second `Add` throws, you've broken the expected behavior (you don't need to check `_forward`/`t1`, though - let that one throw as it chooses) — Marc Gravell, Feb 13 '19 at 10:21
@MarcGravell - Yes, that's true. It was a rather thrown-together class. It does need a little more work to make it robust. — Enigmativity, Feb 13 '19 at 11:10

Fastest way to retrieve record from dictionary contains 1 million records

2 Answers2