blocks|key|1054222|text|最简单的方法是查看源代码，并以这种方式计算出来。然而，你真的在比较苹果和橘子--列表和地图在概念上是非常不同的。您很少会根据内存的使用情况在它们之间进行选择。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1054223|这个问题背后的背景是什么？|1054224|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

The simplest thing would be to look at the source and work it out that way. However, you're really comparing apples and oranges - lists and maps are conceptually quite distinct. It's rare that you would choose between them on the basis of memory usage.

What's the background behind this question?

blocks|key|1056900|text|我不知道确切的数字，但HashMaps要重得多。与这两者相比，ArrayList的内部表示是不言自明的，但是HashMaps保留了条目对象(+Entry+)，这些条目可能会增加您的内存消耗。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1056901|它不是那么大，但它更大。可视化这一点的一个好方法是使用动态分析器(如YourKit+)，它允许您查看所有堆分配。挺不错的。|offset|length|1056902|entityMap|0|LINK|mutability|MUTABLE|url|http://www.yourkit.com/^0|0|Y|7|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

I don't know the exact number, but HashMaps are much heavier. Comparing the two, ArrayList's internal representation is self evident, but HashMaps retain Entry objects (Entry) which can balloon your memory consumption.

It's not that much larger, but it's larger. A great way to visualize this would be with a dynamic profiler such as <a href="http://www.yourkit.com/" rel="nofollow noreferrer">YourKit</a> which allows you to see all heap allocations. It's pretty nice.

blocks|key|1056904|text|正如乔恩·斯基特所指出的，这些都是完全不同的结构。映射(如HashMap)是从一个值到另一个值的映射--也就是说，在键->值类型的关系中，有一个映射到值的键。该键被散列，并放置在一个数组中，以便快速查找。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1056905|另一方面，List是带有order+-+ArrayList的元素集合，碰巧使用数组作为后端存储机制，但这是不相关的。每个索引元素都是列表中的单个元素。|1056906|编辑:根据您的评论，我添加了以下信息：|1056907|密钥存储在hashmap中。这是因为散列不能保证对任何两个不同的元素都是唯一的。因此，在哈希冲突的情况下，必须存储密钥。如果您只是想看看一个元素是否存在于一组元素中，那么使用一个集合(这个元素的标准实现是HashSet)。如果订单很重要，但您需要快速查找，请使用LinkedHashSet，因为它保留了插入元素的顺序。两者的查找时间都是O(1)，但在LinkedHashSet上插入时间稍微长一些。只有当您实际上是从一个值映射到另一个值时才使用Map+--如果您只是拥有一组唯一的对象，那么使用一个集合，如果您已经排序了对象，那么使用一个列表。|1056908|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

As Jon Skeet noted, these are completely different structures. A map (such as HashMap) is a mapping from one value to another - i.e. you have a key that maps to a value, in a Key->Value kind of relationship. The key is hashed, and is placed in an array for quick lookup.

A List, on the other hand, is a collection of elements with order - ArrayList happens to use an array as the back end storage mechanism, but that is irrelevant. Each indexed element is a single element in the list.

edit: based on your comment, I have added the following information:

The key is stored in a hashmap. This is because a hash is not guaranteed to be unique for any two different elements. Thus, the key has to be stored in the case of hashing collisions. If you simply want to see if an element exists in a set of elements, use a Set (the standard implementation of this being HashSet). If the order matters, but you need a quick lookup, use a LinkedHashSet, as it keeps the order the elements were inserted. The lookup time is O(1) on both, but the insertion time is slightly longer on a LinkedHashSet. Use a Map only if you are actually mapping from one value to another - if you simply have a set of unique objects, use a Set, if you have ordered objects, use a List.

