0

根据我对哈希图的理解,内部数据结构可以看作是一个二维数组。第一个索引是“键”,第二个索引是包含哈希到同一键的值的数组。在我看来,您需要初始化一个足够大的数组以考虑未来的条目(否则您需要在某个点扩大数组或所有值散列到相同的值)。由于初始化特定大小的数组的初始成本,这意味着哈希图与链表相比具有较高的初始成本。

链表只需要表示 X 个项目所需的内存。我在这个假设中正确吗?我只是感到困惑,因为很多人说 LinkedList 使用更多内存。

4

2 回答 2

0

您忘记了 Map 具有键和值。所以对于列表中的每个项目,地图中有 2 个。因此,如果 LinkedListn在存储方面需要成本,则 Map 将需要2n. 除此之外,正如您所指出的,您必须有一些可用空间,所以现在您最多为 2n + 2n*.c,即 (1+c)2n,其中 c 是 0.25 之类的分数。

那么与链表相比,这是否符合“高”空间要求?我不这么认为,除非您的内存要求受到限制。请记住,您还可以获得对任何元素的恒定时间访问,对于链表,它的访问时间为 O(n)。

最后,由于 Maps 处理具有键和值的问题,而列表主要只关注值,因此应用这些数据结构的问题往往不同,所以这个问题可能没有多大意义。

于 2012-11-19T23:05:07.287 回答
0

只是一些数字:

一个空的 HashMap 需要 128 个字节:开销是 64 个字节加上每个条目 36 个字节。对于 10K 条目,预期开销约为 360K

一个空的 LinkedList 需要 48 个字节:开销是 24 个字节,加上每个条目 24 个字节。对于 10K 条目,预期开销约为 240K

来源:http ://www.ibm.com/developerworks/java/library/j-codetoheap/

图片来自谷歌搜索

于 2012-11-19T23:12:11.777 回答