Map

What is a Map?

A map is defined as the name of a higher-order function in most of the programming languages that applies a given function to each element of a functor, such as a list, and returns a list of results in the same order. A map is also called the collection of values based on a key, i.e. a key and value pair. A map has its own set of keys. Duplicate keys are not permitted in the Map, although duplicate values are permitted. Because a Map cannot be navigated, it must be converted to a Set using the keySet() or entrySet() methods. For key-value association mapping, such as dictionaries, maps are ideal.

Java Map Hierarchy

The map is implemented in Java using two interfaces: Map and SortedMap, as well as three classes: HashMap, LinkedHashMap, and TreeMap. The Null keys and values are allowed in HashMap and LinkedHashMap, however, they are not allowed in TreeMap. HashMap is a Map implementation that does not keep track of the order.

Hashmap Interface

The java.util package contains the HashMap class. It stores data as (Key, Value) pairs, which may be accessed using an index of a different type, such as an Integer. The map interface is implemented by the hashmap class in java. This allows storing the pairs of value and key, however, the key needs to be unique. The package java.util has the hashmap class. Hashmap performs delete, update, and other operations by using a key index. Abstract map class is extended by hashmap class and implements the interface of Map. When a user tries to input a duplicate key, the element of the matching key is replaced.

Syntax

public class HashMap<K,V> extends abstractMap<K,V> implements Map<V,K>, Cloneable, Serializable

Parameters in hashmap class

Following are the two parameters of the HashMap class

V: Kind of the mapped value.
K: Key types maintained by map.

Hashmap constructors

There are four different types of constructors that are used in hashmap and they have public as their access modifier. The constructors are listed below.

HashMap(): Constructs a default hash map. It is used for generating a HashMap instance with a capacity of 16 and the corresponding load factor of 0.75.
HashMap(int initial_capacity): Hash map’s capacity is initialized with an integer value. It then generates a HashMap object with the specification of 0.75 load factor and the given starting capacity.
HashMap(int initial_capacity, float load_factor): Hash map’s capacity and load factor are initialized by passing it as an argument. It then generates a HashMap object with the passed value of initial capacity and the load factor given.
HashMap(Map map): The hash map is initialized with the provided map element. It then produces the instance of HashMap with the same mappings as the given map.

Structure of hashmap

Hashmap has an array of nodes and the nodes are represented as classes with four fields which are,

Int hash
V values
K key
Node next

Nodes have a reference with their object and they are also known as a linked list.

Operations in Hashmap

Following are the general operations that are performed on HashMap

Add: The put() function is used to add a new item or element to the map. The order of insertion is not preserved, and each element creates its own hash, which is used to calculate the index of the elements.
Change: The item/element can be altered by re-inserting it into the map. As the map elements are indexed, the key value will be updated by adding the new value.
Remove: The components are removed using the delete() function. The key value is used to delete the mapping for the key.
Search: To search across the structure of the framework collections, an interface called iterator is utilized, and the iterator will only function on one data type. The hash map items are shown using the function next().

Hashmap Methods

void clear(): It's used to remove all the mappings of the current map.
Object clone(): It is generally used to return the shallow copy of the corresponding HashMap instance, with no point of cloning of the keys and values.
Set keySet(): Its most common purpose is to return the complete set view of the keys that are present in the given map.
void putAll(Map map): It's used to insert a particular map into another map.

Applications of Hashmap

Priority queues: A priority queue is defined as an abstract data type with the priority value that is given to each piece. A priority queue's items are said to be only partially sorted, with the parent node being more important as compared to both of its child nodes.
Dijkstra's Algorithm: The nodes are partitioned in three different sets that are settled set S, frontier set F and far-off set. In every iteration of the Dijkstra's method, the involved user inserts the node in the frontier set F with the available shortest distance to the source node to the settled set and, if required, updates the distance and then backpointer of the nearby nodes.
Topological Sort: If a node is part of a cycle in the topological sort, it must have an edge leading to it. The user then continues to remove the vertices that have the indegree zero and then erase all of their outgoing edges until no node remains, implying that the indegree of surrounding nodes then must be modified in every iteration.

Advantages

A key value pair can be inserted into the HashMap.
HashMap is a fast iterator that never fails.
It is non-synced, which implies it can't be shared between many threads unless it's properly synchronized.
Hashing technique allows for faster access to components.

Disadvantages

When two separate keys give the same hashCode() value, the performance of the hashMap degrades.
When the original size of the HashMap buckets is full, HashMap may require resizing.
Because of the reason that the items from the old HashMap are moved to a new larger HashMap, resizing requires O(n) time.
Hashmap is not thread-safe.

Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for,

Bachelor's in Computer Science Engineering
Associate of Science in Computer Science.