blocks|key|2579437|text|hashmap试图保持一个加载因子(通常为75%25满)，您可以将hashmap看作一个稀疏填充的数组列表。在大小的直接比较中的问题是，地图的这个负载因子增长以满足数据的大小。另一方面，ArrayList通过加倍其内部数组大小来满足它的需要。对于相对较小的大小，它们是可比较的，但是，当您将越来越多的数据打包到映射中时，需要大量的空引用才能保持哈希性能。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2579438|在这两种情况下，我建议在开始添加之前先启动数据的预期大小。这将为实现提供一个更好的初始设置，并且在这两种情况下都可能消耗更少的资源。|2579439|更新：|offset|length|style|BOLD|2579440|基于您更新的问题，请查看釉表。这是一个整洁的小工具，由谷歌的一些人为做类似于你描述的操作而写的。它也非常快。允许聚类、过滤、搜索等。|2579441|entityMap|0|LINK|mutability|MUTABLE|url|http://publicobject.com/glazedlists/^0|0|0|0|3|0|C|2|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|V|8|@$F|W|G|X|H|I]]|9|@]|A|$]]|$1|J|3|K|5|6|7|Y|8|@]|9|@$F|Z|G|10|1|11]]|A|$]]|$1|L|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|M|$N|$5|O|P|Q|A|$R|S]]]]

Hashmaps try to maintain a load factor (usually 75% full), you can think of a hashmap as a sparsely filled array list. The problem in a straight up comparison in size is this load factor of the map grows to meet the size of the data. ArrayList on the other hand grows to meet it's need by doubling it's internal array size. For relatively small sizes they are comparable, however as you pack more and more data into the map it requires a lot of empty references in order to maintain the hash performance.

In either case I recommend priming the expected size of the data before you start adding. This will give the implementations a better initial setting and will likely consume less over all in both cases.

Update:

based on your updated problem check out <a href="http://publicobject.com/glazedlists/" rel="nofollow noreferrer">Glazed lists</a>. This is a neat little tool written by some of the Google people for doing operations similar to the one you describe. It's also very quick. Allows clustering, filtering, searching, etc.

blocks|key|1054353|text|我也没有答案给您，但是google快速搜索在Java中找到了一个可能有帮助的函数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1054354|Runtime.getRuntime().freeMemory()；|1054355|因此，我建议您使用相同的数据填充HashMap和ArrayList。记录空闲内存，删除第一个对象，记录内存，删除第二个对象，记录内存，计算差异，……利润！|1054356|您可能应该使用大量的数据来完成这一任务。从1000开始，然后是10000,100000,1000000。|1054357|编辑：更正了，多亏了阿米斯酋长。|offset|length|style|BOLD|1054358|编辑:很抱歉编辑了你的帖子，但是如果你要用它的话，这是非常重要的(这对评论来说有点大)。freeMemory不像你想象的那样工作。首先，垃圾回收会改变它的值。其次，当java分配更多的内存时，它的值会发生变化。仅仅使用freeMemory调用并不能提供有用的数据。|1054359|试试这个：|1054360|public+static+void+displayMemory()+{
++++Runtime+r=Runtime.getRuntime();
++++r.gc();
++++r.gc();+//+YES,+you+NEED+2!
++++System.out.println("Memory+Used="%2B(r.totalMemory()-r.freeMemory()));
}|code-block|syntax|javascript|1054361|或者您可以返回所使用的内存并存储它，然后将其与稍后的值进行比较。无论哪种方法，记住2+gcs并从totalMemory()中减去。|1054362|再次，很抱歉编辑你的帖子！|1054363|entityMap^0|0|0|0|0|0|3|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|13|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|14|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|15|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|16|8|@$J|17|K|18|L|M]]|9|@]|A|$]]|$1|N|3|O|5|6|7|19|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|1A|8|@]|9|@]|A|$]]|$1|R|3|S|5|T|7|1B|8|@]|9|@]|A|$U|V]]|$1|W|3|X|5|6|7|1C|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1D|8|@]|9|@]|A|$]]|$1|10|3|-4|5|6|7|1E|8|@]|9|@]|A|$]]]|11|$]]

I don't have an answer for you either, but a quick google search turned up a function in Java that might help.

Runtime.getRuntime().freeMemory();

So I propose that you populate a HashMap and an ArrayList with the same data. Record the free memory, delete the first object, record memory, delete the second object, record the memory, compute the differences,..., profit!!! 

You should probably do this with magnitudes of data. ie Start with 1000, then 10000, 100000, 1000000.

EDIT: Corrected, thanks to amischiefr.

EDIT:
Sorry for editing your post, but this is pretty important if you are going to use this (and It's a little much for a comment)
.
freeMemory does not work like you think it would. First, it's value is changed by garbage collection. Secondly, it's value is changed when java allocates more memory. Just using the freeMemory call alone doesn't provide useful data.

Try this:

<pre><code>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()));
}
</code></pre>

