Java Notes
HubArray IntroductionArray OperationsArray Programs — FundamentalsArray Interview QuestionsJagged Array in JavaMulti Dimensional ArrayOne Dimensional Arraybreak and continue in JavaDo-While Loop in JavaFor Loop in JavaIf-Else Statements in JavaNested Loops in JavaSwitch-Case in JavaWhile Loop in JavaJava Compilation ProcessFeatures of JavaYour First Java ProgramHistory of JavaJava EditionsJava Program StructureJDK, JRE, and JVMWhat is Java?Immutable Strings in JavaString Class in JavaString Interview QuestionsString MethodsString Programs — FundamentalsStringBuffer in JavaStringBuilder in JavaComments in JavaData Types in JavaIdentifiers in JavaInput and Output in JavaKeywords in JavaOperators in JavaType Casting in JavaVariables in JavaAbstract Class in JavaAbstraction in JavaAnonymous Class in JavaClass and Object in JavaConstructor in JavaEncapsulation in JavaInheritance in JavaInner Class in JavaInterface in JavaMethod Overloading in JavaMethod Overriding in JavaObject Class in JavaObject Cloning in JavaOOPs IntroductionPolymorphism in Javastatic Keyword in Javasuper Keyword in Javathis Keyword in JavaWrapper Class in JavaCollections Framework OverviewCollections Practice ProgramsComparable vs Comparator in JavaGenerics in JavaIterator in JavaArrayList in JavaLinkedList in JavaStack in Java — Collections FrameworkVector in JavaHashMap in JavaHashtable in JavaLinkedHashMap in JavaTreeMap in JavaArrayDeque in JavaDeque Interface in JavaPriorityQueue in JavaHashSet in JavaLinkedHashSet in JavaTreeSet in JavaException Handling Best PracticesCustom Exceptions in JavaException Hierarchy in JavaFinally Block in JavaException Handling Introductionthrow and throws Keywords in JavaTry-Catch Block in JavaBuffered Streams in JavaByte Streams in JavaCharacter Streams in JavaDeserialization in JavaFile Class in JavaJava NIO PackageSerialization in JavaDate and Time API in Java 8Default and Static Methods in InterfacesFunctional Interface in Java 8Lambda Expression in Java 8Method Reference in Java 8Optional Class in Java 8Stream API in Java 8Creating Threads in JavaDaemon Threads in JavaExecutor Framework in JavaInter-Thread Communication in JavaMultithreading Programs in JavaRunnable Interface in JavaSynchronization in JavaThread Class in JavaThread IntroductionThread Life Cycle in JavaThread Priority in JavaBatch Processing in JDBCCallableStatement in JDBCJDBC ArchitectureJDBC IntroductionJDBC ProjectsMySQL Connection with JDBCPreparedStatement in JDBCResultSet in JDBCStatement Interface in JDBCTransaction Management in JDBCCookies in ServletsExpression Language (EL)GenericServletHttpServletJSP IntroductionJSP Tags and JSTLMVC ArchitectureRequest and Response ObjectsServlet IntroductionServlet Life CycleSession TrackingDependency InjectionAPI GatewayConfig ServerDocker DeploymentEureka Server - Service DiscoverySpring BeansCRUD ApplicationException Handling in Spring BootJWT Authentication — Java ProgrammingREST API with Spring BootSpring SecuritySpring Boot IntroductionSpring Data JPAValidation in Spring BootSpring Core ContainerSpring Framework IntroductionDynamic Programming in JavaGraph Data Structure in JavaHashing in JavaHeap (DSA)Linked List in JavaQueue in JavaRecursion in JavaSearching Algorithms in JavaSorting Algorithms in JavaStack in Java — DSA in JavaTime ComplexityTree Data Structure in JavaAdapter Design PatternBuilder Design PatternFactory Design PatternMVC Pattern — Java ProgrammingObserver Design PatternSingleton Design PatternArray Programs — PracticeBasic Java ProgramsCollection ProgramsJDBC ProgramsMultithreading ProgramsOOP ProgramsPlacement Coding QuestionsString Programs — PracticeBanking System — Java ProgrammingChat ApplicationE-Commerce BackendEmployee Management SystemLibrary Management System — Java ProgrammingSpring Boot Fullstack ProjectStudent Management System — Java ProgrammingCoding Interview QuestionsCollections Interview QuestionsCore Java Interview QuestionsJDBC Interview QuestionsMultithreading Interview QuestionsOOPs Interview QuestionsSpring Framework Interview QuestionsJava Cheat SheetImportant Formulas & ConceptsImportant Java ProgramsQuick Revision Notes — Java ProgrammingJava Master Course - Learning Roadmap
Complete guide to hashing — hash functions, collision resolution, HashMap internals, custom hashCode/equals, and applications of hashing in problem-solving.
What is Hashing?
Hashing is a technique that maps data of arbitrary size to fixed-size values (hash codes) for O(1) average-case access.
| Key: "Alice" | hashCode() → 63689437 → % table_size → index 5 |
| Key: "Bob" | hashCode() → 66965 → % table_size → index 3 |
| [0] | null |
| [1] | null |
| [2] | null |
| [3] | ("Bob", 92) |
| [4] | null |
| [5] | ("Alice", 85) |
Collision Resolution
Separate Chaining (Used by Java HashMap)
Example
public class ChainingHashMap<K, V> {
private static class Entry<K, V> {
K key; V value; Entry<K, V> next;
Entry(K key, V value) { this.key = key; this.value = value; }
}
private Entry<K, V>[] table;
private int size;
private static final int DEFAULT_CAPACITY = 16;
private static final float LOAD_FACTOR = 0.75f;
@SuppressWarnings("unchecked")
public ChainingHashMap() {
table = new Entry[DEFAULT_CAPACITY];
}
private int index(K key) {
return Math.abs(key.hashCode()) % table.length;
}
public void put(K key, V value) {
if ((float) size / table.length >= LOAD_FACTOR) resize();
int idx = index(key);
Entry<K, V> curr = table[idx];
while (curr != null) {
if (curr.key.equals(key)) { curr.value = value; return; }
curr = curr.next;
}
Entry<K, V> newEntry = new Entry<>(key, value);
newEntry.next = table[idx];
table[idx] = newEntry;
size++;
}
public V get(K key) {
int idx = index(key);
Entry<K, V> curr = table[idx];
while (curr != null) {
if (curr.key.equals(key)) return curr.value;
curr = curr.next;
}
return null;
}
private void resize() {
Entry<K, V>[] oldTable = table;
table = new Entry[oldTable.length * 2];
size = 0;
for (Entry<K, V> head : oldTable) {
while (head != null) {
put(head.key, head.value);
head = head.next;
}
}
}
}
Open Addressing (Linear Probing)
Example
// If collision at index i, try i+1, i+2, i+3...
private int probe(K key) {
int idx = Math.abs(key.hashCode()) % capacity;
while (table[idx] != null && !table[idx].key.equals(key)) {
idx = (idx + 1) % capacity; // Linear probing
}
return idx;
}
Java HashMap Internals (Java 8+)
| Initial capacity | 16 buckets |
| Load factor | 0.75 (resize at 12 entries) |
| Resize | doubles capacity |
| - < 8 entries | LinkedList (O(n) worst search in bucket) |
| - ≥ 8 entries | Red-Black Tree (O(log n) worst search in bucket) |
| - Treeify threshold | 8 |
| - Untreeify threshold | 6 |
hashCode() and equals() Contract
Example
public class Student {
private int id;
private String name;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return id == student.id && Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(id, name);
}
}
// CONTRACT:
// 1. If a.equals(b) then a.hashCode() == b.hashCode() (MUST)
// 2. If a.hashCode() != b.hashCode() then !a.equals(b) (contrapositive)
// 3. If a.hashCode() == b.hashCode(), a.equals(b) may or may not be true (collision OK)
// 4. hashCode must be consistent (same value in same JVM run)
Hashing Applications in Problem Solving
Example
// Two Sum - O(n) with HashMap
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) return new int[]{map.get(complement), i};
map.put(nums[i], i);
}
return new int[]{};
}
// First non-repeating character - O(n)
public char firstUnique(String s) {
Map<Character, Integer> count = new LinkedHashMap<>();
for (char c : s.toCharArray()) count.merge(c, 1, Integer::sum);
for (Map.Entry<Character, Integer> e : count.entrySet())
if (e.getValue() == 1) return e.getKey();
return '\\0';
}
// Group Anagrams - O(n * k log k)
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
// Longest substring without repeating characters - O(n)
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int maxLen = 0, start = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (lastSeen.containsKey(c) && lastSeen.get(c) >= start) {
start = lastSeen.get(c) + 1;
}
lastSeen.put(c, i);
maxLen = Math.max(maxLen, i - start + 1);
}
return maxLen;
}
Interview Questions
Q1: What happens if you override equals() but not hashCode()?
Answer: Objects that are "equal" may have different hash codes, so they'll end up in different HashMap buckets. You'll be able to put an object but not find it with an equal key. The hashCode/equals contract is violated.
Q2: What is the time complexity of HashMap operations?
Answer: Average: O(1) for get/put/remove. Worst case: O(n) with terrible hash function (all in one bucket), but Java 8+ converts to tree at 8 entries making worst case O(log n).
Q3: Why does HashMap use power-of-2 capacity?
Answer: Enables fast modulo using bitwise AND: index = hash & (capacity - 1). This is faster than % operator. Also ensures even distribution when combined with hash spreading.
Q4: What is the load factor and what happens when it's exceeded?
Answer: Load factor (default 0.75) is the ratio entries/capacity that triggers resizing. When exceeded, HashMap doubles capacity and rehashes all entries. Lower load factor = fewer collisions but more memory. Higher = more collisions but less memory.
Q5: How does Java 8 handle hash collisions differently from Java 7?
Answer: Java 7: always uses linked lists for collision chains. Java 8: converts to balanced red-black tree when chain length ≥ 8 (treeify), converts back to list when ≤ 6 (untreeify). This improves worst-case from O(n) to O(log n).
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Hashing in Java.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, dsa, hashing, hashing in java
Related Java Master Course Topics
Continue learning this concept
DSA in JavaDynamic Programming in JavaComplete guide to Dynamic Programming in Java covering memoization, tabulation, classical DP problems (Fibonacci, Knapsack, LCS, LIS, Coin Change), time/space optimization, and interview patterns.DSA in JavaGraph Data Structure in JavaComplete guide to graphs — representation, BFS, DFS, shortest path algorithms, topological sort, and classic graph problems in Java.DSA in JavaHeap (DSA)Complete guide to Heap data structure in Java covering Min Heap, Max Heap, heap operations, heapify algorithm, PriorityQueue class, heap sort, and applications with detailed implementations.DSA in JavaLinked List in JavaComplete guide to Linked Lists — Singly, Doubly, and Circular linked lists with Java implementations, operations, and classic interview problems.DSA in JavaQueue in JavaComplete guide to Queue data structure — FIFO principle, circular queue, priority queue, deque, BFS applications, and classic problems.DSA in JavaRecursion in JavaMaster recursion — base cases, recursive thinking, call stack visualization, tail recursion, memoization, backtracking, and converting recursion to iteration.