Question 1: Most asked interview Questions: HashMap internal working

[00:00:00]Imagine finding one book in a library of a million books.

[00:00:03]You could scan each one, that's O of N, or jump straight to the right shelf, O of 1. That's what a hash map does.

[00:00:09]Internally, it's an array of buckets, 16 by default. Each slot holds an entry, the hash, the key, the value, and a next pointer.

[00:00:17]Put apple 100. Its hash code is masked with hash and N minus 1 to give bucket 10, and an entry is stored there.

[00:00:24]Real maps hold many keys spread across the buckets. Most land alone, but some buckets pick up a short chain.

[00:00:30]Now put papaya. Its hash also lands in bucket 10, a collision. Hash map just links it after apple. Collision is no problem.

[00:00:37]To read it back, get papaya runs the same hash, jumps straight to bucket 10, and never scans the other 15 buckets.

[00:00:44]Then it walks that bucket's chain with equals. Apple? No. Papaya? Yes, return 200. So, here's the split worth memorizing. Hash code finds the bucket, and equals finds the exact key inside it. Since Java 8, if one bucket collects eight or more entries, that long chain turns into a balanced red-black tree, a search tree.

[00:01:03]So, lookups are constant time on average, and thanks to that tree, even the worst case is just O of log N. It used to be O of N.

[00:01:11]Reach for a hash map whenever you need fast lookup by a key, caches, ID lookups, product search, configs.

[00:01:18]The whole picture, an array of buckets, chains for collisions, trees when they grow.

[00:01:23]Hash code for the bucket, equals for the key.

[00:01:26]That's hash map internals in 2 minutes.

[00:01:28]The full deep dive and a test are on yuktiara.com, and follow for the whole Java series.