Or you can return the memory used and store it, then compare it to a later value. Either way, remember the 2 gcs and subtracting from totalMemory().

Again, sorry to edit your post!

blocks|key|1054430|text|HashMap保存对值的引用和对键的引用。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|1054431|ArrayList只保存对值的引用。|1054432|因此，假设键使用相同的值内存，HashMap使用50%25的内存(尽管严格来说，它不是使用该内存的HashMap，因为它只保留对该内存的引用)|1054433|另一方面，HashMap为基本操作(get和put)提供了恒定的时间性能，因此，尽管它可能使用更多的内存，但使用HashMap获得元素可能比使用ArrayList快得多。|1054434|因此，接下来您应该做的是，不关心谁使用更多的内存，但是它们对有什么好处。|1054435|为您的程序使用正确的数据结构可以节省更多的CPU/内存，而不是在下面实现库。|1054436|编辑|1054437|在格兰特·韦尔奇的回答之后，我决定测量200万个整数。|1054438|这是源代码|1054439|这是输出|1054440|$
$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|code-block|syntax|javascript|1054441|entityMap|0|LINK|mutability|MUTABLE|url|http://pastebin.im/177^0|0|7|0|0|9|0|0|0|D|B|0|0|0|2|0|0|2|3|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@$9|1B|A|1C|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1D|8|@$9|1E|A|1F|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|1G|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|1H|8|@]|D|@]|E|$]]|$1|L|3|M|5|6|7|1I|8|@$9|1J|A|1K|B|C]]|D|@]|E|$]]|$1|N|3|O|5|6|7|1L|8|@]|D|@]|E|$]]|$1|P|3|Q|5|6|7|1M|8|@$9|1N|A|1O|B|C]]|D|@]|E|$]]|$1|R|3|S|5|6|7|1P|8|@]|D|@]|E|$]]|$1|T|3|U|5|6|7|1Q|8|@]|D|@$9|1R|A|1S|1|1T]]|E|$]]|$1|V|3|W|5|6|7|1U|8|@]|D|@]|E|$]]|$1|X|3|Y|5|Z|7|1V|8|@]|D|@]|E|$10|11]]|$1|12|3|-4|5|6|7|1W|8|@]|D|@]|E|$]]]|13|$14|$5|15|16|17|E|$18|19]]]]

HashMap hold a reference to the value and a reference to the key.

ArrayList just hold a reference to the value.

So, assuming that the key uses the same memory of the value, HashMap uses 50% more memory ( although strictly speaking , is not the HashMap who uses that memory because it just keep a reference to it ) 

In the other hand HashMap provides constant-time performance for the basic operations (get and put) So, although it may use more memory, getting an element may be much faster using a HashMap than a ArrayList.

So, the next thing you should do is not to care about who uses more memory but what are they good for. 

Using the correct data structure for your program saves more CPU/memory than how the library is implemented underneath.

EDIT 

After Grant Welch answer I decided to measure for 2,000,000 integers.

Here's the <a href="http://pastebin.im/177" rel="nofollow noreferrer">source code</a>

This is the output 

<pre><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
</code></pre>

blocks|key|2579533|text|基本上，你应该使用“适合工作的工具”。因为在不同的实例中，您需要一个键/值对(您可以在其中使用HashMap)和不同的实例，您只需要一个值列表(您可以在其中使用一个ArrayList)，那么在我看来，“哪一个使用更多内存”的问题是没有意义的，因为它不是选择一个而不是另一个的考虑因素。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2579534|但是要回答这个问题，因为HashMap存储键/值对，而ArrayList只存储值，所以我假设将键单独添加到HashMap将占用更多的内存，当然，假设我们用相同的值类型对它们进行比较(例如，两者中的值都是String)。|BOLD|2579535|entityMap^0|1B|7|2A|9|0|C|7|R|9|29|2|0^^$0|@$1|2|3|4|5|6|7|K|8|@$9|L|A|M|B|C]|$9|N|A|O|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|P|8|@$9|Q|A|R|B|C]|$9|S|A|T|B|C]|$9|U|A|V|B|H]]|D|@]|E|$]]|$1|I|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|J|$]]

