1

假设我想要某种位图来了解特定字符在字符串中出现的次数。

因此，例如，如果我读到字符串“abracadabra”，我会得到一个看起来像这样的数据结构：

a -> 5
b -> 2
r -> 2
c -> 1
d -> 1

我读过一本书（Programming INInterviews Exposed），上面写着：

哈希表比数组具有更高的查找开销。
一个数组需要一个元素来代表每个可能的字符。
哈希表只需要存储实际出现在字符串中的字符。所以：

对于具有有限可能字符集的长字符串，数组是更好的选择，而哈希表对于较短的字符串或有许多可能的字符值时更有效。

我不明白为什么：

-> Hashtables 比数组有更高的查找开销？这是为什么？

4

3 回答 3

3

数组是一种极其简单的数据结构。在内存中，它是一个简单的连续块。假设数组中的每个项目都是四个字节，并且数组有 100 个元素的空间。那么数组只是内存中的 400 个连续字节，分配给数组的变量是指向第一个元素的指针。假设这是内存中的位置 10000。

当您访问数组的元素 #3 时，如下所示：

myarray[3] = 17;

...发生的事情非常简单：将 3 乘以元素大小（4 字节）添加到基指针。在此示例中，它是 10000 + 3 * 4 = 10012。然后您只需写入位于地址 10012 的 4 个字节。非常简单的数学运算。

哈希表不是基本数据结构。它可以以多种方式实现，但简单的一种可能是 256 个列表的数组。然后当你访问哈希表时，首先你要计算你的键的哈希值，然后在数组中查找正确的列表，最后沿着列表查找正确的元素。这是一个复杂得多的过程。

一个简单的数组总是比哈希表快。您引用的文字是，如果数据非常稀疏......您可能需要一个非常大的数组来进行这个简单的计算。在这种情况下，您可以使用更少的内存空间来保存哈希表。

考虑一下你的字符是否是 Unicode——每个字符两个字节。那是 65536 个可能的字符。并假设您只谈论具有 256 个或更少字符的字符串。要使用数组计算这些字符，您需要创建一个包含 64K 元素的数组，每个元素一个字节......占用 64K 内存。另一方面，像我上面提到的那样实现的哈希表可能只占用 4*64 字节的列表指针数组，然后每个列表元素占用 5-8 个字节。因此，如果您正在处理一个包含 64 个唯一 Unicode 字符的 256 个字符的字符串，那么它总共最多占用 768 个字节。在这些条件下，哈希表将使用更少的内存。但它总是会变慢。

最后，在你展示的简单案例中，你可能只是在谈论拉丁字母，所以如果你强制使用小写字母，你可以有一个只有 26 个元素的数组，并让它们尽可能大，这样你就可以计算出尽可能多的元素您需要的字符。即使是 40 亿，您也只需要 26 * 4 = 104 个字符数组。所以这绝对是去这里的方式。

于 2013-02-11T19:49:37.847 回答
2

哈希表比数组有更高的查找开销？这是为什么？

当访问一个字符计数数组时，它是直接访问：counter[c]++;

虽然 hastable 是一种（复杂的）数据结构，但首先必须计算一个散列函数，然后是第二个函数以将 hascode 减少到散列表的位置。如果表位置已被使用，则必须执行附加操作。

我个人认为，只要您的角色在 Asci 范围（0-255）内，数组方法总是更快，更适合。如果涉及到 uni 码字符（在 java 中是 Strings 中的默认值，那么 hashtable 更合适。）

于 2013-02-11T19:42:41.383 回答
0

哈希表比数组有更高的查找开销？这是为什么？

因为他们必须搜索 key来计算 key 的 hash。

相反，数组有O(1)查找时间。对于访问数组中的值，通常计算偏移量并返回该偏移量处的元素就足够了，这在恒定时间内起作用。

于 2013-02-11T19:35:52.593 回答