Pages

July 06, 2024

#Collections: Part 3- A Guide to HashMap in Java

 

How null key is handled in HashMap? Since equals() and hashCode() are used to store and retrieve values, how does it work in the case of the null key?

In the Java HashMap when the key is null the hashcode() method is not called. Null keys always map to hash 0 and are put inside the bucket 0.

Here is the implementation of the hash method of HashMap:

static final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h > > > 16);
}

We can see for the null key the hashcode() method is not called, instead puts the key in bucket 0. HashMap uses a linked list to manage multiple objects in the bucket. And if there are already objects in bucket 0, the null object will be appended to the linkedlist of bucket 0.

When we call the get() method, it will call getNode(), which internally calls a hash() method to get the bucket number. Since the key is null, it will return 0. 

How remove() method in HashMap work internally in Java?

To understand how the remove method of HashMap works, we first need to understand the Entry object. FYI, till Java 7, Entry was used after Java 8 it was replaced with Node.

Map.Entry is the static nested class that stores the key/value pair that forms one element of HashMap. Entry object stores in the bucket in the following way (hash,key,value,bucketindex).

That means we need hashvalue and bucketindex besides the key to get access to the desired Entry object in HashMap.

remove(key) method calls the removeEntryForKey(key) method internally, which calculates the final hashValue of the key object and then uses that hashValue in the indexFor(int) method to find the first entry object in the appropriate bucket.

Since bucket(table) is a LinkedList effectively, we start traversing from the first entry object which we got by using the indexFor(int,int) method in the bucket. For each entry object in the bucket, we compare whether hashValue and the key are equal to the calculated hashValue in the first step and the key passed as a parameter in the remove(key) method.

If desired Entry object is found, then we removed that single entry object from the LinkedList. Removing a single Entry object from the LinkedList is implemented just like removing a single object from the LinkedList.

HashMap implementation of the remove(key) method in Java APIs that is rt.jar till Java 7:

In Java 8, the remove method calls removeNode.

Why String is a popular HashMap key in Java?

Since String is immutable, its hashcode is cached at the time of creation and it doesn’t need to be calculated again. This makes it a great candidate for keys in a Map and its processing is faster than other HashMap key objects. This is why String is mostly used Object as HashMap keys.

What is the load factor of a HashMap and how does it affect performance?

In Java's HashMap implementation, the load factor is a measure that determines when the underlying hash table should be resized to accommodate more elements. It is a floating-point value (from 0 to 1) that represents the ratio of the number of elements in the hash table (size) to the number of buckets (capacity or threshold).

The load factor is defined as size/capacity. When the load factor threshold is exceeded, the HashMap increases the capacity of the hash table by roughly doubling the number of buckets (this is done to maintain the efficiency of the hash table operations). Existing entries are redistributed (rehashed) into the new larger table, which involves recalculating hash codes and reassigning entries to new buckets.

The default load factor in Java is 0.75 (75% of the capacity). This means that when the number of elements in the map reaches 75% of the total capacity, the map will resize itself to double the capacity (by default).

A higher load factor means that the hash map can hold more elements before resizing, which reduces memory overhead but increases the likelihood of collisions (different keys hashing to the same bucket). A lower load factor means the hash table will resize more often, consuming more memory but potentially reducing collisions and improving lookup times.

The load factor can be specified when creating a HashMap by using the constructor that allows you to set both the initial capacity and the load factor. e.g, HashMap(int initialCapacity, float loadFactor)

How can you iterate over a HashMap?


What will be the output of the below program?

HashMap < ArrayList , String> al = new HashMap < ArrayList ,, String>();
ArrayList l1=new ArrayList();
ArrayList l2=new ArrayList();
al.put(l1,  "l1");
al.put(l2,  "l2");
System.out.println("Size="+al.size());

Output will be "Size=1", because l1.equals(l2) will return true. But suppose you add an element in l1 or l2 then the output might or might not be 1 depending on the reference of String added in the l1 and l2.

-K Himaanshu Shuklaa..

No comments:

Post a Comment