What is a hash table?

A hash table (or associative array, dictionary) is a data structure that stores pairs of "key-value" and allows for fast lookup, insertion, and deletion of elements by their key.

In Golang, a hash table is implemented as the map type.

Working principle:

1. Hashing the key: For each key, a hash value is computed using a hash function. The hash function transforms a key of any size into a fixed-size number.
2. Determining the index: Based on the hash value, an index in the array (bucket or slot) is determined, where the "key-value" pair will be stored. Usually, a modulo operation by the array size is used.
3. Collisions: Since different keys can produce the same hash value (or determine the same index), a collision occurs. Various methods are used to resolve collisions, for example:
   • Separate Chaining: Each bucket stores a list of "key-value" pairs that have the same index.
   • Open Addressing: When a collision occurs, a free slot in the array is searched using different strategies (linear probing, quadratic probing, etc.). Golang uses a combination of these approaches.

Advantages of hash tables:

• High access speed: On average, insertion, deletion, and search operations have a complexity of O(1).
• Flexibility: Can store keys and values of various data types.

Disadvantages:

• Possibility of collisions: Performance can degrade with a large number of collisions.
• Dependence on the hash function: The quality of the hash function directly affects performance.
• Memory consumption: Usually requires more memory compared to arrays or linked lists.

Example of creating and using a map in Golang:

package main

import "fmt"

func main() {
	// Creating a map with string keys and integer values
	ages := make(map[string]int)

	// Adding elements
	ages["Alice"] = 30
	ages["Bob"] = 25
	ages["Charlie"] = 35

	// Getting a value by key
	aliceAge := ages["Alice"]
	fmt.Println("Age of Alice:", aliceAge)

	// Checking if a key exists
	_, exists := ages["David"]
	if !exists {
		fmt.Println("David not found")
	}

	// Deleting an element
	delete(ages, "Bob")

	// Iterating over the map (order is not guaranteed)
	for name, age := range ages {
		fmt.Printf("%s: %d\n", name, age)
	}
}