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

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

文章目录

• 1 基础知识学习
• • 1.1 什么是Map？
  • 1.2 为什么使用Map？
  • 2 不同的Map实现原理
  • • 2.1 Hash Map
    • • 2.1.1 哈希函数
      • 2.1.2 哈希冲突
      • 2.2 红黑树Map
      • 3 C++中的Map实现
      • • 3.1 std::map
        • 3.2 std::unordered_map
        • 4 总结

          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 

                输出结果：

                3.2 std::unordered_map

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

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

                  示例代码：

                  #include #include int main() {
                      std::unordered_map 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;
                  }
                  

                  输出结果：

                  4 总结

                  在本篇博客中，介绍了Map的基本概念和两种主要实现方式：Hash Map和红黑树Map。我们还简要介绍了C++标准库中的std::map和std::unordered_map。但理论永远是抽象的，在下一篇博客中，我将详细分析C语言中的Hash Map是如何实现的，同时也能加深我们对理论知识的理解。