哈希表和动态数组在计数问题中的应用

哈希表和动态数组总结 哈希表（Hash Table）是一种数据结构，它使用哈希函数将键映射到数组中的索引，以实现快速的查找、插入和删除操作。哈希表的应用非常广泛，例如在搜索引擎、数据库和缓存系统中。 在上面的例题中，需要统计每个数的出现次数，强制在线计算。由于数的最大值可以达到10^9，所以使用数组计数法不适用。排序法可以解决问题，但是时间复杂度为O(nlog(n))，不适合在线计算。因此，需要使用哈希表来解决问题。 哈希表的实现可以使用数组，通常大小为10^6+7或10^7+7。为了避免溢出，可以使用取模的方法将数值映射到数组中，同时记录数值和出现的次数。例如，在上面的例题中，使用模7将数值映射到数组中，然后记录每个数的出现次数。 然而，哈希表也存在一个问题，即哈希冲突（Hash Collision）。例如，以mod7为例，8和1、9和2、10和3等数值会发生冲突。解决哈希冲突的方法有两种：拉链法和线性探测法。拉链法是将表拉成二维数组，取模后如果发现这个格子有数且与它不同，就右移一位。线性探测法是将表拉成一维数组，取模后如果发现这个格子有数且与它不同，就右移一位。 此外，动态数组（Dynamic Array）是一种特殊的数组，它可以根据需要动态地分配和释放内存空间。动态数组可以用来实现哈希表，例如在上面的例题中，可以使用动态数组来实现二维数组，避免了空间浪费。 在C++中，动态数组可以使用vector实现。vector是一种动态数组，能够自动调整大小以适应元素的增加或删除。例如，可以使用vector<int>来实现哈希表，vector中的每个元素是一个整数，表示数值和出现的次数。 哈希表和动态数组是两种非常重要的数据结构，它们广泛应用于计算机科学和软件开发中。哈希表可以快速地查找、插入和删除元素，而动态数组可以动态地分配和释放内存空间，以适应不同的应用场景。