Java HashMap的内存开销与ArrayList相比

Question

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

更新:

我想提高搜索大包(600万+)相同对象的特定值的速度.

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

据我所知,密钥不是存储的,只是密钥的散列,所以它应该像对象的散列大小+一个指针.

但是使用了什么哈希函数？它是Object提供的还是另一个？

Answer 1

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

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

需要注意的关键事项是:

(a)引用或"加载因子"不是杀死你所需的空间,而是创建对象所需的开销.如果密钥是基本类型,或者是2个或更多基元或引用值的组合,则每个密钥将需要其自己的对象,其承载8字节的开销.

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

注意事项:

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

2. 我有一个2.8的数字,插入到ArrayList中的8880502条目与3148004插入-Xmx256M JVM上的HashMap,但是我的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);
    }
}

Answer 2

最简单的方法是查看源代码并以此方式进行处理.但是,你真的在​​比较苹果和橘子 - 列表和地图在概念上非常不同.您很少根据内存使用情况在它们之间进行选择.

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

Answer 3

所有存储在其中的都是指针.根据您的体系结构,指针应为32位或64位(或更多或更少)

10的数组列表倾向于至少分配10个"指针"(以及一些一次性开销的东西).

地图必须分配两次(20个指针),因为它一次存储两个值.然后,最重要的是,它必须存储"哈希".它应该大于地图,在75%的负载下它应该是大约13个32位值(散列).

所以,如果你想要一个随便的答案,比例应该是大约1:3.25左右,但你只是在谈论指针存储 - 非常小,除非你存储大量的对象 - 如果是这样,能够实现即时引用(HashMap)vs iterate(数组)应该比内存大小更重要.

哦,还有:阵列可以适合你的集合的确切大小.如果您指定大小,HashMaps也可以,但如果它"超出"该大小,它将重新分配更大的数组而不使用其中的一些,因此也可能有一些浪费.

Answer 4

我也没有给你一个答案,但快速谷歌搜索在Java中发现了一个可能有帮助的功能.

调用Runtime.getRuntime()freeMemory();

所以我建议用相同的数据填充HashMap和ArrayList.记录空闲内存,删除第一个对象,记录内存,删除第二个对象,记录内存,计算差异,...,利润!

您可能应该使用大量数据.即从1000开始,然后是10000,100000,1000000.

编辑:更正,感谢amischiefr.

编辑:很抱歉编辑你的帖子,但是如果你打算使用它,这是非常重要的(这对评论来说有点多).freeMemory不会像你想象的那样工作.首先,垃圾收集改变了它的价值.其次,当java分配更多内存时,它的值会发生变化.仅仅使用freeMemory调用不能提供有用的数据.

试试这个:

public static void displayMemory() {
    Runtime r=Runtime.getRuntime();
    r.gc();
    r.gc(); // YES, you NEED 2!
    System.out.println("Memory Used="+(r.totalMemory()-r.freeMemory()));
}

或者您可以返回使用的内存并将其存储,然后将其与以后的值进行比较.无论哪种方式,记住2 gcs并从totalMemory()中减去.

再次,抱歉编辑你的帖子!