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

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

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

For loop or Foreach, which one is faster in Java?

When I was looking for a job in 2019, one of the questions I was asked was whether we should iterate through an ArrayList using a for or forEach?

The debate over the difference in preference between FOREACH and FOR isn't new. I was under the impression that FOREACH is faster. I eventually realized I was wrong.

#LeetCode: Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

#LeetCode: Find Numbers with Even Number of Digits

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:
Input: nums = [12,345,2,6,7896]
Output: 2
Explanation:

• 12 contains 2 digits (even number of digits). 
• 345 contains 3 digits (odd number of digits). 
• 2 contains 1 digit (odd number of digits). 
• 6 contains 1 digit (odd number of digits). 
• 7896 contains 4 digits (even number of digits). 
• Therefore only 12 and 7896 contain an even number of digits.

#Collections: Part 8(Time Complexity And Performance of Java Collections)

ALSO CHECK: Java Collections Interview Questions and Answers

ArrayList
The ArrayList in Java is backed by an array.

• add() takes O(1) time
• add(index, element) in average runs in O(n) time
• get() is always a constant time O(1) operation
• remove() runs in linear O(n) time. We have to iterate the entire array to find the element qualifying for removal
• indexOf() also runs in linear time. It iterates through the internal array and checking each element one by one. So the time complexity for this operation always requires O(n) time
• contains() implementation is based on indexOf(). So it will also run in O(n) time

#Collections: Part 7 (All about Exchanger in Java)

ALSO CHECK: Java Collections Interview Questions and Answers

java.util.concurrent.Exchanger < T > class in Java can be used to share objects between two threads of type T. It provides only a single overloaded method exchange(T t).

#Collections: Part 6 (All About SynchronousQueue in Java)

ALSO CHECK: Java Collections Interview Questions and Answers

SynchronousQueue from the java.util.concurrent package allows us to exchange information between threads in a thread-safe manner.

SynchronousQueue is a special kind of BlockingQueue in which each insert operation must wait for a corresponding remove operation by another thread and vice versa.

It has two supported operations: take() and put(), and both of them are blocking.

#Collections: Part 5 (Hashmap implementation in pre-Java 8 and Java 8)

ALSO CHECK: Java Collections Interview Questions and Answers

What is the difference in Hashmap implementation in pre-Java 8 and Java 8?

There is no change to how the Java developer uses and implements HashMap < K, V > . In Java 8, they have made some internal changes in HashMap, well that changes not only affect HashMap but also, LinkedHashMap, and ConcurrentHashMap.

a). The alternative String hash function added in Java 7 has been removed in Java 8. The default hash formula on strings was optimized to being both faster and allow for less clashes on average. Thus if your key is a string (someone’s name in a contacts list), it should calculate that hash faster than before and the likelihood that it would calculate a hash pointing to the same bucket is less.

b). Buckets containing a large number of colliding keys will store their entries in a balanced tree instead of a linked list after a certain threshold is reached.

#Collections: Part 4 (How ConcurrentHashMap Works Internally in Java?)

ALSO CHECK: Java Collections Interview Questions and Answers

What is ConcurrentHashMap?

ConcurrentHashMap class is introduced in JDK 1.5, which implements ConcurrentMap as well as Serializable interface also.

It is a thread-safe implementation of the Map interface provided by Java's concurrency package (java.util.concurrent). It allows concurrent access to the map without the need for external synchronization.

Segment, which is internal data structure and part of map is locked while adding or updating the map. Due to this the ConcurrentHashMap allows concurrent threads to read the value without locking at all. This data structure was introduced to improve performance.

#Collections: Part 3- All about PriorityQueue in Java

ALSO CHECK: Java Collections Interview Questions and Answers

What is PriorityQueue in Java?

• A queue follows First-In-First-Out algorithm, in case of PriorityQueue queue elements are processed according to the priority (ordered as per their natural ordering or based on a custom Comparator supplied at the time of creation).
• The PriorityQueue is based on the priority heap.
• We can’t create PriorityQueue of Objects that are non-comparable
• Inserting null into a PriorityQueue will throw a NullPointerException, as PriorityQueue in Java does not permit null elements.
• PriorityQueue are unbound queues.
• The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements — ties are broken arbitrarily.
• The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
• PriorityQueue inherits methods from AbstractQueue, AbstractCollection, Collection and Object class.
• Inserting an element (offer()) and deleting an element (poll()) in a PriorityQueue both have a time complexity of O(log n), where n is the number of elements in the queue.
• The default PriorityQueue is implemented with Min-Heap, which means the top element is the minimum one in the heap. If we want to implement a max-heap, we need to use our custom Comparator.
• Internally, the PriorityQueue in Java uses an array to store its elements. This array automatically grows in size if the initial capacity (which is 11 by default in JDK 17) is not large enough to hold all the elements added to the queue. 
• While you don't have to specify an initial capacity when creating a PriorityQueue, if you know how many elements you'll be adding ahead of time, it's beneficial to set an initial capacity. This helps prevent the queue from frequently resizing, which can use up unnecessary CPU resources that could be better utilized elsewhere.

Can you provide an example scenario where a PriorityQueue would be useful?

A PriorityQueue can be used in scenarios such as task scheduling in an operating system, where tasks with higher priority need to be executed before those with lower priority.

