Java HashMap相对于ArrayList的内存开销问题

Question

我想知道Java HashMap和ArrayList相比的内存开销有多大？

更新：

我希望提高对大型包（6百万个以上）相同对象的特定值搜索速度。

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

据我所了解，它不存储键本身，只存储键的哈希值，因此它应该类似于对象哈希大小+一个指针。

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

- elhoim

---

与ArrayList相比，一个HashMap会占用多少更多的内存空间，这根本不是复制问题。 - elhoim

你是否在考虑使用两个 ArrayList 还是一个 HashMap？ - Dean J

你关于只有哈希值被存储的说法是错误的。整个密钥都被存储。 - finnw

Answer 1

如果你正在比较 HashMap 和 ArrayList，我推断你要对 ArrayList 进行某种搜索/索引，例如二分查找或自定义哈希表...? 因为通过线性搜索查询 6 百万项将是不可行的。

假设这样，我进行了一些实证测试，并得出结论："如果使用 ArrayList 结合二分查找或自定义哈希映射实现，则可以在相同的内存量中存储 2.5 倍小对象，而不是使用 HashMap"。我的测试基于仅包含 3 个字段的小对象，其中一个是键，键是整数。我使用了一个 32 位的 jdk 1.6。请参见下文，了解有关 "2.5" 数字的注意事项。

需要注意以下几点：

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

(b) 在我的经验中，通常需要将键作为值的一部分（例如，为了存储按客户 ID 索引的客户记录，您仍然希望客户 ID 作为 Customer 对象的一部分）。这意味着，我认为 HashMap 分别存储对键和值的引用有些浪费。

注意事项：

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

2. 在 -Xmx256M JVM 上，我得到了一个 2.8 的数字，将 8880502 个条目插入 ArrayList，与将 3148004 个条目插入 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);
    }
}

- Tim Cooper

---

嗨，蒂姆。在大多数情况下，键集是明确定义且有限的。我认为你可以通过添加一个键缓存来优化你的代码，以便清除键的对象创建。你觉得呢？ - Rafael Sanches

@Rafael Sanches：您能解释一下“添加键缓存以驱逐对象创建”的意思吗？ - Tim Cooper

Answer 2

最简单的方法是查看源代码并以此方式解决。然而，您真正比较的是苹果和橙子-列表和映射在概念上是非常不同的。很少会根据内存使用情况来选择它们之间的差异。

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

- Jon Skeet

---

我总是对ArrayList和HashMap的比较感到惊讶。我可以理解ArrayList和HashSet的比较，但Map甚至不属于集合(Collection)。 - Laurence Gonsalves

这个问题有点混淆，因为它在谈论Map和List之间的内存消耗... 但是这个问题可能源于elhoim正在使用一个非常大的列表，查找不尽人意（您可以使用LinkedHashMap来保留顺序，或多或少）。他们可能不希望由于转换为Map而使应用程序的占用空间急剧膨胀。 - Malaxeur

Map 严格来说是一个集合（但它不是一个 Collection）：http://java.sun.com/javase/6/docs/technotes/guides/collections/overview.html - TofuBeer

TofuBeer：请注意我使用的大写字母。 - Laurence Gonsalves

我不确定我在这里同意 - 我偶尔会想“我应该使用Map<Integer, X>而不是List<X>”，如果键稀疏且列表中会有很多空值，或者如果我需要以不可预测的顺序填充列表。 - finnw

Answer 3

存储在这两者中的都是指针。根据你的架构，指针应该是32位或64位（或更多或更少）。

10个元素的数组列表最少会分配10个“指针”（还有一些一次性开销）。

映射表必须分配两倍的空间（20个指针），因为它同时存储两个值。然后，在此基础上，它还必须存储“哈希”。在75％的负载下，哈希应该大于映射表，大约为13个32位值。

所以，如果您想要一个不经思考的答案，比率应该是1：3.25左右，但您只谈到了指针存储--除非您存储了大量对象，否则非常小--如果是这样，能够即时引用（HashMap）与迭代（数组）之间的效用应该比内存大小重要得多。

哦，还有：

数组可以适应您集合的确切大小。如果指定大小，哈希映射表也可以，但是如果超出该大小，则会重新分配较大的数组，并且不使用其中的一些空间，因此也可能会有一些浪费。

- Bill K

---

一张地图必须要分配两倍的空间（20个指针），因为它每次存储两个值，假设键和值是不同的。由于作者没有给我们太多细节，我们实际上不知道他希望存储什么数据。 - matt b

一个映射总是需要为键和值分配存储空间，即使它们相同（因此称为“映射”）。@ matt b，可能你想到的是 HashSet，它只分配单个数组，然后在对象内部执行映射操作，这种情况下比率大约为1:2.25。 - Bill K

关于我之前的评论的说明：实际上，HashSet是HashMap的子类实现，所以即使它从不使用映射的“值”部分，指针的存储仍然被创建，并且在要求上与HashMap相同。 - undefined

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个垃圾回收并从totalMemory()中减去。再次抱歉编辑您的帖子！

- sanscore

---

该方法：“返回Java虚拟机中的总内存量”，而不是当前应用程序使用的内存量或剩余内存。如果需要获取这些信息，您需要调用freeMemory()方法。 - amischiefr

@Bill：为了避免gc改变您的度量标准，您需要使用相同的初始/最大大小启动VM。如果您有对数据结构的引用（即，数据结构不可gc），则调用gc()x2没有任何效果。 - OscarRyz