Basically, you should be using the "right tool for the job". Since there are different instances where you'll need a key/value pair (where you may use a <code>HashMap</code>) and different instances where you'll just need a list of values (where you may use a <code>ArrayList</code>) then the question of "which one uses more memory", in my opinion, is moot, since it is not a consideration of choosing one over the other.

But to answer the question, since <code>HashMap</code> stores key/value pairs while <code>ArrayList</code> stores just values, I would assume that the addition of keys alone to the HashMap would mean that it takes up more memory, assuming, of course, we are comparing them by the same value type (e.g. where the values in both are Strings).

blocks|key|2579554|text|如果考虑两个ArrayLists对一个哈希映射，它是不确定的；两者都是部分完整的数据结构。如果您要比较，则Vector可能更节省内存，因为它只分配它所使用的空间，而Hashtable分配更多的空间。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2579555|如果您需要一个键值对，并且不需要非常需要内存的工作，只需使用Hashmap即可。|2579556|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

If you're considering two ArrayLists vs one Hashmap, it's indeterminate; both are partially-full data structures. If you were comparing Vector vs Hashtable, Vector is probably more memory efficient, because it only allocates the space it uses, whereas Hashtables allocate more space.

If you need a key-value pair and aren't doing incredibly memory-hungry work, just use the Hashmap.

blocks|key|1054537|text|所有存储在这两者中的都是指针。取决于您的体系结构，指针应该是32位或64位(或或多或少)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1054538|10的数组列表倾向于至少分配10个“指针”(还有一些一次性开销)。|1054539|映射必须分配两倍于此的值(20个指针)，因为它一次存储两个值。更重要的是，它必须存储“哈希”。它应该比地图大，在75%25的加载下，它应该在13+32位值(散列)左右。|1054540|因此，如果你想要一个临时的答案，这个比率应该是1:3.25左右，但是你只是在说指针存储--除非你存储了大量的对象--如果是这样的话，能够立即引用(HashMap)和迭代(数组)的功能应该比内存大小重要得多。|1054541|哦，还有:数组可以与您的集合的确切大小相匹配。如果您指定大小，HashMaps也可以，但是如果它“增长”超过该大小，它将重新分配一个更大的数组，而不是使用其中的一些数组，因此也可能会有一些浪费。|1054542|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

All that is stored in either is pointers. Depending on your architecture a pointer should be 32 or 64 bits (or more or less)

An array list of 10 tends to allocate 10 "Pointers" at a minimum (and also some one-time overhead stuff).

A map has to allocate twice that (20 pointers) because it stores two values at a time. Then on top of that, it has to store the "Hash". which should be bigger than the map, at a loading of 75% it SHOULD be around 13 32-bit values (hashes).

so if you want an offhand answer, the ratio should be about 1:3.25 or so, but you are only talking pointer storage--very small unless you are storing a massive number of objects--and if so, the utility of being able to reference instantly (HashMap) vs iterate (array) should be MUCH more significant than the memory size.

Oh, also:
Arrays can be fit to the exact size of your collection. HashMaps can as well if you specify the size, but if it "Grows" beyond that size, it will re-allocate a larger array and not use some of it, so there can be a little waste there as well.

