Lists, Maps and hashCode

List’s are better suited when iterative operations are to be performed on your objects (use Iterators for this):

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
Class object = iterator.next();
// do something
}

Map’s are better suited when search operations are to be performed on your objects, as Maps are (Key, Value) associative arrays:

map.get(key);

However, in order to make the Map’s search/fetch operations really efficient one must implement / override the int hashCode() method of Java Object’s, as Java uses this method to perform search / operations in Maps (see HashMaps, HashTables, …).

int hashCode(), what and how?
One might wander what is this method that, for Classes with several int‘s, String‘s, Object‘s, …etc attributes, returns a single int! If so, different Objects might have the same hashCode!

The answer is YES! Different objects might have the same hashCode. Even more, if your int hashCode() returns a different and unique hashCode for each different Object, you’re doing wrong and your code is not efficient at all! However, the hashCode must be the same if two objects are equal from the application point of view. This is why we generally advice people to override the boolean equals() method each time the int hashCode() is implemented.

The illustration is quite simple: as (Key, Value) pairs are added to the Map, Java will save a reference of the (Key, Value) pair in a (a bi-dimensional) table where the row index is determined by Key’s hashCode. So (Key, Value) of equal Key’s hashCode will find themselves on the same row and thus (Key, Value) pairs are grouped into subgroups (subgroups are the rows of the table) and searching / fetching a Value within a Map by it’s Key is reduced to a search on the row index containing the corresponding pair.

You understand now (I hope) why Key objects returning a unique hashCode value for each Object is not efficient since it will create a table with as many rows as Keys’s references … In the opposite way, returning the same hashCode for all objects will create a single row for all (Key, Value) pairs.

All the staff is to write a int hashCode() method that wisely spreads and divides your (Key, Value) pairs into subgroups of equal but not huge capacity (what do I define by huge? Only god knows!) … think of using “modulo” in computing your hashCode It surely will be of great help!

Hope this might help!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s