@Oscar，gc()确实有所作为，因为ArrayList和HashMap在集合超出原始数组时必须重新分配数组。而旧数组可能不会立即释放。 - finnw

嗯，不能保证在调用gc()时虚拟机会进行完整的垃圾回收。这是不确定的。连续调用两次只会增加机会。我认为这很愚蠢。 - matt b

我的评论是基于假设除了那个测试之外还有更多其他操作--如果你没有收集任何东西，那么它可能可以在没有垃圾收集器的情况下工作，但除非你的分配导致垃圾收集器，否则会再次给出错误结果。总的来说，小心总比后悔好。是的，它的工作原理是通过对先前值和后续值进行差异化来实现的。 - Bill K

Answer 5

HashMap持有对值和键的引用。

ArrayList只持有对值的引用。

因此，假设键使用相同的内存作为值，则 HashMap 使用 50% 更多的内存（严格来说，并不是 HashMap 使用了那些内存，因为它只保留对其的引用）

另一方面，HashMap 提供基本操作（get 和 put）的常数时间性能。因此，尽管它可能使用更多内存，但使用 HashMap 比使用 ArrayList 快得多。

所以，你应该不关心谁使用更多内存，而是关注它们的适用场景。

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

编辑

在 Grant Welch 的回答之后，我决定测试 2,000,000 个整数。

这是源代码。

这是输出结果：

$
$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

- OscarRyz

---

这并不奇怪——列表中有2000000个元素，但映射表中只有65536个条目。你为什么要进行短强制转换？另外2000000相当大（使用默认堆设置会得到OutOfMemoryError）。最后，你省略了Grant建议的System.gc()调用。添加这些调用并将大小减小到20000，我得到了410,376字节的列表和912,680字节的映射表。 - finnw

这并不是一个好的测试。你是否意识到在打印堆大小时，列表或映射可能已经被垃圾回收了？因此会擦除你分配的任何对象。 - matt b

@finnw：我添加了gc调用并使用双倍的键。结果与您的类似。HashMap使用的内存比ArrayList多得多。 @matt b：它们没有被gc清除，因为它们是实例变量。我已经修改了代码，现在更加清晰（我在结尾处添加了一个println，让您看到对象仍然存在）。 - OscarRyz

这是如何在Java中更好地测量字节的方法 :) http://code.google.com/p/memory-measurer/ - Karussell

Answer 6

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

无论哪种情况，我建议在开始添加之前先确定预期数据的大小。这将给实现一个更好的初始设置，并且在两种情况下都可能消耗更少。

更新：

根据您的更新问题，请查看Glazed lists。这是由一些Google人编写的一个非常快速的类似于您描述的操作的小工具。允许聚类、过滤、搜索等操作。

- reccles

Answer 7

基本上，在使用中应该选择“正确的工具”。由于有不同的实例需要键/值对（可能使用 HashMap），而有些实例只需要一组值（可能使用 ArrayList），所以“哪个使用更多内存”的问题，在我看来是无关紧要的，因为这不是选择其中一个而不是另一个的考虑因素。

但是回答这个问题，由于 HashMap 存储键/值对，而 ArrayList 只存储值，我会假设仅添加键到 HashMap 中就意味着它占用更多内存，当然，我们比较它们时正在比较相同的值 类型（例如，两者的值都是字符串）。

- Avrom

Answer 8

我认为这里提出的问题不正确。

如果您想提高在包含六百万条目的List中搜索对象的速度，那么您应该研究这些数据类型检索操作的速度。

通常情况下，这些类的Javadocs很明确地说明了它们所提供的性能类型：

HashMap：

这种实现提供了基本操作（获取和放置）的恒定时间性能，假设散列函数将元素适当地分散在桶中。这意味着HashMap.get(key)的时间复杂度是O(1)。

ArrayList：

大小、isEmpty、get、set、iterator和listIterator操作的运行时间是恒定的。添加操作以平均恒定时间运行，也就是说，添加n个元素需要O(n)时间。所有其他操作都以线性时间运行（粗略地说）。

这意味着大多数 ArrayList 的操作都是 O(1)，但可能不包括您用于查找与特定值匹配的对象的操作。

如果您正在遍历 ArrayList 中的每个元素并测试相等性，或使用 contains()，那么这意味着您的操作运行时间为 O(n)（或更差）。

如果您不熟悉 O(1) 或 O(n) 符号，这是指操作需要多长时间。在这种情况下，如果您可以获得常量时间性能，您就要利用它。如果 HashMap.get() 是 O(1)，这意味着检索操作需要大致相同的时间，而不管 Map 中有多少条目。

像 ArrayList.contains() 这样的操作是 O(n)，这意味着它所需的时间随列表大小增加而增加；因此，在具有六百万条目的 ArrayList 上进行迭代将不会非常有效。

- matt b

---

对象检索操作很快，因为它们只是POJO。是的，我知道HashMap的获取是O(1)，这就是为什么我想使用它们，但我的问题仍然是关于HashMap使用多少比ArrayList更多的内存？ - elhoim

你的对象是POJO与遍历包含它们的列表的速度无关。 - matt b

Answer 9

我不知道确切的数字，但HashMap比较重。相比之下，ArrayList的内部表示是自证的，但HashMap保留了Entry对象，这可能会使您的内存消耗急剧增加。

它并不是很大，但确实比较大。一个很好的可视化方法是使用动态分析器，例如YourKit，它允许您查看所有堆分配。这非常不错。

- Malaxeur

Answer 10

这篇文章提供了关于Java中对象大小的大量信息。

- elhoim