blocks|key|1058206|text|我想这是个错误的问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1058207|如果您想提高在包含600万个条目的List中搜索对象的速度，那么您应该查看这些数据类型的检索操作执行的速度。|offset|length|style|CODE|BOLD|1058208|与往常一样，这些类的Javadocs非常清楚地说明了它们提供的性能类型：|1058209|HashMap|1058210|这个实现为基本操作(get和put)提供了恒定的时间性能，假设哈希函数适当地将元素分散在桶中。|blockquote|1058211|这意味着HashMap.get(key)是O(1)。|1058212|ArrayList|1058213|大小、isEmpty、get、set、迭代器和listIterator操作在恒定时间内运行。add操作在摊销常数时间内运行，也就是说，添加n个元素需要O(n)时间。所有其他操作都以线性时间运行(粗略地说)。|1058214|这意味着ArrayList的大多数操作都是O(1)，但很可能不是用来查找与某个值匹配的对象的操作。|1058215|如果您正在遍历ArrayList中的每个元素并测试是否相等，或者使用contains()，那么这意味着您的操作在O(n)时运行(或者更糟)。|1058216|如果您不熟悉O(1)或O(n)表示法，这是指操作所需的时间。在这种情况下，如果您可以获得固定时间的性能，您想要它。如果HashMap.get()是O(1)，这意味着检索操作所需的时间大致相同，而不管地图中有多少条目。|1058217|像ArrayList.contains()这样的东西是O(n)，这意味着随着列表大小的增长，它所花费的时间也会增加；因此，通过一个有600万个条目的ArrayList迭代根本不会很有效。|1058218|entityMap|0|LINK|mutability|MUTABLE|url|http://java.sun.com/javase/6/docs/api/java/util/HashMap.html|1|http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html^0|0|H|4|11|H|0|0|10|0|0|7|0|7|0|0|0|1B|0|0|Q|L|4|0|0|9|0|9|1|0|0|2V|0|0|1D|4|9|L|4|0|0|1Y|7|9|Y|A|1K|4|0|0|30|6|4|B|4|1N|D|21|4|0|0|2L|1|K|R|4|22|9|0^^$0|@$1|2|3|4|5|6|7|1D|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1E|8|@$D|1F|E|1G|F|G]|$D|1H|E|1I|F|H]]|9|@]|A|$]]|$1|I|3|J|5|6|7|1J|8|@$D|1K|E|1L|F|H]]|9|@]|A|$]]|$1|K|3|L|5|6|7|1M|8|@$D|1N|E|1O|F|H]]|9|@$D|1P|E|1Q|1|1R]]|A|$]]|$1|M|3|N|5|O|7|1S|8|@$D|1T|E|1U|F|H]]|9|@]|A|$]]|$1|P|3|Q|5|6|7|1V|8|@$D|1W|E|1X|F|H]|$D|1Y|E|1Z|F|G]]|9|@]|A|$]]|$1|R|3|S|5|6|7|20|8|@$D|21|E|22|F|H]]|9|@$D|23|E|24|1|25]]|A|$]]|$1|T|3|U|5|O|7|26|8|@$D|27|E|28|F|H]]|9|@]|A|$]]|$1|V|3|W|5|6|7|29|8|@$D|2A|E|2B|F|H]|$D|2C|E|2D|F|G]|$D|2E|E|2F|F|G]]|9|@]|A|$]]|$1|X|3|Y|5|6|7|2G|8|@$D|2H|E|2I|F|H]|$D|2J|E|2K|F|G]|$D|2L|E|2M|F|G]|$D|2N|E|2O|F|G]]|9|@]|A|$]]|$1|Z|3|10|5|6|7|2P|8|@$D|2Q|E|2R|F|H]|$D|2S|E|2T|F|G]|$D|2U|E|2V|F|G]|$D|2W|E|2X|F|G]|$D|2Y|E|2Z|F|G]]|9|@]|A|$]]|$1|11|3|12|5|6|7|30|8|@$D|31|E|32|F|H]|$D|33|E|34|F|G]|$D|35|E|36|F|G]|$D|37|E|38|F|G]]|9|@]|A|$]]|$1|13|3|-4|5|6|7|39|8|@]|9|@]|A|$]]]|14|$15|$5|16|17|18|A|$19|1A]]|1B|$5|16|17|18|A|$19|1C]]]]

I think the wrong question is being asked here.

If you would like to improve the speed at which you can search for an object in a <code>List</code> containing six million entries, then you should look into how fast these datatype's retrieval operations perform.

As usual, the Javadocs for these classes state pretty plainly what type of performance they offer:

<a href="http://java.sun.com/javase/6/docs/api/java/util/HashMap.html" rel="nofollow noreferrer">HashMap</a>:

<blockquote>
 This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
</blockquote>

This means that HashMap.get(key) is <code>O(1)</code>.

<a href="http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html" rel="nofollow noreferrer">ArrayList</a>:

<blockquote>
 The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). 
</blockquote>

This means that most of <code>ArrayList</code>'s operations are <code>O(1)</code>, but likely not the ones that you would be using to find objects that match a certain value.

If you are iterating over every element in the <code>ArrayList</code> and testing for equality, or using <code>contains()</code>, then this means that your operation is running at <code>O(n)</code> time (or worse).

If you are unfamiliar with <code>O(1)</code> or <code>O(n)</code> notation, this is referring to how long an operation will take. In this case, if you can get constant-time performance, you want to take it. If <code>HashMap.get()</code> is <code>O(1)</code> this means that retrieval operations take roughly the same amount of time regardless of how many entries are in the Map. 

