[SOLVED] How to efficiently search for keys with values in a map

Getting Help
1

I have a map of key value string pairs. The keys are unique (naturally) but so are the values. Is there an efficient way to use a value in the map to find a key (instead of looping through all keys)? The idea is to be able to use the value as a way to get a key and a key as a way to get the value - so I a two way map ¯ \ _ (ツ)_ / ¯
I am open to the use of other data structures if you believe it would be a better fit however bear in mind that I need to also be able to use the key to find the unique value.

Thanks in advance.

2

You need two maps.

Or potentially something else, like a type entry struct { value string; otherIdx int } and then two []entry lists that are sorted and refer to the indexes in the other, which would save you some memory at the price of more work.

But really, two maps. Given how strings work you most likely won’t be storing the string data twice anyway, merely the pointer words.

https://play.golang.org/p/pE217y68zg

2 Likes
3

Cheers man, and thanks for providing a code example.

4

Could you please tell more about this or point to a reference on how strings work and how the data is not stored twice? Thanks!

5

Strings are essentially pointers to a const array of characters. Most compilers are smart enough to realise when the same string is used to initialise two different variables and will only store a single copy of the string. So for instance:

myString1 := "Hello" // 5 bytes + whatever go uses to determine end of a string
myString2 := "Hello" // 5 bytes + whatever go uses to determine end of a string

Would not take up 10 bytes + 2 * whatever go uses to determine end of a string because the compiler while realise they strings are the same and only create a single copy and have both variables point to the same copy. Because strings are immutable this is perfectly fine.

Edit: This is based on my knowledge so far of Go and how strings work in other languages (C++) as well. Of course I am still learning Go, so I could be wrong.

6

Yes. Strings are pointer+length (plus separate storage for the string data). So when we store both m1[a]=b and m2[b]=a you’re storing each pointer+length twice, plus overhead of the map itself, but the actual string data is not duplicated.

7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.