How is Map structured in Go?

Map in Go is implemented as a hash table.

Main components of the map structure:

• Hash function: Maps keys to hash values (integers).
• Array of buckets: A set of lists or arrays where key-value pairs are stored. The bucket index is determined by the hash value of the key.
• Collision handling: When different keys have the same hash (collision), elements with these keys are stored in the same bucket, usually as a linked list or overflow into a neighboring bucket.
• Load factor: The ratio of the number of elements to the number of buckets. When a certain threshold is exceeded, rehashing occurs – creating a new, larger array of buckets and moving all elements from old buckets to new ones.

The map structure in Go is represented by the hmap type:

type hmap struct {
    count     int // Number of elements
    flags     uint8 // State flags
    B         uint8 // log_2 of the number of buckets (buckets number is 2^B)
    noverflow uint16 // Number of overflowed buckets (for statistics only)
    hash0     uint32 // Initial hash function value

    buckets    unsafe.Pointer // Pointer to array of buckets (main and overflowed)
    oldbuckets unsafe.Pointer // Pointer to old array of buckets during migration
    nevacuate  uintptr // Indicates how far migration has progressed in old buckets

    extra *mapextra // Additional info (optional)
}

type mapextra struct {
    overflow    *[2]*[]*bmap // Pointers to arrays of overflowed buckets
    oldoverflow *[2]*[]*bmap // Pointers to old overflowed buckets
    nextOverflow *bmap // Next free overflowed bucket
}

type bmap struct {
    tophash [8]uint8 // Top hash (upper bits of hash) for speeding up bucket search
    // Followed by keys, values, and pointer to next bmap (if bucket is overflowed)
    // Layout all the data for hmap.buckets in a single malloc chunk
    // see ../../runtime/map.go for details
}

Operations:

• Insert/Update: Compute the hash of the key, determine the bucket. If the key already exists, update the value. Otherwise, add the key-value pair to the bucket. Rehashing may occur if the bucket overflows or the load factor is exceeded.
• Search: Compute the hash of the key, determine the bucket. Iterate over elements in the bucket by top-hash, then compare full keys. Return the value and a flag indicating presence.
• Delete: Compute the hash of the key, determine the bucket. Mark the element as deleted (but not immediately remove from memory). Deletion occurs during subsequent operations or rehashing.

The map in Go is not synchronized and cannot be safely used by multiple goroutines simultaneously without external synchronization.