What is the maximum card performance in the golang?

Question

The Map Types section of the go language specification describes the interface and general use of map types, and the Go maps in action post on the Go blog casually mentions hash tables and quick search, add and delete.

the current runtime/hashmap.go source code describes its implementation as a hash table (which is usually amortized by O(1) ); however, I see no guarantee of performance (such as Big O performance) in the language specification or other materials.

Does go support any kind of performance guarantee (for example, insert / search / delete constant duration?) For map types or only interface guarantees? (Compare with the Java language, where interfaces and implementations are clearly separated.)

Answer 1

Linking to a language does not give any explicit guarantees regarding card performance. There's an implicit expectation that maps work the way you expect hash tables to execute. I do not see to guarantee that the guarantee of effectiveness will be either vague or inaccurate.

Big-O complexity is a bad way to describe launch times for cards: the actual time of the clock is actual, but complexity is not. Theoretically, cards with keys from final domains (e.g. int) are trivial to O (1) in space and time, and cards with keys with infinite domains (e.g. strings) require hashing and equality testing specifics, which should be included in the price, which makes inserting and searching for the best case O (N log N) on average (since keys must be at least O (N log N) on average to build a hash table with N elements. If you do not get this data directly into the specification, which will be inaccurate, and the benefits of her right are not worth it justify it.

It will also be difficult to provide assurances regarding the actual execution time, and not complexity: there is a wide range of target machines, as well as problems associated with caching and garbage collection.

Answer 2

From what I see, the "Programming Programming Language" provides no performance guarantees for card types. Hash tables in general are O (1) for inserting, searching, and deleting data; we can assume that this is also true for Go maps.

If you are concerned about card performance, you can always benchmark your code on different loads and decide whether to use Go cards or some other data structure.

Answer 3

To be precise, the performance of the hash tables is O (1 + n / k) for conflict resolution, where n / k refers to the load factor. Go spec declares cards as not limiting the number of keys. Therefore, they need to dynamically resize with a partial reboot in order to maintain the load factor during growth or contraction. This means that near O (1) can be easily reached for searching maps with a constant size, but even theoretically cannot be guaranteed for massive insertion or deletion. Such operations require redistribution, partial reboots, and possible garbage collections to preserve load factors and use memory wisely.