1

First, this question is not a duplicate of Most efficient method to get key for a value in a dict for the inquirer there asked about python and also because I want to discuss if solution given below makes sense and if it is fine to go about such a problem.

So, let's suppose, I have following a following datastructure:

{ 
   "one" : "1",
   "two" : "2",
   .
   .
   "hundred thousand" : "100000"
}

Now, I want to able to get key against a particular value (assuming that I will not have same values for different keys). One solution is to get key by iterating the data but how efficient can become our code if we structure our data as:

 data = [
    { 
       "one" : "1",
       "two" : "2",
       .
       .
       "hundred thousand" : "100000"
    },
    { 
       "1" : "one",
       "2" : "two",
       .
       .
       "100000" : "hundred thousand"
    }
   ]

So, now data[0]."two" can be used to get value of two. But, let's suppose there is a scenario in which I know the value as 999 and I want to know it's key so to get its key I will do data[1]."999" i.e. I will use the reversed data in data[1].

This solution is perhaps faster than iterating over data to find right key. What do you think?

Community
  • 1
  • 1
Uthman
  • 9,251
  • 18
  • 74
  • 104
  • 2
    I don't of a way to do this in standard Javascript that doesn't involve iterating over the complete set of elements. Also it is important to point out that if you are talking about Javascript in this question then what you have above is _not_ a dictionary but an array of _objects_. Have a look at this question: http://stackoverflow.com/questions/9907419/javascript-object-get-key-by-value – Hunter McMillen Jul 09 '12 at 12:35
  • Will the dictionary always be sorted, as illustrated in your example? – Skylar Anderson Jul 09 '12 at 12:37
  • 1
    So rather than accepting O(n) for your search, you want to double the amount of storage and create another object that you'll have to sync as well. Is that overhead worth it? – StuperUser Jul 09 '12 at 12:42
  • Well, @StuperUSer you are right, it will become memory intensive. – Uthman Jul 09 '12 at 12:47

2 Answers2

2

You're correct that iterating over all the keys is inefficient, and the method you propose of keeping a reverse lookup hash around is the most common one I've seen for solving this problem. The best solution, of course, is to have a design where you don't need to perform the reverse lookup.

If you're storing a small number of keys, and performing this lookup infrequently, then you're probably fine with the O(n) cost (of course, in that case, maintaining a reverse lookup hash doesn't hurt much either). On the other extreme, where you have millions of keys and can't take the memory hit of having a reverse lookup hash, you could use something like Bloom Filters to help reduce the cost of lookups.

Ben Taitelbaum
  • 7,343
  • 3
  • 25
  • 45
  • Bloom Filters can only help to find if a particular value "exist" in a set though. – Uthman Jul 09 '12 at 13:06
  • @baltusaj well, they tell you if the particular value _probably_ exists in the set, so the specific optimization is in the case where you have a giant set, and most of the values you want to look up don't exist in the set, so you can check the bloom filter first, and only do the lookup if you get a positive. It's probably not relevant here, but I wanted to sound smart :/ – Ben Taitelbaum Jul 09 '12 at 15:12
0

There isn't a general solution to your problem since multiple keys can have the same value. For your specific example, if you're talking about efficiency in terms of speed, then yes, your current solution of having a reverse map is the fastest way to do it (at the expense of additional space for storing the reverse map).

casablanca
  • 69,683
  • 7
  • 133
  • 150