Java HashMap 的内存开销与 ArrayList 的比较

如果你正在比较HashMap和ArrayList，我假设你正在对ArrayList进行某种搜索/索引，例如二进制搜索或自定义哈希表...？因为使用线性搜索，通过600万个条目的.get（key）是不可行的。

利用这个假设，我做了一些经验测试，得出的结论是“如果你使用ArrayList与二进制搜索或自定义哈希映射实现，你可以在相同数量的RAM中存储2.5倍的小对象，而不是HashMap”。我的测试基于仅包含3个字段的小对象，其中一个是键，键是整数。我用了一个32位的jdk 1.6。有关此数字“2.5”的注意事项，请参见下文。

需要注意的关键事项是：

（a）杀死你的不是引用或“负载因子”所需的空间，而是创建对象所需的开销。如果键是基元类型，或者是 2 个或更多基元值或引用值的组合，则每个键都需要自己的对象，该对象的开销为 8 个字节。

（b） 根据我的经验，您通常需要密钥作为值的一部分（例如，存储按客户 ID 编制索引的客户记录，您仍然希望客户 ID 作为 Customer 对象的一部分）。这意味着IMO单独存储对键和值的引用有点浪费。

警告：

1. 用于 HashMap 键的最常见类型是 String。此处不适用对象创建开销，因此差异会更小。

2. 我的数字是2.8，与3148004插入到-Xmx256M JVM上的HashMap相比，8880502条目插入到ArrayList中，但我的ArrayList加载因子是80%，我的对象非常小 - 12字节加上8字节的对象开销。

3. 我的图和我的实现要求密钥包含在值中，否则我会遇到对象创建开销的相同问题，它只是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);
    }
}

最简单的事情就是查看源代码并以这种方式解决它。但是，您实际上是在比较苹果和橙子 - 列表和地图在概念上是完全不同的。您很少会根据内存使用情况在它们之间进行选择。

这个问题背后的背景是什么？