SoFunction
Updated on 2025-03-01

Detailed explanation of whether custom structures in Go can be used as map keys

1. Introduction

In Go,mapis a built-in data type that provides an efficient way to store and retrieve data.mapIs an unordered set of key-value pairs where each key is associated with a value. Use map data structures to quickly find the corresponding value based on keys without traversing the entire collection.

In Go,mapis a built-in data type that can be declared and initialized in the following ways:

m := make(map[keyType]valueType)

In usemapWhen we usually use the basic data type as key. However, when we need to use a custom structure as a key, we need to consider whether the structure contains fields of reference type. Reference type refers to the type of address that stores data, such as pointers, slices, dictionaries, and channels. existGoIn , the reference type has dynamic characteristics and may be modified or point to new data. This raises the question: Can custom structures containing reference types be used asmapWhat about the key?

2. The basic model of map

Find out if you can use a custom structure containing a reference type asmapWe need to understand the key issue firstmapbasic model. In Go,mapImplemented using a hash table. A hash table is a data structure that stores data in key-value pairs, which maps keys to hash values ​​by using a hash function.

The hash function is an algorithm used to map keys to hash values. It accepts keys as input and generates a fixed-length hash. Go languagemapThe internal hash function is used to calculate the hash value of the key.

And differentkeyThe hash value generated by the hash function may be the same, and a hash collision occurs. Hash conflict refers to the same hash value obtained after different keys are calculated by the hash function. Since the output space of the hash function is much smaller than the input space of the key, hash collisions are inevitable. It is impossible to judge thiskeyIs it an element that already exists in the current hash table or is it because of hash conflict that different keys map to the same bucket. You need to judge these twokeyWhether it is equal or not.

Therefore, inmapIn, asmapIn-housekey, if it needs to be ensured that it supports comparison operations, two can be comparedkeyWhether it is equal or not.

3. Requirements for map key

From abovemapIn the basic model introduction, we learned thatmapThe key in it needs to support the calculation of hash function, and the key type must support comparison operations.

existmapIn, calculatekeyThe hash value ofmapIn-housekeyThere are no additional requirements.

existmapIn the process, determining whether two keys are equal is by calling the equality operator of the key type (==or!=) to complete it, sokeyMust be sure to support this type==operate. This requirement ismapThe implementation mechanism determines.mapThe equality of keys is used internally to determine the storage location of the key and the search value. If the key types are not comparable, equality comparison cannot be performed, resulting in the inability to accurately locate the key and retrieve the values.

In Go, basic data types (such as integers, floating point numbers, strings) and some built-in types are comparable, so they can be used directly asmapkey. However, when a custom structure is used as a key, it is necessary to ensure that all fields of the structure are of comparable types. If the structure contains a field of reference type, the structure cannot be used directly asmapkeys, because the reference type does not have simple equality comparison.

Therefore, ifmapThe key in the key is a custom type and contains a reference field. It will not be used asmapThe key will fail directly to compile. The code example is as follows:

type Person struct {
   Name    string
   Age     int
   address []Address
}
func main() {
    // It will be compiled directly here without passing    m := make(map[Person]int)
}

The second is that the custom structure contains a field of pointer type, which is supported at this time.==Operation, but it is done using pointer addresshashComputation and equality comparison, it is possible that we understand that it is the samekey, in factmapIt doesn't seem to be true, it is very easy to cause errors at this time. The examples are as follows:

type Person struct {
   Name    string
   Age     int
   address *Address
}
func main(){
    m := make(map[Person]int)
    p1 := Person{Name: "Alice", Age: 30, address: &Address{city: "beijing"}}
    p2 := Person{Name: "Alice", Age: 30, address: &Address{city: "beijing"}}
    m[p1] = 1
    m[p2] = 2
    // Output 1    (m[p1])
    // Output 2    (m[p2])
}

