Menu
I've read in "The Go Programming Language" that a "given key can be retrieved ... using a constant number of key comparisons on average, no matter how large the hash table." I'm not sure what that means in terms of its implementation internally though. Does that mean it searches through every key until it finds a match or is some type of binary (or other) search algorithm used internally?
For example, if I have a map with 2,000 keys, does it "on average" need to look at 1,000 to find a match or does it look at only 11 (log2 n) as it would with binary search?
583
To check if specific key is present in a given map in Go programming, access the value for the key in map using map[key] expression. This expression returns the value if present, and a boolean value representing if the key is present or not.
The native map type uses a hash table implementation. It uses a hashing function on the key to generate an index into an array of data. Thus, generally, most actions occur in O(1) time.
You can retrieve the value assigned to a key in a map using the syntax m[key] . If the key exists in the map, you'll get the assigned value. Otherwise, you'll get the zero value of the map's value type.
In Go language, a map is a powerful, ingenious, and versatile data structure. Golang Maps is a collection of unordered pairs of key-value. It is widely used because it provides fast lookups and values that can retrieve, update or delete with the help of keys.
Maps are implemented as hash tables. There are plenty of places that explain hashing; Here's a nice visualization you can run.
One nice feature of Go is that
From the source file for hashmap:
// A map is just a hash table. The data is arranged
// into an array of buckets. Each bucket contains up to
// 8 key/value pairs. The low-order bits of the hash are
// used to select a bucket. Each bucket contains a few
// high-order bits of each hash to distinguish the entries
// within a single bucket.
//
// If more than 8 keys hash to a bucket, we chain on
// extra buckets.
https://github.com/golang/go/blob/master/src/runtime/map.go
One thing that you can learn from this code that is not normally covered in a lot of classes is how not to invalidate iterators when the map is resized internally.
58
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
