Golang map internal implementation - how does it search the map for a key?
<p>I've read in &quot;The Go Programming Language&quot; that a &quot;given key can be retrieved ... using a constant number of key comparisons on average, no matter how large the hash table.&quot;  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?</p>
<p>For example, if I have a map with 2,000 keys, does it &quot;on average&quot; 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?</p>