PriorityQueue Constructors

• PriorityQueue(): Creates a PriorityQueue with the default initial capacity (which is 11) that orders its elements according to their natural ordering.
• PriorityQueue(Collection c): It creates a PriorityQueue containing the elements in the specified collection.
• PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
• PriorityQueue(int initialCapacity, Comparator comparator): Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
• PriorityQueue(PriorityQueue c): Creates a PriorityQueue containing the elements in another priority queue.
• PriorityQueue(SortedSet c): Creates a PriorityQueue containing the elements in the specified sorted set.

PriorityQueue operations

• boolean add(E element)inserts the specified element into this priority queue.
• boolean offer(E e) method is used to insert a specific element into the priority queue.
• public peek() retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
• public poll() retrieves and removes the head of this queue, or returns null if this queue is empty.
• public remove() removes a single instance of the specified element from this queue, if it is present. When we remove an element from the priority queue, the least element according to the specified ordering is removed first.
• Iterator iterator() returns an iterator over the elements in this queue.
• boolean contains(Object o) method returns true if this queue contains the specified element
• void clear() is used to remove all of the contents of the priority queue.
• int size() returns the number of elements present in the set.
• toArray() is used to return an array containing all of the elements in this queue.
• Comparator comparator() method is used to return the comparator that can be used to order the elements of the queue.

What is the difference between offer and add methods of PriorityQueue?

• offer() and add() are two ways to insert data into a PriorityQueue.
• In Queues, the add is used to insert a specified element into the queue. It returns true when the task is successful or else it throws an exception. offer() is also used to insert a specified element into the queue. But it returns true when the task is successful or else its return false.
• In the case of PriorityQueue, the add method behaves identically to offer() in a PriorityQueue. If you see the implementation, the add method of PriorityQueue is internally calling offer.

GIT URL: PriorityQueue Example in Java

Priority Queue Example

-K Himaanshu Shuklaa..

#Collections: How LinkedHashMap works internally in Java?

ALSO CHECK: Java Collections Interview Questions and Answers

Java LinkedHashMap class is Hashtable and Linked list implementation of the Map interface. LinkedHashMap is like HashMap with an additional feature of maintaining an order of elements inserted into it.

All About Bloom Filter

What is Bloom Filter?

Bloom filters are for set membership which determines whether an element is present in a set or not. Bloom filter is a probabilistic data structure that works on hash-coding methods (similar to HashTable).

It is a memory-efficient, probabilistic data structure that we can use to answer the question of whether or not a given element is in a set.

Part 3: LinkedList Related Algorithm Interview Questions(Union and Intersection)

Also Check: Algorithms and System Design Interview Questions

Create a Union and Intersection of two Linked Lists.
Solution 1: Using Merge Sort.
In this approach you need to sort both the lists,this will take O(mLogm) and O(nLogn) time.
Now we will iterate both the sorted lists to get the union and intersection, it will take O(m + n) time
Time complexity of this method is O(mLogm + nLogn).

Solution 2:Use Hashing
We can use HashTable to find the Union and Intersection of two Linked Lists. Here we are assuming that there are no duplicates in each list. Time Complexity would be O(m+n).

For Union:
1). Create the result list, initialize it with NULL and create an empty hash table.
2). Start traversing the givens lists one by one. During iteration, look the element in the hash table. If the element is not present, then insert the element to the result list and in the hash table as well. Else if the element is present, then ignore it.

For Intersection:
1). Create the result list, initialize it with NULL and create an empty hash table.
2). Start traversing the first list, and insert each element in the hash table.
3). Now traverse the second list. During iteration, look the element in the hash table. If the element is not present, then insert the element to the result list and in the hash table as well. Else if the element is present, then ignore it.

Write a function to get the intersection point of two Linked Lists.
Solution 1: Nested Loop
1). We will use 2 nested loops. In the outer loop will be for each node of the 1st list and inner loop will be for 2nd list.
2). In the inner loop, we will check if any of nodes of the 2nd list is same as the current node of the first linked list.

The time complexity of this approach will be O(M * N), where m and n are the numbers of nodes in two lists.

Solution 2: Node count difference.
1). We will get the count of the nodes in the both the lists, lets say c1 and c2 are the number of nodes on 1st and 2nd list.
2). Now we will get the difference of node counts, d = abs(c1 – c2).
3). We will start traversing the bigger list from the first node till dth node. From here onwards both the lists have equal no of nodes.
4). Now we can traverse both the lists in parallel till we come across a common node.



-K Himaanshu Shuklaa..

Part 2: LinkedList Related Algorithm Interview Questions(Reverse)

Also Check: Algorithms and System Design Interview Questions

How to reverse a linked list using recursion and iteration?
In the iteration approach we reverse linked list using 3 pointers in O(n) time, This is done by creating a new list by reversing direction, and subsequently inserting the element at the start of the list.



We can also reverse a singly linked list by using recursion. We will traverse the linked list until we find the tail, this tail  would be the new head for reversed linked list.



-K Himaanshu Shuklaa..

Part 1: LinkedList Related Algorithm Interview Questions(find kth element from end, check if list has loop)

Also Check: Algorithms and System Design Interview Questions

How to find middle element of linked list in one pass?
LinkedList data structure contains a collection of the node and has head and tail. To find the middle element in one pass we can use two-pointer approach.