- 数组
- 列表
- 哈希表
- 链表
我记得在不同的地方看到过一些这样的估算，但现在好像找不到了。
我知道这实际上非常复杂，特别是对于像HashMaps这样的东西，但我正在寻找一些粗略的东西，比如：
Memory(HashMap) = fixedOverhead + variableOverhead * tableSize + A*numKeys + B*numValues + Memory(allKeys) + Memory(allValues)
当然，这将根据各种因素而有很大的差异，但即使是粗略估计，也会非常有用。
这张表非常详尽，精确地涉及了以字节为单位衡量的JDK实现选择。如果您想在自己的机器上进行操作 - 如果您正在运行不同的机器，也许 - 这个Google Code网站将允许您下载其源代码。http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures
这可能有点粗糙，但这些估计值应该是正确的。这些是裸骨数据结构，不包括长度变量或其他通常包含在Java中的额外内容。
其中dataType是存储的数据类型
Array: (length n)
n*sizeOf(dataType)
LinkedList:
n*(sizeOf(dataType)+sizeOf(pointer))+sizeOf(pointer[head pointer])
List:
Array-backed=SpaceEfficiency(Array)
LinkedList-backed=SpaceEfficiency(LinkedList)
HashMap: with v values, k keys
v*sizeOf(valueDataType)
Tree: k-way tree with n nodes
n*(sizeOf(nodeDataType)+(k*sizeOf(pointer)))+sizeOf(pointer[head pointer])
Graph: e edges, v vertices
AdjacencyList:
at most: v*((v*sizeOf(vertexDataType))+(e*sizeOf(pointer))) fully connected graph
at least: v*sizeOf(vertexDataType) disconnected graph
AdjacencyMatrix:
v^2*sizeOf(int)
这里有一个简单的程序，它只是消耗内存：
import java.util.*;
/**
RamInit (c) GPLv3
@author Stefan Wagner
@date Do 22. Mär 08:40:40 CET 2012
*/
public class RamInit
{
private java.lang.Object consumer;
public RamInit (char type, int size)
{
switch (type)
{
case 'a': Integer [] ai = new Integer [size];
for (int i = 0; i < size; ++i)
ai[i] = i;
consumer = ai;
break;
case 'l': List<Integer> li = new ArrayList<Integer> ();
for (int i = 0; i < size; ++i)
li.add (i);
consumer = li;
break;
case 'h': HashMap <Integer, Integer> hm = new HashMap <Integer, Integer> ();
for (int i = 0; i < size; ++i)
hm.put (i, size - i);
consumer = hm;
break;
case 'L': LinkedList <Integer> ll = new LinkedList <Integer> ();
for (int i = 0; i < size; ++i)
ll.add (i);
consumer = ll;
break;
default: System.err.println ("invalid: " + type);
}
}
public static void main (String args[])
{
char type = 'a';
int size = 1000000; // 1M
if (args.length == 2)
{
type = args[0].charAt (0);
size = Integer.parseInt (args[1]);
}
try {
new RamInit (type, size);
}
catch (OutOfMemoryError oome)
{
System.exit (1);
}
}
}
这里有一个非常简单的脚本来测试它：
#!/bin/bash
iterProg () {
ram=$1
maxram=$2
typ=$3
size=$4
# echo java -Xmx${ram}M RamInit $typ $((size*1000*1000))
echo -n "."
java -Xmx${ram}M RamInit $typ $((size*1000*1000)) && echo -en "\n"$typ $size ${ram}M || {
if (($ram==$maxram))
then
# echo "fail"
return
else
iterProg $((ram+1)) $maxram $typ $size
fi
}
}
# try from 16 MB to 256
for typ in {a,l,h,L}; do
for size in {1,2,4}; do
iterProg $((size*17+1)) 256 $typ $size
done
done
这是一个原始的迭代器，应该被更复杂的东西所取代 - 例如，如果你需要37MB来调用Collection a和1M元素的RamInit，那么你应该从超过2M个元素开始。
而且你应该选择二分搜索中的步骤，例如如果20M太少了，就检查128，然后(20+128)/2，然后根据下限或上限的成功或失败来计算平均值。
由于HashMap每个元素存储2个Ints，因此它的初始大小应该大约是List/Array/Vector的两倍。然而 - 时间飞逝，当写作时，结果已经完成：
bash iterRamFind.sh
..
a 1 19M.....
a 2 39M...............
a 4 83M..
l 1 19M.......
l 2 41M.......................
l 4 91M..............................................
h 1 63M.............................................................................................
h 2 127M...........................................................................................................................................................................................
h 4 255M......................
L 1 39M.................................................
L 2 83M...............................................................................................
L 4 163
值为17的意义可以从最初的实验中解释清楚。正如我们所看到的，大小几乎成线性增长。
如果您使用Longs来检查影响，修改代码取决于您 - 我猜您最终将得出2的因素。