unordered_map and Algorithm Complexity Analysis: Search, Insertion, Deletion

# 1. Introduction

In software development, associative containers are a vital data structure used to store key-value pairs. Associative containers provide fast searching, insertion, and deletion capabilities and are one of the commonly used tools in programming. When using associative containers, it's important to understand the different types and characteristics of these containers to choose the appropriate one to solve a given problem.

During operations with associative containers, we need to consider the algorithm's complexity, including time complexity and space complexity. These complexity indicators can help us evaluate the efficiency of the algorithm and resource consumption, thereby choosing the right algorithm to enhance the performance of the program.

By studying associative containers and algorithm complexity, we can better understand the relationship between data structures and algorithms, laying a solid foundation for future programming work.

# 2. Introduction to unordered_map

#### 2.1 Overview of unordered_map
In C++'s Standard Template Library (STL), the `unordered_map` is an associative container implemented with a hash table, ***pared to `map`, `unordered_map` has an advantage in terms of average time complexity for insertion, searching, and deletion operations.

##### 2.1.1 Characteristics of unordered_map
- Unordered: Elements are stored in an unordered manner and are not sorted based on the key's value.
- Fast Search: Implemented using a hash table, the average time complexity for searching, inserting, and deleting operations is O(1).
- Support for Custom Hash Functions: Custom hash functions can be defined to improve performance based on specific requirements.

##### 2.1.2 Differences from map
- Ordering: `map` is an ordered associative container that sorts elements from the smallest to the largest key, whereas `unordered_map` does not.
- Implementation: `map` is typically implemented using a red-black tree, while `unordered_map` is based on a hash table.

#### 2.2 Using unordered_map
`unordered_map` provides a simple API for inserting, deleting, and searching for elements.

##### 2.2.1 Inserting Elements
The `insert` function can be used to insert key-value pairs into `unordered_map`. If the key already exists, insertion fails.

#include <iostream>
#include <unordered_map>

int main() {
     std::unordered_map<std::string, int> umap;

     // Insert key-value pairs
     umap.insert({"apple", 3});
     umap["banana"] = 5;

     return 0;
}

##### 2.2.2 Deleting Elements
The `erase` function can delete elements based on their key.

// Delete the element with the key "apple"
umap.erase("apple");

##### 2.2.3 Searching for Elements
The `find` function can be used to search for a specific key.

// Search for the element with the key "banana"
auto it = umap.find("banana");
if (it != umap.end()) {
     std::cout << "Value of banana: " << it->second << std::endl;
}

From these operations, we can see that the usage of `unordered_map` is straightforward and efficient. It can be flexibly applied based on specific needs.

# 3. Underlying Implementation of unordered_map

- 3.1 Principles of unordered_map
- 3.1.1 Concept of Hash Tables
A hash table is a data structure that maps keys to positions in a table using a hash function, enabling fast insertions, deletions, and searches. The basic components of a hash table include an array and a hash function.
- 3.1.2 Importance of Hash Functions
The hash function is crucial for the performance of a hash table, as a good hash functi