资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

C语言实现Hash Map(1)：Map基础知识入门

创作时间:

作者:

@小白创作中心

C语言实现Hash Map(1)：Map基础知识入门

引用

CSDN

https://blog.csdn.net/tilblackout/article/details/139006311

Map（映射）是一种重要的数据结构，用于存储键值对。它提供了一种高效的方式来存储和检索数据。常见的Map实现有基于哈希表的Hash Map和基于平衡二叉树的红黑树Map。本文将介绍Map的基础知识，探索不同的Map实现，并简要介绍C++中的这两种实现。

1 基础知识学习

1.1 什么是Map？

Map是一种关联容器，它存储键值对（key-value pairs），通过键（key）来快速查找对应的值（value）。它支持以下主要操作：

插入（Insert）：将一个键值对插入Map。
查找（Find）：根据键查找对应的值。
删除（Delete）：从Map中删除一个键值对。

1.2 为什么使用Map？

Map提供了高效的数据存储和检索方法，常用于需要快速访问数据的场景。例如，符号表、缓存系统、数据库索引等都广泛使用Map数据结构。

2 不同的Map实现原理

2.1 Hash Map

Hash Map是一种基于哈希表的数据结构，它通过哈希函数将键映射到哈希表中的桶（bucket），从而实现快速的查找、插入和删除操作。

原理图示：

2.1.1 哈希函数

哈希函数将键转换为整数（哈希值），然后使用哈希值确定键在哈希表中的位置。一个好的哈希函数应当均匀分布键以减少冲突。

2.1.2 哈希冲突

当两个不同的键产生相同的哈希值时，就会发生哈希冲突。解决哈希冲突的方法包括：

链地址法：每个桶存储一个链表，冲突的键值对将被添加到链表中。
开放寻址法：当冲突发生时，寻找下一个空闲位置存储键值对。

链地址法图示：

2.2 红黑树Map

红黑树是一种自平衡二叉搜索树，确保插入、删除和查找操作的时间复杂度为O(log n)。它通过节点的颜色（红或黑）和一系列平衡规则来保持树的平衡。

红黑树图示：

3 C++中的Map实现

3.1 std::map

std::map是C++标准库提供的基于红黑树实现的有序映射。它按照键的顺序存储键值对，插入、删除和查找操作的时间复杂度为O(log n)。这意味着：

有序性：std::map按照键的顺序存储元素。
遍历顺序：遍历std::map时，会按照键的升序输出元素。

示例代码：

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    for (const auto &pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

输出结果：

1: one
2: two
3: three

3.2 std::unordered_map

std::unordered_map是C++标准库提供的基于哈希表的无序映射。它的插入、删除和查找操作的平均时间复杂度为O(1)。这意味着：

无序性：std::unordered_map按照哈希值存储元素，元素的存储顺序取决于哈希函数和桶的分配情况。
遍历顺序：遍历std::unordered_map时，输出顺序与插入顺序无关，取决于内部哈希表结构。

示例代码：

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> myMap;
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    for (const auto &pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

输出结果：