Java HashMap Introduction

Java HashMap is the HashTable implementation of Map interface. It is a collection used to store data as key and value. It allow a single null in Key and any number of null values.

Java HashMap Anatomy

Buckets: It is the Entry array created to hold different key-value pairs. Internally it maintains a LinkList of Entry nodes for each key having same hash value.

Capacity: It is the number of buckets currently present in the Map instance.

DEFAULT_INITIAL_CAPACITY = 16

MAXIMUM_CAPACITY = 1073741824

Load Factor: It is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The default value is a float of .75F. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets. It is defined as:

DEFAULT_LOAD_FACTOR = 0.75

HashTable:It maps keys to values. Any non-null object can be used as a key or as a value. To successfully store and retrieve objects from a hash-table, the objects used as keys must implement the hashCode method and the equals method. The hash table is open: in the case of a “hash collision”, a single bucket stores multiple entries, which must be searched sequentially.

fail-fast: It means the Iterator over collection(Map in this case) fails as soon as it come to know that the collections is being updated by some other thread while current is still going through it. The update could be adding, removing or manipulating any value in the collection.

Iteration: The Map interface does not implement iterable so it could not be used to iterate over the elements, but the EntrySetinterface which is the subset of Map implements iterable so the elements could be iterated over by getting iterator on EntrySet of the Map.

Flow

Internal Storage Structure Explained:

HashMap consist of two following two datastructure:

  1. Array if Integer
  2. LinkList of Entry

The Array is initialized as:

Entry[]table = new Entry[i];

The Entry class is defined with following values:

Entry(inti, Object obj, Object obj1, Entry entry) {
        value = obj1;
        next = entry;
        key = obj;
        hash = i;
}

It maintains an array of type Entry named table for storing the key and value. When the request come to inflate table with a threshold value, the Map increase the capacity by rounding of the requested value to the power of 2 and create new Entry array with the new value.
For every key to be inserted in the Map, Map calculate the hash of the key in the following way:

Final int hash(Object obj)
    {
Int i = hashSeed;
if(0 != I && (obj instanceof String))
        {
return Hashing.stringHash32((String)obj);
        } else
        {
i ^= obj.hashCode();
i ^= i>>> 20 ^ i>>> 12;
returni ^ i>>> 7 ^ i>>> 4;
        }
    }

Map find the Entry table index for the object (Key) by the hash value returned. The hash returned is an integer in the range of Map’s capacity. For all the object (Keys) that returns the same hash, Map create an Entry object and put the key and value to the hash index of the table.
If at the hash index, the Entry table already consist of an Entry node for any previous key and value inserted in the Map, then a new node of Entry is created for new Key and Value, and linked to the Entry node already present in the Map table.

Example

Java HashMap Types

1. HashMap<K,V>
HashMap is the HashTableimplementation of Map interface.Unlike HashTable, it allows a null key. It does not maintain any order for the entries. A HashMap performance is based on two parameters: initial capacity and load factor. This implementation of HashTable is not synchronized and in case of multiple threads accessing the same Map, the Map must be synchronized externally.

2. ConcurrentHashMap<K,V>
ConcurrentHashMap is also a HashTable implementation that allow concurrent reads along with adjustable concurrency for updates. Read operation do not cause locking on the Map which could result in its overlapping with update operation. Read operation returns the most recent update. The update concurrency is maintained by concurrrencylevelconstructor argument with a default value of 16.The good design of concurrencyLevel is the number of threads that could possible try to update the table. Unlike HashMap it does not allow null.

3. Collections.synchronizedMap(Map<K,V> m):
It use a single monitor to synchronize all themethods. Locking the entire collection is a performance overhead. While one thread holds on to the lock, no other thread can use the collection.This means if multiple threads try to access synchronizedMap at same time, they will be allowed to get/put key-value pairs one at a time in synchronized manner.

Collections.synchronizedMap() returns the reference of internally created inner-class “SynchronizedMap”, which contains key-value pairs of input HashMap, passed as argument.This instance of inner class has nothing to do with original parameter HashMap instance and is completely independent.