Here we define aPersonStructure containing a field of pointer typeaddress. Two objects were createdp1andp2,In our understanding, it is the same object, in factmapThere are two unrelated objects in the process. The main reason is to use the address to perform hash calculation and equality comparison.

To sum up, if the custom structure contains a field of reference type (the pointer is a special reference type), it will not be used asmapType ofkey。

4. Why not extract hashCode and equals method interfaces and implement them by the user

currentgomiddlemapThe calculation of hash value in the hash value provides the default hash function and does not need to be implemented by the user; secondlykeyComparison of equality is through==The operator is implemented, and the comparison function is not customized by the user. Then we have a question, why not extract the hashCode and equals method interfaces and implement them by the user?

4.1 Simplicity and performance angles

Equalities are comparedGoUsed in language==Operators are implemented, and hash functions are the default implementation provided by the runtime library. I understand this design choice for several reasons:

  • Simplicity: For the default hash function function, it is built into the language and does not require additional implementation and configuration from the user. This simplifies the use of maps. For equality comparison operations,==Comparison of operators is an intuitive and simple way. In terms of grammar,==Operators are used to compare whether two values ​​are equal, and this syntax simplicity makes the code more readable and understandable.
  • performance: The default hash function is optimized and tested to provide good performance in most cases. Next use==to achieve equality comparison, because==Operators are native operations at the language level, and the compiler can optimize them to improve the execution efficiency of the code.

4.2 Key immutable limitations

mapThe immutability of bonds is also a consideration. based on==To determine whether the objects are equal, indirectly guaranteeing the immutability of the key. at present,==Most types of comparisons have been supported, only the reference type fields in the custom structure cannot be used directly==Make a comparison. If there is no reference type field in the key, this means that the value put in the Map key cannot change at runtime, thus ensuring the immutability of the key at runtime.

ifkeyThere is no immutable limit, then it was stored inmapThere may be problems with key-value pairs in it. Because when placing elements,mapThe hash value is calculated based on the current value of the key, and the hash value is used to find the corresponding storage location. If placedmapThe value of the key in the change has changed, and it is calculated at this timehashThe values ​​may also change, which means the data is placed in the wrong place. Even if you use it latermapIf the same value of the key in the search key is used, the data may not be found.

Here is a simple code to illustrate the variable type askeyProblems that will be caused:

type Person struct {
    Name       string
    Age        int
    SliceField []string
}
func main() {
    person := Person{Name: "Alice", Age: 25, SliceField: []string{"A", "B"}}
    // Assuming Person can be used as a key, it is actually not supported    personMap := make(map[Person]string)
    personMap[person] = "Value 1"
    // Modify the value of SliceField in person    [0] = "X"
    // Try to find the value through the same person    (personMap[person]) // Output an empty string, the corresponding value cannot be found}

If drawnequalsMethod interface is implemented by the user, at this timekeyThe immutability of the user needs to implement it, and secondlygoThe language also needs to add some detection mechanisms, which first increases the burden on users, which is not in line withgoPhilosophy of language design.

4.3 Summary

To sum up, based on considerations of simplicity, performance and semantic consistency and key immutability, Go language chooses to use==Operators perform key comparisons, and hash functions as the default implementation of runtime library is more in line withgoPhilosophy of language design.

5. Summary

In Go language, map is an unordered set of key-value pairs that provide efficient data storage and retrieval mechanisms. When using map, the basic data type is usually used as the key. However, when we want to use a custom structure as a key, we need to consider whether the structure contains fields of reference type.

Custom structure asmapThe key needs to meet some requirements. First, the key types must be comparable, that is, they support the== Operators perform equality comparison. existGoIn this case, basic data types and some built-in types meet this requirement. However, if the structure contains a field of reference type, the structure cannot be directly used asmapkeys, because the reference type does not have simple equality comparison.

Therefore, in general, a custom structure containing a reference type field cannot be used asmapofkeyof.

The above is a detailed explanation of whether custom structures in Go can be used as map keys. For more information about Go maps, please follow my other related articles!