Java

Java Collection Framework

The Java Collection Framework is a set of Classes and Interfaces that provides implementation of some useful data structures and algorithms to work on a collection of data. 

[Java Doc]
A collections framework is a unified architecture for representing and manipulating collections. All collections frameworks contain the following:

• Interfaces: These are abstract data types that represent collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages, interfaces generally form a hierarchy.
• Implementations: These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.
• Algorithms: These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces. The algorithms are said to be polymorphic: that is, the same method can be used on many different implementations of the appropriate collection interface. In essence, algorithms are reusable functionality.

The Java Collection Framework encapsulates four important collection data structures as Maps, Sets, Lists and Queues.

Java Collection Interfaces

Maps

A map is a collection of data in which values are mapped to keys. We will discuss the implementation level details of all the maps and see in detail, how is this achieved.
There are four implementations of Map

• HashMap
• Hashtable,
• TreeMap
• LinkedHashMap

HashMap

HashMap is a hash table based implementation of Map interface.

Implementation of HashMap

• HashMap is an array of Entry objects.
• Entry used in the HashMap is a Class that implements Map.Entry.

To understand the internal implementation of HashMap, you must understand two things :

1. What is Entry ?
2. What is Hashing and how it is used ?

What is Entry ? 

        static class Entry<K,V> implements Map.Entry<K,V> 

       {

                final K key;

               V value;

               Entry<K,V> next;

               final int hash;

              .......

              .......

              .......

        }

This is the how the Entry Class for HashMap is written. Each entry objects holds information about the key, the value, the hash and a reference to the next Entry object. Because the Entry Class has next filed, an Entry object can be used to build a LinkedList by assigning the reference of another Entry object to the next field of the previous Entry object.

What is hashing and how is it used ?