What data structures make up the implementation of key-value mapping in most programming languages?

In most programming languages, the implementation of key-value mapping (e.g., map, dictionary) is based on two main data structures:

1. Hash table — the basis for fast access by key. The key is transformed into a hash code, which points to an index in an array where the value is stored.

2. Linked lists or trees — used to resolve collisions when different keys have the same hash code. For example, in Go, chains (linked lists) or balanced trees are used to resolve collisions.

In Go, map is implemented as a hash table with dynamic resizing and optimizations for efficient access and insertion.

Example of using a map in Go:

m := make(map[string]int)
m["apple"] = 5
fmt.Println(m["apple"]) // 5