Java HashMap与ArrayList的内存开销比较
我想知道与HashMap相比，java ArrayList的内存开销是多少？
更新：
我想提高搜索一大包(6 Millions+)相同对象的特定值的速度。
因此，我正在考虑使用一个或几个HashMap而不是使用ArrayList。但是我想知道HashMap的开销是多少。
据我所知，键不是存储的，只有键的散列，所以它应该类似于对象的散列的大小+一个指针。
但是使用了什么哈希函数呢？是由对象提供的还是另一个？
回答 13
Stack Overflow用户
发布于 2011-01-07 06:14:27
如果您将HashMap与ArrayList进行比较，我猜想您正在对ArrayList进行某种类型的搜索/索引，例如二进制搜索或自定义哈希表.？因为一个.get(键)到600万个条目使用线性搜索是不可行的。
使用这个假设，我做了一些经验测试，得出了这样的结论：“如果您使用ArrayList进行二进制搜索或自定义散列图实现，相对于HashMap，您可以在相同数量的内存中存储2.5倍的小对象”。我的测试是基于只包含3个字段的小对象，其中一个是键，键是一个整数。我使用了32位JDK1.6。关于"2.5“这一数字的注意事项见下文。
要注意的关键是：
(a)导致您死亡的不是引用或“负载因子”所需的空间，而是对象创建所需的开销。如果键是一个基本类型，或者是2个或更多的原始值或引用值的组合，那么每个键都需要自己的对象，其开销为8个字节。
(b)根据我的经验，你通常需要钥匙作为价值的一部分(例如，为了存储客户记录，按客户id索引，您仍然希望将客户id作为客户对象的一部分)。这意味着HashMap单独存储对键和值的引用有点浪费。
注意事项：
- 用于HashMap键的最常见类型是字符串。对象创建开销在这里不适用，因此差别会更小。
- 我得到了一个2.8个数字，即将8880502个条目插入到ArrayList中，而将3148004项插入到-Xmx256M JVM上，但我的ArrayList负载因子是80%，而我的对象非常小-- 12字节加上8字节对象开销。
- 我的图形和实现都要求将键包含在值中，否则在对象创建开销方面也会出现同样的问题，这只是HashMap的另一个实现。
我的代码：
public class Payload {
int key,b,c;
Payload(int _key) { key = _key; }
}
import org.junit.Test;
import java.util.HashMap;
import java.util.Map;
public class Overhead {
@Test
public void useHashMap()
{
int i=0;
try {
Map<Integer, Payload> map = new HashMap<Integer, Payload>();
for (i=0; i < 4000000; i++) {
int key = (int)(Math.random() * Integer.MAX_VALUE);
map.put(key, new Payload(key));
}
}
catch (OutOfMemoryError e) {
System.out.println("Got up to: " + i);
}
}
@Test
public void useArrayList()
{
int i=0;
try {
ArrayListMap map = new ArrayListMap();
for (i=0; i < 9000000; i++) {
int key = (int)(Math.random() * Integer.MAX_VALUE);
map.put(key, new Payload(key));
}
}
catch (OutOfMemoryError e) {
System.out.println("Got up to: " + i);
}
}
}
import java.util.ArrayList;
public class ArrayListMap {
private ArrayList<Payload> map = new ArrayList<Payload>();
private int[] primes = new int[128];
static boolean isPrime(int n)
{
for (int i=(int)Math.sqrt(n); i >= 2; i--) {
if (n % i == 0)
return false;
}
return true;
}
ArrayListMap()
{
for (int i=0; i < 11000000; i++) // this is clumsy, I admit
map.add(null);
int n=31;
for (int i=0; i < 128; i++) {
while (! isPrime(n))
n+=2;
primes[i] = n;
n += 2;
}
System.out.println("Capacity = " + map.size());
}
public void put(int key, Payload value)
{
int hash = key % map.size();
int hash2 = primes[key % primes.length];
if (hash < 0)
hash += map.size();
do {
if (map.get(hash) == null) {
map.set(hash, value);
return;
}
hash += hash2;
if (hash >= map.size())
hash -= map.size();
} while (true);
}
public Payload get(int key)
{
int hash = key % map.size();
int hash2 = primes[key % primes.length];
if (hash < 0)
hash += map.size();
do {
Payload payload = map.get(hash);
if (payload == null)
return null;
if (payload.key == key)
return payload;
hash += hash2;
if (hash >= map.size())
hash -= map.size();
} while (true);
}
}Stack Overflow用户
发布于 2009-10-06 16:23:03
最简单的方法是查看源代码，并以这种方式计算出来。然而，你真的在比较苹果和橘子--列表和地图在概念上是非常不同的。您很少会根据内存的使用情况在它们之间进行选择。
这个问题背后的背景是什么？
Stack Overflow用户
发布于 2009-10-06 17:36:04
所有存储在这两者中的都是指针。取决于您的体系结构，指针应该是32位或64位(或或多或少)
10的数组列表倾向于至少分配10个“指针”(还有一些一次性开销)。
映射必须分配两倍于此的值(20个指针)，因为它一次存储两个值。更重要的是，它必须存储“哈希”。它应该比地图大，在75%的加载下，它应该在13 32位值(散列)左右。
因此，如果你想要一个临时的答案，这个比率应该是1:3.25左右，但是你只是在说指针存储--除非你存储了大量的对象--如果是这样的话，能够立即引用(HashMap)和迭代(数组)的功能应该比内存大小重要得多。
哦，还有:数组可以与您的集合的确切大小相匹配。如果您指定大小，HashMaps也可以，但是如果它“增长”超过该大小，它将重新分配一个更大的数组，而不是使用其中的一些数组，因此也可能会有一些浪费。
https://stackoverflow.com/questions/1526596
复制相似问题
腾讯云开发者
