根据我对哈希图的理解，内部数据结构可以看作是一个二维数组。第一个索引是“键”，第二个索引是包含哈希到同一键的值的数组。在我看来，您需要初始化一个足够大的数组以考虑未来的条目（否则您需要在某个点扩大数组或所有值散列到相同的值）。由于初始化特定大小的数组的初始成本，这意味着哈希图与链表相比具有较高的初始成本。
链表只需要表示 X 个项目所需的内存。我在这个假设中正确吗？我只是感到困惑，因为很多人说 LinkedList 使用更多内存。
问问题
503 次
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 回答