Golang地图内部实现-如何在地图上搜索密钥？

Question

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?

Thanks, Ben

Answer 1

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. This is only generally true as some keys can result in the same index when hashed, called a collision, which then must be handled specially.

Hash tables are cool!