MediumConcept

How does HashMap work internally in Java?

Technology:
Java
Experience:
Mid-level,
Senior

Quick answer

A HashMap stores entries in an array of buckets; it computes the key's hash code to choose a bucket, resolves collisions with a linked list that becomes a red-black tree when a bucket grows large, and resizes when the load factor of 0.75 is exceeded.

Detailed explanation

On put(key, value), HashMap calls key.hashCode(), spreads the bits, and uses hash & (capacity - 1) to pick a bucket index. If the bucket is empty, the entry is stored there. If not, it walks the bucket comparing keys with equals(): a matching key has its value replaced, otherwise the new entry is added to the end. That is why correct hashCode() and equals() implementations are essential for keys.

The default capacity is 16 and the load factor is 0.75, so when more than 12 entries are stored, the table doubles and entries are redistributed. Since Java 8, a bucket with 8 or more entries (when the table has at least 64 buckets) is converted from a linked list to a red-black tree, which keeps worst-case lookup at O(log n) instead of O(n). Average get and put are O(1). HashMap allows one null key, does not guarantee ordering and is not thread-safe.

Key points

  • Index = hash of key mapped onto the bucket array
  • Collisions: linked list, treeified at 8 entries
  • Resizes at load factor 0.75; not thread-safe

Follow-up questions

  • What happens if two keys have the same hashCode?
  • Why should HashMap keys be immutable?
  • JavaMedium

    What is the difference between ArrayList and LinkedList in Java?

    ArrayList is backed by a resizable array with O(1) index access and O(n) insertion in the middle, while LinkedList is a doubly linked list with O(n) index access and O(1) insertion once you hold the node; in practice ArrayList is faster for most workloads.

    Junior 路 Mid-level 路 Data Structures
  • JavaMedium

    What is the difference between an abstract class and an interface in Java?

    An abstract class can have instance fields, constructors and a mix of implemented and abstract methods but supports only single inheritance, while an interface defines a contract that a class can implement multiple times and, since Java 8, can include default methods.

    Junior 路 Mid-level 路 Object-Oriented Programming
  • JavaMedium

    What is the difference between checked and unchecked exceptions in Java?

    Checked exceptions (subclasses of Exception other than RuntimeException) must be caught or declared with throws, while unchecked exceptions (RuntimeException and Error) do not have to be handled and usually signal programming bugs.

    Junior 路 Mid-level 路 Programming Fundamentals
  • JavaMedium

    What are the main features of Java 8: lambdas, streams and Optional?

    Java 8 introduced lambda expressions, functional interfaces, the Stream API for declarative collection processing, Optional to represent missing values, default methods in interfaces, method references and the java.time date and time API.

    Junior 路 Mid-level 路 Functions & Scope
  • JavaHard

    How does JVM memory management and garbage collection work in Java?

    The JVM divides memory into a per-thread stack, a shared heap (split into young and old generations) and Metaspace; the garbage collector frees heap objects that are no longer reachable, collecting short-lived young objects frequently and old objects less often.

    Mid-level 路 Senior 路 Memory Management