Hashmap internal implementation
===

HashMap
-------


<img src="http://s16.postimage.org/vnkgehglh/Hash_Map3.jpg">

***HashMap is an array of Entry objects.***
 
Consider HashMap as just an array of objects.

Have a look what this Object is:

    static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;
            final int hash;
    ... 
    }

Each Entry object represents key-value pair. Field `next` refers to other `Entry` object if a bucket has more than 1 Entry. 

Sometimes it might happen that hashCodes for 2 different objects are the same. In this case 2 objects will be saved in one bucket and will be presented as LinkedList. 
The entry point is more recently added object. This object refers to other objest with `next` field and so one. Last entry refers to null.

When you create HashMap with default constructor

    HashMap hashMap = new HashMap();

Array is gets created with size 16 and default 0.75 load balance.

**Adding a new key-value pair**

1. Calculate hashcode for the key
2. Calculate position 
`hash % (arrayLength-1))` 
where element should be placed(bucket number)

3. If you try to add a value with a key which has already been saved in HashMap, then 
value gets overwritten.
4. Otherwise element is added to the bucket.
If bucket has already at least one element - a new one is gets added and placed in the first position in the bucket. Its `next` field refers to the old element.

**Deletion:**

1. Calculate hashcode for the given key
2. Calculate bucket number (hash % (arrayLength-1))
3. Get a reference to the first Entry object in the bucket and by means of equals method iterate over all entries in the given bucket. Eventually we will find correct Entry.
If desired element is not found - return `null` 
 