The fact that something like <code>ArrayList.contains()</code> is <code>O(n)</code> means that the amount of time it takes grows as the size of the list grows; so iterating thru an <code>ArrayList</code> with six million entries will not be very effective at all.

blocks|key|1058228|text|这个职位提供了大量关于Java中对象大小的信息。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1058229|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/258120/what-is-the-memory-consumption-of-an-object-in-java^0|0|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

<a href="https://stackoverflow.com/questions/258120/what-is-the-memory-consumption-of-an-object-in-java">This post</a> is giving a lot of information about objects sizes in Java.

blocks|key|2579708|text|如果您将HashMap与ArrayList进行比较，我猜想您正在对ArrayList进行某种类型的搜索/索引，例如二进制搜索或自定义哈希表.？因为一个.get(键)到600万个条目使用线性搜索是不可行的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2579709|使用这个假设，我做了一些经验测试，得出了这样的结论：“如果您使用ArrayList进行二进制搜索或自定义散列图实现，相对于HashMap，您可以在相同数量的内存中存储2.5倍的小对象”。我的测试是基于只包含3个字段的小对象，其中一个是键，键是一个整数。我使用了32位JDK1.6。关于"2.5“这一数字的注意事项见下文。|2579710|要注意的关键是：|2579711|(a)导致您死亡的不是引用或“负载因子”所需的空间，而是对象创建所需的开销。如果键是一个基本类型，或者是2个或更多的原始值或引用值的组合，那么每个键都需要自己的对象，其开销为8个字节。|2579712|(b)根据我的经验，你通常需要钥匙作为价值的一部分(例如，为了存储客户记录，按客户id索引，您仍然希望将客户id作为客户对象的一部分)。这意味着HashMap单独存储对键和值的引用有点浪费。|2579713|注意事项：|2579714|用于HashMap键的最常见类型是字符串。对象创建开销在这里不适用，因此差别会更小。|ordered-list-item|2579715|我得到了一个2.8个数字，即将8880502个条目插入到ArrayList中，而将3148004项插入到-Xmx256M+JVM上，但我的ArrayList负载因子是80%25，而我的对象非常小--+12字节加上8字节对象开销。|2579716|我的图形和实现都要求将键包含在值中，否则在对象创建开销方面也会出现同样的问题，这只是HashMap的另一个实现。|2579717|我的代码：|2579718|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%2B%2B)+{
++++++++++++++++int+key+=+(int)(Math.random()+*+Integer.MAX_VALUE);
++++++++++++++++map.put(key,+new+Payload(key));
++++++++++++}
++++++++}
++++++++catch+(OutOfMemoryError+e)+{
++++++++++++System.out.println("Got+up+to:+"+%2B+i);
++++++++}
++++}

++++@Test
++++public+void+useArrayList()
++++{
++++++++int+i=0;
++++++++try+{
++++++++++++ArrayListMap+map+=+new+ArrayListMap();
++++++++++++for+(i=0;+i+<+9000000;+i%2B%2B)+{
++++++++++++++++int+key+=+(int)(Math.random()+*+Integer.MAX_VALUE);
++++++++++++++++map.put(key,+new+Payload(key));
++++++++++++}
++++++++}
++++++++catch+(OutOfMemoryError+e)+{
++++++++++++System.out.println("Got+up+to:+"+%2B+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+%25+i+==+0)
++++++++++++++++return+false;
++++++++}
++++++++return+true;
++++}

++++ArrayListMap()
++++{
++++++++for+(int+i=0;+i+<+11000000;+i%2B%2B)++++//+this+is+clumsy,+I+admit
++++++++++++map.add(null);
++++++++int+n=31;
++++++++for+(int+i=0;+i+<+128;+i%2B%2B)+{
++++++++++++while+(!+isPrime(n))
++++++++++++++++n%2B=2;
++++++++++++primes[i]+=+n;
++++++++++++n+%2B=+2;
++++++++}
++++++++System.out.println("Capacity+=+"+%2B+map.size());
++++}

