Which data structure uses more memory?

Question

Which type of data structure uses more memory?

• Hashtable
• Hashmap
• ArrayList

Could you please give me a brief explanation which one is less prone to memory leakage?

Answer 1

In most languages it depends on how good you are at picking up your toys after you're done with them.

In Java, it doesn't matter since garbage collection is done automatically and you don't really need to worry about memory leaks.

Answer 2

You're not comparing like with like: HashMap and Hashtable implement the Map interface, and ArrayList implements the List interface.

In a direct comparison between Hashtable and HashMap, HashMap will probably offer better performance because Hashtable is synchronized.

If you give some indication about what you're using the collections for, you might get a more insightful answer.

Answer 3

...which one to use for avoiding the memory leakage

The answer is all of them and none of them.

Memory leakage is not related to the data structure, but the way you use them.

The amount of memory used by each one is irrelevant when you aim to avoid "memory leakage".

The best thing you can do is: When you detect an object won't be used any longer in the application, you must remove it from the collection ( not only those you've listed, but any other you might use; List, Map, Set or even arrays ).

That way the garbage collector will be able to release the memory used by that object.

You can take a look at this article "How does garbage collector works" for further explanation on how Java release memory from the objects it uses.

Edit:

There are others data structures in Java which help for the references management such as WeakHashMap, but this may be considered as "advanced topics".

Answer 4

Most likely you should really just use a Collection that suits your current need. In the most common cases, if you need a List, use ArrayList, and if you need a Map, use HashMap. For a tutorial, see e.g. http://java.sun.com/docs/books/tutorial/collections/

When your profiler shows you there is an actual memory leak related to the use of Java Collections, then do something about it.

Answer 5

Your question is woefully underspecified because the concrete data structures you specify are not of comparable structure.

The HashMap/HashTable are comparable since they both function as maps (key -> value lookups). ArrayLists (and lists in general) do not.

The HashMap/HashTable part is easy to answer as they are largely identical (the major difference is null keys) but the former is not synchronized and the latter is, thus HashMap will generally be faster (assuming the synchronization is not required) Modern JVM's are reasonably fast at uncontended locks though so the difference will be small in a micro benchmark.

Answer 6

Hashtables (be it HashMap or HashTable) would take a little more memory than what they use to actually store the information.

Hashing performance comes at a price.

Answer 7

A java.util.Collection stores references to objects.

A java.util.Map stores references to Map.Entry instances, which hold references to keys and objects.

So a java.util.Collection holding N references to objects will require less memory than a java.util.Map holding onto the same N references, because the Map has to point to the keys as well.

Performance for reading and writing differs depending on the implementation of each of these interfaces.

I don't see any java.util.Collection analogous to WeakHashMap. I'd read about that class if you're worried about garbage collection and memory leaks.

Answer 8

Well, I've actually been, recently, in a situation where I had to hold onto large collections of custom objects, where the size of the collections was one of the applications limiting factors. If that's your situation, a few suggestions -

• there are a few implementations of collections using primitives (list here). Played around a bit with trove4j, and found a somewhat smaller memory footprint (as long as you're dealing with primitives, of course).
• If you're dealing with large collections, you'll probably get more bang for your buck, in terms of reducing memory footprint, by optimizing the objects you're holding. After all, you've got a lot more of them, otherwise you wouldn't need a collection, right?
• Some collections are naturally smaller (e.g. LinkedList will be a bit smaller than an ArrayList) but the difference will probably be swamped by the differences in how they're used)
• Most of the java collections can be manually sized - you can set your arraylist of 100 elements to be initialized to 100 elements, and you can set your maps to keep less open space at the cost of slower performance. All in the javadocs.

Ultimately the simplest thing to do is to test for yourself.

Answer 9

As others have pointed out, your question is underspecified.

Still, sometimes an ArrayList based implementation can replace a HashMap based implementation (I would not consider Hashtable at all, it's obsolete). You might need to search the ArrayList linearly but for small Lists that might still be fast enough and the ArrayList will need less memory (for the same data), because it has less overhead.