C++ 中哈希表和数组的区别

在本文中，我们将讨论 C++ 中哈希表和数组之间的区别。在讨论它们的区别之前，我们必须了解哈希表和 数组 及其工作原理、优缺点。

什么是哈希表？

最重要的数据结构之一是哈希表，它使用一种称为哈希函数的特殊函数，该函数将给定值映射到具有可以更快地访问元素的键。

哈希表是一种存储某些信息的数据结构。在这种情况下，所有信息都包含两个主要内容——键和值。哈希表也可以借助关联数组来实现。映射的效率取决于用于映射的哈希函数的效率。

哈希

它是使用恒定时间复杂度O(1)的搜索技术之一，这是哈希的时间复杂度。到目前为止，我们已经学习了两种搜索技术，即线性搜索和二分搜索。线性搜索的最坏时间复杂度为 O(n)，二分搜索为 O(logn)。在这两种搜索技术中，它都取决于元素的数量，而我们只想要一种可以花费恒定时间的技术。这里就出现了哈希技术，它只提供恒定时间。

哈希表在 C++ 中如何工作？

• 哈希函数：哈希函数接受一个键（可以是整数、字符串或任何其他对象）并计算一个索引（哈希值），该索引指向底层数组中的一个位置。
• 处理冲突：当两个键产生相同的哈希值时，即它们映射到表中的同一索引时，就会发生冲突。处理冲突有两种标准方法：
  1. 链表法：每个数组索引包含一个具有相同哈希值的条目的链表。
  2. 开放寻址法：当系统通过预先分配的探测序列搜索下一个可用槽时，会发生冲突。

插入、搜索和删除操作

• 插入：通过将哈希函数应用于键以获得所需的索引来插入键值对，并将值存储在该位置。
• 搜索：为了找到一个值，将哈希函数应用于键，并且将以恒定时间（平均情况）检索相应的值。
• 删除：通过哈希键并从相应位置删除键值对来删除键值对。

C++ 中哈希表的优点

C++ 中哈希表的几个优点如下：

• 恒定时间访问：哈希表中搜索、插入和删除操作的平均时间复杂度为 O(1)。因此，当我们需要快速访问数据时，这些数据结构非常高效。
• 高效查找：哈希表最适用于执行基于唯一键的频繁搜索的应用程序，例如缓存、索引和映射。
• 高效处理大量数据：尽管哈希表可以存储大量数据，但数据访问速度也非常快。轻松适应小型和大型数据集。
• 支持唯一键：由于哈希表维护唯一键，因此它们非常适合键唯一性很重要的集合或字典。
• 动态调整大小：为了获得最大的效率，现代哈希表实现，例如 C++ 中的 std::unordered_map，会随着元素的添加而动态调整其表的大小。因此，避免了在扩展表时性能下降。
• 不需要有序数据：由于哈希表不维护元素之间的任何特定顺序，因此它们适用于顺序不重要但需要快速访问单个组件的情况。

C++ 中哈希表的缺点

C++ 中哈希表的几个缺点如下：

• 内存开销：通常，哈希表比数组和链表等简单数据结构消耗更多内存，以弥补存储键和处理冲突时使用的额外空间。
• 冲突管理：虽然哈希表有处理冲突的程序（如开放寻址法或链表法），但性能下降的可能性始终存在。
• 无序数据：哈希表不允许元素排序。如果我们确实想要排序元素，我们需要使用不同的数据结构，如映射（通常在 C++ 中实现为平衡树）或在插入时显式排序数据。
• 哈希函数的复杂性：选择不当的哈希函数会导致哈希冲突，从而降低性能。好的哈希函数应均匀分布键并最小化冲突以提高效率。
• 非确定性时间复杂度：在最坏情况下，当出现过多哈希冲突时，搜索、插入和删除等操作的时间复杂度将变为 O(n)。

C++ 中的数组是什么？

在 C++ 中，数组是一种数据结构，它在紧邻的内存位置存储具有相同 数据类型 的元素集合。可以使用索引/单个下标或方括号访问每个数组元素，第一个元素从0开始，后续元素以一个为步长递增。数组的大小是固定的；因此，数组大小必须在编译时可知，或者对于动态数组，必须在运行时明确指定。

数组是最简单和使用最广泛的数据结构之一，它们构成了哈希表、链表和树等更复杂数据结构的基础。

数组在 C++ 中如何工作？

• 连续内存：数组为其所有元素分配连续的内存块，允许通过直接计算任何元素的内存地址来更快地访问元素。
• 索引：使用索引访问元素。对于数组 arr，索引为 i 的元素可以表示为 arr[i]。访问时间为O(1)。

C++ 中数组的优点

C++ 中数组的几个优点如下：

• 快速访问：数组读取时间为恒定时间，即 O(1)，因为元素位于连续的内存位置。
• 易于使用：数组非常容易声明、初始化和使用，它是几乎所有编程构建块的基础。
• 空间效率高：与使用指针需要额外内存的链表等其他数据结构相比，占用连续内存位置的数组在内存方面效率更高。
• 支持多维数据：数组可以很好地处理多维数据，例如用于表示矩阵的二维数组或用于更复杂结构的二维数组。

C++ 中数组的缺点

C++ 中数组的几个缺点如下：

• 固定大小：对于静态数组，大小是固定的，并在编译时确定。因此，如果高估了大小，内存就会浪费，如果低估了大小，则可能导致运行时错误。
• 插入和删除开销：插入或删除元素（不包括最后一个）会移动元素，通常非常耗时。
• 无边界检查：C++ 在访问数组时不会执行边界检查。这意味着当数组访问超出任何边界时，不会出现错误或异常，这可能导致未定义行为和难以追踪的错误。
• 功能有限：数组没有内置的搜索、排序或调整大小的功能，这需要额外的实现代码和算法。

哈希表和数组之间的主要区别

C++ 中哈希表和数组之间存在几个主要区别。一些主要区别如下：

结论

总而言之，哈希表就像数组一样，是具有不同用途的基本 数据结构。它们平均访问时间快（O(1)），可以动态调整大小，并支持非整数类型的键。例如，字典、缓存和符号表都受益于哈希表。但是，应该注意的是，它们会消耗额外的存储空间用于哈希和冲突处理内容。相反，数组通过索引进行可预测的 O(1) 访问，可以放置在连续内存中，并且在内存效率方面更高，除了静态数组之外，vector 提供了一个动态选项。通常，数组最适合顺序或可预测索引访问的情况，例如存储有序数据。总而言之，哈希表因其灵活的基于键的操作而被选择，而数组则用于简单的索引存储。