++++public+void+put(int+key,+Payload+value)
++++{
++++++++int+hash+=+key+%25+map.size();
++++++++int+hash2+=+primes[key+%25+primes.length];
++++++++if+(hash+<+0)
++++++++++++hash+%2B=+map.size();
++++++++do+{
++++++++++++if+(map.get(hash)+==+null)+{
++++++++++++++++map.set(hash,+value);
++++++++++++++++return;
++++++++++++}
++++++++++++hash+%2B=+hash2;
++++++++++++if+(hash+>=+map.size())
++++++++++++++++hash+-=+map.size();
++++++++}+while+(true);
++++}

++++public+Payload+get(int+key)
++++{
++++++++int+hash+=+key+%25+map.size();
++++++++int+hash2+=+primes[key+%25+primes.length];
++++++++if+(hash+<+0)
++++++++++++hash+%2B=+map.size();
++++++++do+{
++++++++++++Payload+payload+=+map.get(hash);
++++++++++++if+(payload+==+null)
++++++++++++++++return+null;
++++++++++++if+(payload.key+==+key)
++++++++++++++++return+payload;
++++++++++++hash+%2B=+hash2;
++++++++++++if+(hash+>=+map.size())
++++++++++++++++hash+-=+map.size();
++++++++}+while+(true);
++++}
}|code-block|syntax|javascript|2579719|entityMap^0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|11|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|12|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|13|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|14|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|15|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|16|8|@]|9|@]|A|$]]|$1|L|3|M|5|N|7|17|8|@]|9|@]|A|$]]|$1|O|3|P|5|N|7|18|8|@]|9|@]|A|$]]|$1|Q|3|R|5|N|7|19|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1A|8|@]|9|@]|A|$]]|$1|U|3|V|5|W|7|1B|8|@]|9|@]|A|$X|Y]]|$1|Z|3|-4|5|6|7|1C|8|@]|9|@]|A|$]]]|10|$]]

If you're comparing HashMap with ArrayList, I presume you're doing some sort of searching/indexing of the ArrayList, such as binary search or custom hash table...? Because a .get(key) thru 6 million entries would be infeasible using a linear search.

Using that assumption, I've done some empirical tests and come up with the conclusion that "You can store 2.5 times as many small objects in the same amount of RAM if you use ArrayList with binary search or custom hash map implementation, versus HashMap". My test was based on small objects containing only 3 fields, of which one is the key, and the key is an integer. I used a 32bit jdk 1.6. See below for caveats on this figure of "2.5".

The key things to note are:

(a) it's not the space required for references or "load factor" that kills you, but rather the overhead required for object creation. If the key is a primitive type, or a combination of 2 or more primitive or reference values, then each key will require its own object, which carries an overhead of 8 bytes.

(b) In my experience you usually need the key as part of the value, (e.g. to store customer records, indexed by customer id, you still want the customer id as part of the Customer object). This means it is IMO somewhat wasteful that a HashMap separately stores references to keys and values.

Caveats:

<ol>
<li>The most common type used for HashMap keys is String. The object creation overhead doesn't apply here so the difference would be less.</li>
<li>I got a figure of 2.8, being 8880502 entries inserted into the ArrayList compared with 3148004 into the HashMap on -Xmx256M JVM, but my ArrayList load factor was 80% and my objects were quite small - 12 bytes plus 8 byte object overhead.</li>
<li>My figure, and my implementation, requires that the key is contained within the value, otherwise I'd have the same problem with object creation overhead and it would be just another implementation of HashMap.</li>
</ol>

My code:

<pre><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&lt;Integer, Payload&gt; map = new HashMap&lt;Integer, Payload&gt;();
 for (i=0; i &lt; 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 &lt; 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&lt;Payload&gt; map = new ArrayList&lt;Payload&gt;();
 private int[] primes = new int[128];

 static boolean isPrime(int n)
 {
 for (int i=(int)Math.sqrt(n); i &gt;= 2; i--) {
 if (n % i == 0)
 return false;
 }
 return true;
 }

 ArrayListMap()
 {
 for (int i=0; i &lt; 11000000; i++) // this is clumsy, I admit
 map.add(null);
 int n=31;
 for (int i=0; i &lt; 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 &lt; 0)
 hash += map.size();
 do {
 if (map.get(hash) == null) {
 map.set(hash, value);
 return;
 }
 hash += hash2;
 if (hash &gt;= 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 &lt; 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 &gt;= map.size())
 hash -= map.size();
 } while (true);
 }
}
</code></pre>

