Java HashMap 与 ArrayList 相比的内存开销

我想知道java HashMap与ArrayList相比的内存开销是多少？

Update:

我想提高搜索一大包（600 万以上）相同对象的特定值的速度。

因此，我正在考虑使用一个或多个HashMap来代替ArrayList。但我想知道 HashMap 的开销是多少。

据我了解，密钥不被存储，只存储密钥的哈希值，所以它应该是类似的对象哈希的大小 + 一个指针.

但是使用什么哈希函数呢？是吗Object 提供的一个 http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Object.html#hashCode()或者另一个？

如果您将 HashMap 与 ArrayList 进行比较，我认为您正在对 ArrayList 进行某种搜索/索引，例如二分搜索或自定义哈希表......？因为使用线性搜索 .get(key) 超过 600 万个条目是不可行的。

使用这个假设，我做了一些实证测试，并得出了这样的结论：“如果使用带有二分搜索或自定义哈希映射实现的 ArrayList，那么与 HashMap 相比，您可以在相同数量的 RAM 中存储 2.5 倍数量的小对象” 。我的测试是基于只包含3个字段的小对象，其中一个是键，键是一个整数。我用的是32位的jdk 1.6。有关“2.5”这个数字的注意事项，请参见下文。

需要注意的关键事项是：

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

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

Caveats:

1. HashMap 键最常用的类型是字符串。对象创建开销在这里不适用，因此差异会更小。

2. 我得到的数字是 2.8，即 8880502 个条目插入到 ArrayList 中，而在 -Xmx256M JVM 上插入到 HashMap 中的条目为 3148004 个，但我的 ArrayList 负载系数为 80%，而且我的对象非常小 - 12 字节加上 8 字节对象开销。

3. 我的图和我的实现要求键包含在值中，否则我会遇到与对象创建开销相同的问题，并且它只是 HashMap 的另一个实现。

My code:

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);
    }
}