CODEWITHSUNDEEP
javadata-structurescollections
vikas368
vikas368

Reputation: 1468

which type of data structure is best?

In my application, we already have 

Map<String, List<String>>

Now we got another use-case where need to find a key which is mapped to a particular string inside the list.

I am thinking of writing following: 

string getKey(Map<String, List<String>> m, String str) {
  for (Entry<String, List<String>> entry :m.entrySet()) {
    if(entry.getValue().contains(str)) {
      retrun entry.getKey();
    }
  }
  return null;
}

Map can have at max 2000 entries. and each List can have at max 500 Strings.

Any suggestions that might be a better fit? I can change the initial data structure (Map) also if there is a better way to do it..

Upvotes: 2

Views: 366

Answers (2)

posdef
posdef

Reputation: 6532

Are you familiar with Guava API? If you have the liberty to add/change dependencies, it's definitely worth checking out, particularly implementations of the Multimap interface. It's exactly built for those cases where the same key can be mapped to multiple values.

In case I misunderstood the question and the same key will not be mapped to multiple values then you might need to reformulate/rethink your question as your current idea Map<String, List<String>> is essentially just that.

Upvotes: 2

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

I would suggest that you add another map that gives the reverse mapping - from a string to list of keys. This will require a bit more of work to keep in sync with the first map but will give the best performance for your task.

Still if you think the frequency of such queries will be relatively low, maybe your solution could be better(although slower, the time you save for keeping both maps in sync will make up for that).

Upvotes: 5

Related Questions