Win a copy of Head First Android this week in the Android forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Rob Spoor
  • Bear Bibeault
Saloon Keepers:
  • Jesse Silverman
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Al Hobbs
  • salvin francis

memory usage compare hashmap, arraylist, and array

 
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.





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





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

 
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And where in the code did you test the memory use?
 
Steve Jiang
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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



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




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




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
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
     
    You showed up just in time for the waffles! And this tiny ad:
    Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
    https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
    reply
      Bookmark Topic Watch Topic
    • New Topic