memory usage compare hashmap, arraylist, and array

[Steve Jiang]

Hi,

I try to compare the memory usage between hashmap and arraylist using the following code.

I got the following result, the memory usage is monitored from Activity Monitor from Mac OS

NO list, and no Map : 10 M
No list and new HashMap: 10.1M
No Map , and creating new ArrayList: 13.9M
creating both Map and arraylist : 13.9M

Looks like hashmap doesn't use memory, but arrayList spend aroun 4M for 1M size list.

public class MemoryTest_HashMap {
	private static Map testMap = new HashMap(1000 * 1000);
//	private static List testList = new ArrayList(1000 * 1000);
	
	public static void main(String[] args) {

		System.out.println("Hello start");
		try {
			Thread.sleep(10 * 1000 );
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println("Hello end");
	}

}

Another tetst code to put the value , I git the different value as below

No map, list: 10M
only Map: 116M
only List : 35M
Both Map and list : 119 M

Array (with/without setting) : 14M

public class MemoryTest_HashMap {
//	private static Map<Integer, Integer> testMap = new HashMap<Integer, Integer>(1000 * 1000);
//	private static List testList = new ArrayList(1000 * 1000);
	
	public static void main(String[] args) {
		

		System.out.println("Hello start");
		
		Map testMap = new HashMap(1000 * 1000);
		for (int i =0; i < 1000 * 1000 ; i ++ ) {
			testMap.put(i,i);
		}
		
//		List testList = new ArrayList(1000 * 1000);
//		for (int i =0; i < 1000 * 1000 ; i ++ ) {
//			testList.add(i);
//		}
		

		int[] testArray = new int[1000 * 1000];
//		for (int i =0; i < 1000 * 1000; i++) {
//			testArray[i] = i;
//		}
//		
		
		try {
			Thread.sleep(10 * 1000 );
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println("Hello end");
	}

}

I was thinking when the hashMap and list were created , the memory will be allocated. and we should not be that much difference between setting the data or not. Looks like arrayList and hashMap doesn't allocate the memory even it was set the init capacity. but I hope to confirm if this is the right reason for the different memory usage.

Also I can see much difference between arraylIst and array. Is there more information to explain why ArrayList use more memory 35M than array 14M?

Thanks

[Campbell Ritchie]

And where in the code did you test the memory use?

[Steve Jiang]

the memory usage is monitored from Activity Monitor from Mac OS . Active Monitor will show how many memory is used for this Java process.

[Campbell Ritchie]

And how do you know how much is before an after creation of your List? Also is that on a 32‑bit machine or a 64‑bit machine?

[Steve Jiang]

I just comments out the code if that part is not for testing. test it with multiple combination. It is 64 bit machine. I don't need to get the exact memory usage for these data structire, but try to understand the reason for different structure.

Especially, why arraylist use more memory than array, also hashmap look like spend much more than the array with same capacity?

Thanks

[Campbell Ritchie]

Since an array list contains an array usually larger than the size of the list, and a hash map contains an array larger than the size of the list if you use the default load factor, I find those figures hard to believe.
On a 32‑bit machine an array will occupy 4 bytes for its length field, 4 bytes for each element (not longs or double which are 8 bytes each) (=400 bytes for new Foo[100]) whether the places are filled or not and a few dozen bytes to make it into an object, I would expect a 1000000‑element array and a 1000000‑element array list to be of the same order of magnitude. If you have a 75% load factor, then a 1000000‑capacity hash map would occupy at least twice that memory. So you are looking at 4MB, 4to6MB and 8+MB respectively.

A hash map doubles its capacity whenever the load factor is exceeded so a 1048576‑capacity (=2²⁰) hash map will double the size of its backing array when it contains more than 1048576 × 0.75 = 786432 elements, to 2097152 (=2²¹). And each of those elements occupies 4 bytes. That makes 8388608. Since each bucket contains the equivalent of a little linked list, the memory use for a hash map will be more than that.

[Steve Jiang]

Thanks, Campbell! The explanation is very make sense and similar as I thought.

also one more informaiton for the test, the jvm paramter is "-Xmx256m -Xms8m"

if I do nothing, and only print hello world, I can see the memory usage is around 10M

so if only tetsing creating 1M array, I get the memory usage arund 14M , which means the new array used additional 4M , which make sense, since int as 32 bit and 4 bytes, * 1M = 4M

//		int[] testArray = new int[1000 * 1000];
//		for (int i =0; i < 1000 * 1000; i++) {
//			testArray[i] = i;
//		}

For arrayList , as you described, I assume when I add the data less the 600K, (less than loading factor 0.75) it should be similar usage as array, around 4M , and when I insert 1M data, list will double the size , and it may use 8M for 2M int array.

insert 1M data for arraylist, the memory usage is 36M , which meeans the arraylist could use 36M -10M = 26 M
insert 0.5M data in arraylist, the memory usage is 24.6M (around 25M), which means 15M = 25M - 10M

	List testList = new ArrayList(1000 * 1000);
		for (int i =0; i < 500 * 1000 ; i ++ ) {
			testList.add(i);
		}

For hashmap, I did same thing for 1M data, and 0.5M


1M data in hashmap, the memory usage is 119M . it means double hashmap (for 2m) could use 119 - 10 = 109 M
0.5M data in hashmap , the memory usage is 72M, it means the hashmap could use 72M - 10 M = 62M

		Map testMap = new HashMap( 1000 * 1000 );
		for (int i =0; i < 500 * 1000 ; i ++ ) {
			testMap.put(i,i);
		}

Looks like the array usage is match what I think, but arraylist, and hashmap use more than I expected. Not sure if jvm also need to allocate other memory for the arraylist and hashmap memory?


Thanks

[Campbell Ritchie]

The load factor only applies to maps, not Lists.
I think ArrayList increases its capacity by about 50% when the array is full. Not certain, however.
A hash map usually doubles its capacity when the load factor is over 75%.

[Campbell Ritchie]

If you are adding 1000000 things to a List, the List will contain 1000000 references. But if each of those references may refer to an object somewhere else, and that object will occupy space. Are those objects in the List multiple copies of the same object, or different objects?

[Steve Jiang]

I add all int to list, and it converts int to Integer. From some link http://www.javaworld.com/article/2077496/testing-debugging/java-tip-130--do-you-know-your-data-size-.html , we see Inetger spends 16 bytes and int for 4 bytes. So if here are same capactivity for 1M, arraylist should be 16M and array could be 4M. It could explains most part for arraylist use more than array. Looks like they are still more than 4 times of array, maybe there are some other related stuff, but at least it is not different as expected so much.

Thanks

[Campbell Ritchie]

Steve Jiang wrote:. . . we see Inetger spends 16 bytes and int for 4 bytes. . . .

That conclusion is dubious for several reasons:-

1: It depends on the words size for your processor and endianness. A 32‑bit machine may have different memory use from a 64‑bit machine.

2: It is an implementation detail which may differ depending on which Java™ implementation they used: it may differ in Sun from Jikes or gcj.

3: The implementation details will probably have changed in the intervening 13 years.

You cannot make such assumptions about the amount of memory used for an object.

I still find an array list being 4× an array hard to believe. An int[], now, that does not contain references. The elements are the actual values. So you do not have 1000000 Integer objects anywhere. So you are not comparing like with like.