根据我对哈希图的理解,内部数据结构可以看作是一个二维数组。第一个索引是“键”,第二个索引是包含哈希到同一键的值的数组。在我看来,您需要初始化一个足够大的数组以考虑未来的条目(否则您需要在某个点扩大数组或所有值散列到相同的值)。由于初始化特定大小的数组的初始成本,这意味着哈希图与链表相比具有较高的初始成本。
链表只需要表示 X 个项目所需的内存。我在这个假设中正确吗?我只是感到困惑,因为很多人说 LinkedList 使用更多内存。
根据我对哈希图的理解,内部数据结构可以看作是一个二维数组。第一个索引是“键”,第二个索引是包含哈希到同一键的值的数组。在我看来,您需要初始化一个足够大的数组以考虑未来的条目(否则您需要在某个点扩大数组或所有值散列到相同的值)。由于初始化特定大小的数组的初始成本,这意味着哈希图与链表相比具有较高的初始成本。
链表只需要表示 X 个项目所需的内存。我在这个假设中正确吗?我只是感到困惑,因为很多人说 LinkedList 使用更多内存。
您忘记了 Map 具有键和值。所以对于列表中的每个项目,地图中有 2 个。因此,如果 LinkedListn
在存储方面需要成本,则 Map 将需要2n
. 除此之外,正如您所指出的,您必须有一些可用空间,所以现在您最多为 2n + 2n*.c,即 (1+c)2n,其中 c 是 0.25 之类的分数。
那么与链表相比,这是否符合“高”空间要求?我不这么认为,除非您的内存要求受到限制。请记住,您还可以获得对任何元素的恒定时间访问,对于链表,它的访问时间为 O(n)。
最后,由于 Maps 处理具有键和值的问题,而列表主要只关注值,因此应用这些数据结构的问题往往不同,所以这个问题可能没有多大意义。
只是一些数字:
一个空的 HashMap 需要 128 个字节:开销是 64 个字节加上每个条目 36 个字节。对于 10K 条目,预期开销约为 360K
一个空的 LinkedList 需要 48 个字节:开销是 24 个字节,加上每个条目 24 个字节。对于 10K 条目,预期开销约为 240K
来源:http ://www.ibm.com/developerworks/java/library/j-codetoheap/