Guy Wiener

When I try to remember the Data Structures course I did some years ago, I recall vaguely that:

1. Linked lists should take less memory then array-based lists
2. Hash tables should take more memory then tree-based maps

I actually put these believes to the test today. I profiled a small Java program that added 100,000 elements to these collections. The results were surprising:

1. Unless you delete a lot of elements, linked lists take twice more memory then array lists
2. If you have a good hash functions, hash tables consume only a small amount of memory more then tree maps

The explanation, in both cases is as follows: Array lists and hash tables are supposed to consume more memory then their array-based counterparts because the array-based implementations must keep an array that is larger then the exact capacity, while the size of node-based collections is concise. However, since the size of a reference is the same as of an array cell, the math is different: Array-based collections keep an array that is 1.5 larger then needed, so their size is 1.5N. Each node in a linked list or a tree map must keep a couple of references at least, so their size is 2N or 3N.

This is true in the case of reference-based languages, such as Java et al. The exception is for value-based languages, such as C++, for collections of concrete elements instead of pointers. In this case, the size of an empty array cell is the same as of a stored element, so the array wastes more memory.

Conclusions:

1. In Java, if you have a collection and you do not add and remove elements frequently, use an array-based implementation rather then a node-based one
2. Validate your assumptions! As the great sensei Steven Segal once said, “Assumption is the mother of all fuck-ups”

Nothing quite says “long international flight” like looking at your watch and wandering if it is 9:00 AM or 9:00 PM. I’m back home now, somewhat jet-legged, but fine. I can coop with that. I accepted coffee as a part of my metabolism a long time ago.

The peak of our west-coast tour was going to the Yosemite park. I mean “peak” literally, because we did the 4-miles trail: A steep climb to Glacier Point. The view was amazing (pictures to come soon), and after some rest I can use my legs again.

One the down side, is was cold in Yosemite. It was about 8°C by day and -5°C by night. We, Mediterranean guys, are not really used to these temperatures. We were so cold that we considered leaving the food out on purpose and cuddle with the bears when they come to get it (Note to self: Reading the temperature in Fahrenheit doesn’t make it warmer). It was supposed to be warmer, but “climate is what you expect, weather is what you get”.

So, if you’re planning to go to Yosemite, remember that faith and an arctic sleeping-bag will keep you warmer then just faith. We had to learn it the hard way.

I haven’t updated my site for a while because Hagit and I are travelling in the USA. We’re visiting family on the east coast (D.C and Philadelphia) and west coast (San-Fransisco). We’ve just finished our east coast tour and came to see the west.

Visiting America this way is great - When you have someone local to show you around. It’s a reminder that the U.S is not “as seen on t.v”. For one thing, we found out that outside of the White House - Capitol - Pentagon triangle, Washington D.C is more-or-less a village. It has rustic-like houses and neighbourhood coffee shops. The east coast, on the other hand, is another story: Even the small places, like Berkeley or Oakland, are actually rather big. Everything is big. The roads are huge. Even if you bind together all the highways in Israel, you still won’t get that highway monstrosity that covers the bay area and silicon valley.

So more to come when I’ll get back home. I have to go over some SOA material from IBM, which will probably result in some more ratings.