How HashMap work in Java


If someone had asked me a year ago how HashMap works, I would've confidently said,

"It's just a key-value pair that uses hashing to store data."

Technically, I wasn't wrong.

But I wasn't completely right either.

While preparing for interviews, I decided to go beyond the definition.

That's when I discovered what actually happens inside a HashMap.

It isn't just a collection of random buckets.

At its core, HashMap uses a dynamic array.

Each position in that array is called a bucket.

When you insert a key, Java calculates its hashCode() to decide which bucket it belongs to.

But what if two different keys end up in the same bucket?

That's called a collision.

Instead of overwriting the existing value, HashMap stores both entries together.

Java then uses equals() to identify the correct key when retrieving data.

Earlier versions stored collided entries as a Linked List.

But in Java 8 and above, if too many entries accumulate in the same bucket (and the table is large enough), the linked list is converted into a Red-Black Tree.

That small optimization improves lookup performance from O(n) to O(log n) in worst-case scenarios.



View image

Comments

Post a Comment

Popular posts from this blog

Async/await

  Async/await An async function is a function declared with the async keyword, and the await keyword is permitted within them. The async and await keywords enable asynchronous, promise-based behavior to be written in a cleaner style, avoiding the need to explicitly configure promise chains. "async and await make promises easier to write" async  makes a function return a Promise await  makes a function wait for a Promise  Async functions Let’s start with the async keyword. It can be placed before a function, like this: async function f() {   return 1; } The word “async” before a function means one simple thing: a function always returns a promise. Other values are wrapped in a resolved promise automatically. For instance, this function returns a resolved promise with the result of 1; let’s test it: async function f() {   return 1; } f().then(alert); // 1 …We could explicitly return a promise, which would be the same: async function f() {   return Promis...
Read more

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.   Example 1: Input: s = "()" Output: true Example 2: Input: s = "()[]{}" Output: true Example 3: Input: s = "(]" Output: false Example 4: Input: s = "([])" Output: true   Stack-Based Logic: Traverse each character in the string. If it's an opening bracket ( '(' , '{' , '[' ), push it onto the stack. If it's a closing bracket ( ')' , '}' , ']' ): If the stack is empty , return false (nothing to match). If the top of the stack is the corresponding opening bracket , pop it. Otherwise, return false . ...
Read more

First negative in every window of size k

 Given an array arr[]  and a positive integer k, find the first negative integer for each and every window(contiguous subarray) of size k. Note: If a window does not contain a negative integer, then return 0 for that window. Examples: Input: arr[] = [-8, 2, 3, -6, 10] , k = 2 Output: [-8, 0, -6, -6] Explanation: Window [-8, 2] First negative integer is -8. Window [2, 3] No negative integers, output is 0. Window [3, -6] First negative integer is -6. Window [-6, 10] First negative integer is -6. Input: arr[] = [12, -1, -7, 8, -15, 30, 16, 28] , k = 3 Output: [-1, -1, -7, -15, -15, 0]  Explanation: Window [12, -1, -7] First negative integer is -1. Window [-1, -7, 8] First negative integer is -1. Window [-7, 8, -15] First negative integer is -7. Window [8, -15, 30] First negative integer is -15. Window [-15, 30, 16] First negative integer is -15. Window [30, 16, 28] No negative integers, output is 0. Input: arr[] = [12, 1, 3, 5] , k = 3 Output: [0, 0]  Explanation: Windo...
Read more