4. WeakHashMap<K,V>:
It is used to have weak reference keys that would be easily collected by garbage collector. The presence of mapping for a given key does not prevent it from being garbage collected. The behavior of WeakHashMap depends on the action of garbage collector on it over a period of time. It could return size in decreasing order over the period of time. It could return false on isEmpty and then return true later on. Similarly true for containesKey for particular key and later false.

Each key in WeakHaspMap is stored as a referent of a weak reference. Thus it will be collected by garbage collector only after the weak references to it both inside as well as outside the Map.

5. ConcurrentSkipListMap<K,V>
It is an implementation of scalable concurrent ConcurrentNavigableMap. The map is sorted based on the natural ordering of keys or the comparator provided at the time of map creation.This class implements a concurrent variant of SkipLists(a skip list is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, each skipping over fewer elements.) providing expected average log(n) time cost for the containsKey, get, put and remove operations.

6. IdentityHashMap<K,V>
This HashMap implements HashTable using reference-equality instead of object-equality. In this, two keys k1 and k2 are considered equal if and only if (k1==k2). (In normal Map implementations (like HashMap) two keys k1 and k2 are considered equal if and only if (k1.equals(k2).)

7. SortedMap<K,V>
It provides the ordering on the keys. The map is ordered according to natural ordering of the keys or the comparator provided at time of creation.

8. NavigableMap<K,V>
It implements the SortedMap along with the navigation methods returning the closest match for the searched targets. Methods lowerEntry, floorEntry, ceilingEntry, and higherEntry return Map.Entry objects associated with keys respectively less than, less than or equal, greater than or equal, and greater than a given key, returning null if there is no such key. Similarly, methods lowerKey, floorKey, ceilingKey, and higherKey return only the associated keys. All of these methods are designed for locating, not traversing entries.

This interface additionally defines methods firstEntry, pollFirstEntry, lastEntry, and pollLastEntry that return and/or remove the least and greatest mappings, if any exist, else returning null.

Reference: Map

Share this:

8 thoughts on “Java HashMap

  1. Hello this is a fantastic article. I’m going to email this to my friends. I stumbled on this while browsing on bing I’ll be sure to come back. thanks for sharing.

  2. I’ve also been wondering about the similar point. Delighted to see someone on the same wavelength! Nice article.

  3. I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! keep up the good work.

  4. Congratulations for posting such a useful blog. Your blog isn’t only informative but also extremely artistic too. There usually are extremely couple of individuals who can write not so easy articles that creatively. Keep up the good writing !!

  5. Your blogs always have got a decent amount of really up to date info. Where do you come up with this? Just declaring you are very innovative. Thanks again

  6. I simply want to mention I am just new to blogs and honestly liked your web-site. Probably I’m planning to bookmark your blog . You absolutely come with fabulous stories. Cheers for sharing with us your webpage.

  7. ブランドコピー時計(N級品)激安通販専門店
    世界一流のブランドコピーブランド時計の卸売と小売を行っております。
    業界でも高い知名度と好評度を持っております。
    弊社は進んでいる生産設備成熟な技術と研究部門を持っており、コピー時計のパーツは直接にメーカーから買い、それを組み合わせます。
    主な取り扱いブランド:ロレックス時計コピー,パネライ時計コピー,ウブロ時計コピー,ブライトリング時計コピー,IWC時計コピー,
    フランクミュラー時計コピー,カルティエ時計コピー,ベル&ロス時計コピー,オメガ時計コピー,ショパール時計コピー,コルム時計コピー,
    パテックフィリップ時計コピー,ヴァシュロンコンスタンタン時計コピー,オーデマピゲ時計コピー,ブルカリ時計コピー品を扱っております。
    他にも各種ブランドのブランドコピー品多数、取り扱っております。
    以上 宜しくお願い致します。(^0^)
    広大な客を歓迎して買います!── (*^-^*)
    ■ホームページ上でのご注文は24時間受け付けております
    その他の世界一流スーパーコピー https://www.watchergz.com/wallet/product-22016.html

Leave a Reply

Your email address will not be published. Required fields are marked *