Java的HashMap的内存开销相比，ArrayList的 [英] Memory overhead of Java HashMap compared to ArrayList
问题描述
我想知道什么是Java的HashMap的内存开销相比，ArrayList的？
I am wondering what is the memory overhead of java HashMap compared to ArrayList?
更新：
我想提高速度为寻找一个大包的特定值（600万+）相同的对象。
I would like to improve the speed for searching for specific values of a big pack (6 Millions+) of identical objects.
因此，我想用一个或几个HashMap中，而不是使用ArrayList的。但我想知道是什么的HashMap的开销。
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 the one offered by Object or another one?
推荐答案
如果您正在使用ArrayList的比较HashMap的，我presume你正在做一些搜索的ArrayList的/索引，如二进制搜索或自定义的哈希表...？由于获得（键）至600万条目将使用线性搜索是不可行的。
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.
使用这一假设，我做了一些实证检验，并提出了这样的结论：你可以存储相同数量的RAM 2.5倍，许多小物件，如果您使用的二进制搜索或自定义哈希表实现的ArrayList，与HashMap的。我的试验是基于仅包含3个字段，其中一个是关键的小物件，和密钥是一个整数。我用了一个32位的JDK 1.6。请参阅下面的注意事项对这个人物的2.5。
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".
要注意的关键事情是：
（一）它不适合引用或杀死你客座率所需的空间，而是创建对象所需的开销。如果键是一基本类型，或者2个或更多的原始或参考值的组合，则每个键将需要其自己的目的，它携带的8个字节的开销。
(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.
（二）在我的经验，你通常需要的密钥值，部分（例如存储客户记录，按客户ID索引，你还是希望客户ID作为客户对象的一部分）。这意味着它是IMO有点浪费了一个HashMap分别存储到键和值的引用。
(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.
注意事项：
-
使用HashMap的键最常见的类型为String。对象创建开销在这里并不适用等方面差异会少些。
The most common type used for HashMap keys is String. The object creation overhead doesn't apply here so the difference would be less.
我得到了2.8的数字，被插入的ArrayList 8880502项与3148004插入-Xmx256M JVM HashMap的比较，但我的ArrayList的客座率为80％，我的对象是相当小 - 12字节加上8字节对象的开销。
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.
我的身影，我的实现，要求密钥包含值的范围内，否则，我必须和对象创建开销同样的问题，这将只是HashMap中的另一种实现方式。
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.
我的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<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);
}
}
这篇关于Java的HashMap的内存开销相比，ArrayList的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
