dictionarygogo-map

Check if key exists in map storing large values


To know a key k exist in a map M1[k]v is very straightforward in Go.

if v, ok := M1[k]; ok {
    // key exist
}

'v': a value of a non-pointer type.

If v is large, To just check if a particular key exists using the above method is not efficient as it will load the value v in the memory(even if I use a blank identifier _ in the place of v as per my understanding and please correct me if my understanding is wrong here).

Is there an efficient way in which we can check if a key is present in a Map(without reading/or the value is allocated in the memory)?

I am thinking to create a new map M2[k]bool to store the information and make an entry in M2 each time I insert something in M1.


Solution

  • Use if _, ok := M1[k]; ok { }. If you use the blank identifier, the value will not be "loaded".

    Let's write benchmarks to test it:

    var m = map[int][1_000_000]int64{
        1: {},
    }
    
    func BenchmarkNonBlank(b *testing.B) {
        for i := 0; i < b.N; i++ {
            if v, ok := m[1]; ok {
                if false {
                    _ = v
                }
            }
        }
    }
    
    func BenchmarkBlank(b *testing.B) {
        for i := 0; i < b.N; i++ {
            if _, ok := m[1]; ok {
                if false {
                    _ = ok
                }
            }
        }
    }
    

    Running go test -bench ., the output is:

    BenchmarkNonBlank-8         1497            763278 ns/op
    BenchmarkBlank-8        97802791                12.09 ns/op
    

    As you can see, using the blank identifier, the operation takes about 10 ns. When we assign the value to a non-blank identifier, it's almost 1 ms (almost a hundred thousand times slower) when the value type has a size of around 8 MB.