Java HashMap与ArrayList相比的内存开销

Question

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

更新：

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

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

据我了解，密钥不是存储的，只是密钥的哈希，因此它应该类似于 对象的哈希大小+一个指针 。

但是使用什么哈希函数？是对象提供的还是另一种？

Answer 1

如果您将HashMap与ArrayList进行比较，我假设您正在对ArrayList进行某种搜索/索引，例如二进制搜索或自定义哈希表…？因为使用线性搜索无法通过600万个.get（key）项。

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

要注意的关键事项是：

（a）杀死您的不是引用或“负载因子”所需的空间，而是对象创建所需的开销。如果密钥是原始类型，或者是两个或多个原始或引用值的组合，则每个密钥将需要其自己的对象，该对象带有8个字节的开销。

（b）根据我的经验，您通常需要将键作为值的一部分（例如，存储按客户ID索引的客户记录，但您仍希望将客户ID作为客户对象的一部分）。这意味着IMO在某种程度上浪费了HashMap单独存储对键和值的引用。

注意事项：

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

2. 我得到的数字为2.8，与在-Xmx256M JVM上的HashMap中插入3880004相比，将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);
    }
}