与ArrayList相比，Java HashMap的内存开销

Question

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

更新：

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

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

据我所知，密钥不是存储的，只是密钥的散列，因此它应该类似于对象散列的大小+一个指针

但是使用什么哈希函数呢？是the one offered by Object还是另一个

Answer 1

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

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

Answer 2

Hashmaps试图保持一个加载因子（通常75%已满），您可以将hashmap视为一个稀疏填充的数组列表。直接比较大小的问题是，映射的负载因子会随着数据的大小而增长。另一方面，ArrayList通过将其内部数组大小增加一倍来满足需要。对于相对较小的大小，它们是可比较的，但是当您将越来越多的数据打包到映射中时，需要大量空引用才能保持哈希性能

在任何一种情况下，我都建议在开始添加之前启动预期大小的数据。这将为实现提供一个更好的初始设置，并且在这两种情况下都可能消耗更少的资源

更新：

根据您更新的问题，请签出Glazed lists。这是一个整洁的小工具，由一些谷歌人编写，用于执行与您描述的类似的操作。它也很快。允许群集、筛选、搜索等

Answer 3

其中存储的都是指针。根据您的体系结构，指针应为32或64位（或更多或更少）

一个10的数组列表倾向于至少分配10个“指针”（以及一些一次性开销）

一个映射必须分配两倍（20个指针），因为它一次存储两个值。除此之外，它还必须存储“散列”。它应该比映射更大，在75%的负载下，它应该是大约13个32位的值（散列）

因此，如果你想要一个简单的答案，这个比例应该是1:3.25左右，但你只是在谈论指针存储——非常小，除非你存储了大量的对象——如果是这样的话，能够立即引用（HashMap）和迭代（array）的效用应该比内存大小重要得多

哦，还有： 数组可以适合集合的确切大小。如果指定大小，HashMaps也可以，但是如果它“增长”到该大小之外，它将重新分配一个更大的数组，而不使用其中的一些数组，因此也可能会有一些浪费

Answer 4

我也没有答案，但是快速的谷歌搜索在Java中找到了一个可能有用的功能

运行时。getRuntime（）。freemory（）

因此，我建议您使用相同的数据填充HashMap和ArrayList。记录可用内存，删除第一个对象，记录内存，删除第二个对象，记录内存，计算差异，。。。，利润

您可能应该使用大量的数据来实现这一点。从1000开始，然后是10000、100000、1000000

编辑： 很抱歉编辑了你的文章，但如果你打算使用它，这是非常重要的（这是一个有点多的评论） . 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（）中减去

再次，很抱歉编辑您的帖子

Answer 5

HashMap保存对值和键的引用

ArrayList只需保留对该值的引用即可

因此，假设键使用与值相同的内存，HashMap使用的内存增加了50%（虽然严格来说，不是HashMap使用该内存，因为它只保留对它的引用）

另一方面，HashMap为基本操作（get和put）提供了恒定时间性能，因此，尽管它可能会使用更多内存，但使用HashMap获取元素可能比使用ArrayList快得多

因此，接下来你应该做的是不要关心谁使用了更多的内存，而是他们有什么好处

为程序使用正确的数据结构比库的底层实现方式节省更多的CPU/内存

编辑

在格兰特·韦尔奇给出答案后，我决定测量2000000个整数

这是source code

这是输出

$
$javac MemoryUsage.java  
Note: MemoryUsage.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
$java -Xms128m -Xmx128m MemoryUsage 
Using ArrayListMemoryUsage@8558d2 size: 0
Total memory: 133.234.688
Initial free: 132.718.608
  Final free: 77.965.488

Used: 54.753.120
Memory Used 41.364.824
ArrayListMemoryUsage@8558d2 size: 2000000
$
$java -Xms128m -Xmx128m MemoryUsage H
Using HashMapMemoryUsage@8558d2 size: 0
Total memory: 133.234.688
Initial free: 124.329.984
  Final free: 4.109.600

Used: 120.220.384
Memory Used 129.108.608
HashMapMemoryUsage@8558d2 size: 2000000

Answer 6

如果您将HashMap与ArrayList进行比较，我假定您正在对ArrayList进行某种搜索/索引，例如二进制搜索或自定义哈希表。。。？因为一个。使用线性搜索无法从600万个条目中获取（密钥）

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

需要注意的关键事项是：

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

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

注意事项：

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

2. 我得到的数字是2.8，插入ArrayList的条目为8880502个，而在-Xmx256M JVM上插入HashMap的条目为3148004个，但我的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);
    }
}