blocks|key|1058299|text|这个站点列出了几种常用的数据结构(而不是一般的)的内存消耗。从这里可以看出，HashMap占用的空间大约是ArrayList的5倍。映射还将为每个条目分配一个额外的对象。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1058300|如果您需要一个可预测的迭代顺序并使用LinkedHashMap，那么内存消耗将更高。|1058301|您可以使用存储器测量器进行自己的内存测量。|1058302|然而，有两个重要的事实需要注意：|1058303|许多数据结构(包括ArrayList和HashMap)确实分配了比当前需要的空间更多的空间，因为否则它们将不得不频繁地执行代价高昂的调整大小操作。因此，每个元素的内存消耗取决于集合中有多少个元素。例如，具有默认设置的ArrayList对0到10个元素使用相同的内存。|ordered-list-item|1058304|正如其他人所说，地图的钥匙也是储存的。因此，如果它们不存在于内存中，那么您也将不得不添加这个内存成本。一个额外的对象通常只需要8个字节的开销，加上它的字段的内存，可能还需要一些填充。所以这也是一个很大的记忆。|1058305|entityMap|0|LINK|mutability|MUTABLE|url|https://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures|1|http://code.google.com/p/memory-measurer/^0|12|7|1H|9|2|2|0|0|I|D|0|5|6|1|0|0|9|9|J|7|30|9|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@$9|11|A|12|B|C]|$9|13|A|14|B|C]]|D|@$9|15|A|16|1|17]]|E|$]]|$1|F|3|G|5|6|7|18|8|@$9|19|A|1A|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|1B|8|@]|D|@$9|1C|A|1D|1|1E]]|E|$]]|$1|J|3|K|5|6|7|1F|8|@]|D|@]|E|$]]|$1|L|3|M|5|N|7|1G|8|@$9|1H|A|1I|B|C]|$9|1J|A|1K|B|C]|$9|1L|A|1M|B|C]]|D|@]|E|$]]|$1|O|3|P|5|N|7|1N|8|@]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|1O|8|@]|D|@]|E|$]]]|R|$S|$5|T|U|V|E|$W|X]]|Y|$5|T|U|V|E|$W|Z]]]]

This <a href="https://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures" rel="nofollow">site</a> lists the memory consumption for several commonly (and not so commonly) used data structures. From there one can see that the <code>HashMap</code> takes roughly 5 times the space of an <code>ArrayList</code>. The map will also allocate one additional object per entry.

If you need a predictable iteration order and use a <code>LinkedHashMap</code>, the memory consumption will be even higher.

You can do your own memory measurements with <a href="http://code.google.com/p/memory-measurer/" rel="nofollow">Memory Measurer</a>.

There are two important facts to note however:

<ol>
<li>A lot of data structures (including <code>ArrayList</code> and <code>HashMap</code>) do allocate space more space than they need currently, because otherwise they would have to frequently execute a costly resize operation. Thus the memory consumption per element depends on how many elements are in the collection. For example, an <code>ArrayList</code> with the default settings uses the same memory for 0 to 10 elements.</li>
<li>As others have said, the keys of the map are stored, too. So if they are not in memory anyway, you will have to add this memory cost, too. An additional object will usually take 8 bytes of overhead alone, plus the memory for its fields, and possibly some padding. So this will also be a lot of memory.</li>
</ol>

I am wondering what is the memory overhead of java HashMap compared to ArrayList?

Update:

I would like to improve the speed for searching for specific values of a big pack (6 Millions+) of identical objects.

Thus, I am thinking about using one or several HashMap instead of using ArrayList. But I am wondering what is the overhead of HashMap.

As far as i understand, the key is not stored, only the hash of the key, so it should be something like size of the hash of the object + one pointer.

But what hash function is used? Is it <a href="http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Object.html#hashCode()" rel="noreferrer">the one offered by Object</a> or another one?

Memory overhead of Java HashMap compared to ArrayList

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我想知道与HashMap相比，java ArrayList的内存开销是多少？更新：我想提高搜索一大包(6 Millions+)相同对象的特定值的速度。因此，我正在考虑使用一个或几个HashMap而不是使用ArrayList。但是我想知道HashMap的开销是多少。据我所知，键不是存储的，只有键的散列，所以它应该类似于对...

问Java HashMap与ArrayList的内存开销比较
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java HashMap与ArrayList的内存开销比较EN