Pages

July 30, 2024

Why Mita Vashisht’s Goodbye to Irrfan Khan Deserves Empathy, Not Criticism


Mita Vashisht recently shared how she tried to say a final goodbye to her friend Irrfan Khan at the cemetery. 

She said, "They didn’t let me in because women weren’t allowed inside. I stood outside near the barricade. Later, when they finally brought his remains, I was able to say my final goodbye. But then, unexpectedly, they came back and walked past me. The procession was so close to me that I laughed and said to myself, 'See, you came to say goodbye to me.'"

July 07, 2024

#Collections: Part 4- A Guide to HashTable in Java

 

What is a Hashtable?

Java Hashtable class implements Map, which maps keys to values.  It operates on the concept of Hashing, where each key is converted by a hash function into a distinct index in an array. The index functions as a storage location for the matching value. Here is the declaration for java.util.Hashtable class.

public class Hashtable < K,V > extends Dictionary implements Map < K,V >, Cloneable, Serializable

where, K is the type of keys maintained by this map and V is the type of mapped values.

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..

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


What is Hash Map in Java?

In Java, a HashMap is a data structure that implements the Map interface and stores key-value pairs. It allows you to store and retrieve elements based on keys rather than indexes.

HashMap allows a single null key and multiple null values. This means one key can be null, but duplicate keys are not permitted, as keys must be unique.

HashMap maintains performance even with an increasing number of elements by automatically resizing itself when the number of elements exceeds a certain threshold (the load factor). This ensures effective memory utilization.

The sequence in which entries in a hash map are iterated is not fixed and can vary over time, particularly if the structure is altered by adding or deleting members. If order is important, consider using LinkedHashMap or TreeMap.

#Collections: Part 1- A Guide to Map in Java

What is a Map in Java?

In Java, a Map is an interface that represents a collection of key-value pairs where each key is unique within the Map, and it maps to exactly one value. It is part of the Java Collections Framework and provides methods to manipulate and retrieve data based on the keys.

July 05, 2024

#Collections: A Guide to Spliterator in Java

What is a Spliterator?

  • A Spliterator is an iterator-like object that can traverse and partition sequences of elements. It combines the functionalities of an Iterator and a Splitter, allowing efficient parallel traversal and decomposition of elements from a source. It supports both sequential and parallel processing of data structures.
  • A Spliterator can traverse and split the underlying data source into multiple parts for concurrent processing. This makes it suitable for parallel computation.
  • Unlike traditional Iterators, Spliterators can partition off some of their elements, which can be processed in parallel by different threads. This feature enhances performance for large data sets.
  • Spliterators are designed to be stateless and immutable. This ensures that they can safely be used concurrently by multiple threads without interference.
  • Spliterators can be either ordered or unordered. Ordered spliterators maintain a specific order of elements (e.g., in a list or array), while unordered spliterators do not guarantee any specific order (e.g., in a set or hash map).

#Collections: A Guide to Iterator in Java



What is an Iterator?

Iterator is an interface, which is found in java.util package. It provides a way to access elements of a collection sequentially without exposing its underlying implementation. 

The iterator allows the traversal of elements and supports removing elements during iteration. The Iterator interface has three main methods:
  • boolean hasNext(): Returns true if there are more elements in the collection.
  • E next(): Returns the next element in the collection.
  • void remove(): Removes the last element returned by next() from the collection (optional operation).