Forem: Tapas Pal

Find First Non Repeating Character - Java Program With Time and Space Complexity

Tapas Pal — Wed, 13 May 2026 04:49:30 +0000

Problem Statement
Given a string: "swiss"
Find the first character that appears only once.
Expected Output : w
Because:
s repeats
w appears once and comes first

Solution:
Best Approach (Using LinkedHashMap)
We will use: LinkedHashMap
Why? Because:

Stores frequency count
Maintains insertion order

Approach-1 : Frequency Array (int[256])

// Method to find the first non-repeating character
public class FirstNonRepeatingCharacter {
   public static Character firstNonRepeating(final String str) {
         // Check if string is null or empty
        // If yes, return null because no character exists
       if (str == null || str.isEmpty()){
            return null;
        }
        // Create frequency array of size 256
        // Each index represents an ASCII character
        // Example: freq['a'] stores count of 'a'
       int[] freq = new int[256];
       // Convert string into char array and iterate each character
       for(char ch : str.toCharArray()) {
           // Increment frequency count of character
           freq[ch]++;
       }
       // Iterate again to preserve original order
       // We need FIRST non-repeating character
       for(char ch : str.toCharArray()) {
          // Check if character frequency is exactly 1
          if(freq[ch] == 1) {
             // Return first unique character immediately
             return ch;
          }
       }
   // If no non-repeating character found
   return null;
   }
   public static void main(String[] args) {
        // Example 1
        // swiss
        // s -> 3
        // w -> 1
        // i -> 1
        // First non-repeating = w
        System.out.println(firstNonRepeating("swiss"));
        // Example 2
        // null input
        // returns null
        System.out.println(firstNonRepeating(null));
    }
}

Approach-2 : LinkedHashMap

public class FirstNonRepeatingCharacter {

    public static Character findFirstNonRepeating(final String str) {
        if (str == null || str.isEmpty()){
            return null;
        }
        // Step 1: Create LinkedHashMap to store character frequencies
        Map<Character, Integer> map = new LinkedHashMap<>();
        // Step 2: Count frequency of each character
        for(char ch : str.toCharArray()) {
        //If key exists → return value otherwise return default   
       //value 0, for first time of each character always map.getOrDefault(ch, 0) = 0
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        // Step 3: Find first character with frequency 1
        for(Map.Entry<Character, Integer> entry : map.entrySet()) {
            if(entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return null;
    }
   public static void main(String[] args) {
        System.out.println(firstNonRepeating("swiss"));
        System.out.println(firstNonRepeating(null));
    }
}

Approach-3 : Java Streams + groupingBy

public class FirstNonRepeatingCharacter {
    public static char firstNonRepeating(final String str) {
       if (str == null || str.isEmpty()){
            return null;
        }
       Map<Character, Long> map =
            str.chars()
             .mapToObj(c -> (char) c)
             .collect(Collectors.groupingBy(
                     c -> c,
                     LinkedHashMap::new,
                     Collectors.counting()
             ));

       return map.entrySet()
              .stream()
              .filter(e -> e.getValue() == 1)
              .map(Map.Entry::getKey)
              .findFirst()
              .orElse(null);
}
    public static void main(String[] args) {
        System.out.println(firstNonRepeating("swiss"));
        System.out.println(firstNonRepeating(null));
    }
}

Comparing 3 Approaches for First Non-Repeating Character

We will compare:

Frequency Array (int[256])
LinkedHashMap
Java Streams + groupingBy

We’ll analyze:

readability
performance
memory usage
Unicode support
interview suitability
production suitability
Problem Statement

Input: "swiss"
Frequency:
s -> 3
w -> 1
i -> 1

Output: w
Approach 1 — Frequency Array (int[256])
Code Logic
int[] freq = new int[256];
Store frequency using ASCII index.
Example: freq['s']
stores count of s. Visual Flow "swiss"
↓
freq['s'] = 3
freq['w'] = 1
freq['i'] = 1
Second loop:
s -> 3 ❌
w -> 1 ✅
Return: w
Time Complexity Two loops: O(n) + O(n)
Final: O(n)
Space Complexity int[256]
Fixed size, so: O(1) (constant space)
Advantages
✅ Fastest approach
✅ Lowest memory usage
✅ Very interview-friendly
✅ Excellent cache locality
✅ No object creation overhead
Disadvantages
❌ ASCII only
❌ Not Unicode-safe
❌ Less flexible
❌ Hardcoded size assumption
Important Unicode Problem
This breaks for:

Chinese
Japanese
Emoji
Unicode chars

Because Unicode exceeds 256.
Best Use Case Best for:

competitive programming
ASCII-only systems
performance-critical code

Approach 2 — LinkedHashMap
Code Logic
Map<Character, Integer> map = new LinkedHashMap<>();

Why LinkedHashMap? Preserves insertion order

Needed for: FIRST non-repeating character
Time Complexity Insertion: O(1) for each char.

Total: O(n) Space Complexity
Worst case: all unique characters
Map stores all. So: O(n)
Advantages
✅ Unicode-safe
✅ Easy to understand
✅ Flexible
✅ Maintains insertion order
✅ Production-friendly

Disadvantages
❌ More memory usage
❌ Object overhead
❌ HashMap node overhead
❌ Slightly slower than array

Internal Memory Cost Each entry stores:

Character object
Integer object
Node object
next pointer
hash

Much heavier than array.
Best Use Case
Best for:

enterprise applications
Unicode support
maintainable code
real production systems

Approach 3 — Streams + groupingBy
Code Logic str.chars()
Convert string to stream. Then: groupingBy(...)
creates frequency map.
Visual Flow
"swiss"
↓ chars()
115 119 105 115 115
↓ mapToObj()
[s,w,i,s,s]
↓ groupingBy()
{
s=3,
w=1,
i=1
}
↓ filter(value == 1)
w
Time Complexity Still: O(n)
BUT Important Hidden Cost

Streams introduce:
lambda calls
boxing/unboxing
stream pipeline overhead
temporary objects

So practical runtime is slower. Space Complexity

Internally creates:

Stream objects
Collectors
Lambda instances
LinkedHashMap

Worst case: O(n)
but with higher constant factors.
Advantages
✅ Elegant
✅ Functional style
✅ Modern Java
✅ Very expressive
✅ Concise

Disadvantages
❌ Slowest approach
❌ More garbage objects
❌ Higher memory overhead
❌ Harder debugging
❌ Less beginner-friendly

Performance Reality Even though all are: O(n)
Big difference exists in actual runtime.
Real Runtime Ranking **
Array > LinkedHashMap > Streams
**Memory Ranking Least memory → Highest memory
Array > LinkedHashMap > Streams
Readability Ranking
Most readable: LinkedHashMap
Most concise: Streams
Most low-level: Array

DRY RUN WITH APPROACH 2(LinkedHashMap) with input swiss
Step 1 — Null/Empty Check

if (str == null || str.isEmpty())

Input: "swiss"
Condition: false
Continue execution.
Step 2 — Create LinkedHashMap

Map<Character, Integer> map = new LinkedHashMap<>();

Initially: {} (empty map)
IMPORTANT
LinkedHashMap preserves insertion order. This is critical.
Step 3 — Convert String to char[]
str.toCharArray()
Result: [s, w, i, s, s]
FIRST LOOP — Count Frequencies
Iteration 1 char ch = 's'
Execute map.getOrDefault('s', 0)
's' not present.
Returns: 0 Then 0 + 1 becomes: 1
Put into map

map.put('s', 1)

Map Now
{
s=1
}
Visual Representation
Head
↓
[s=1]
Iteration 2
char ch = 'w'
Execute
map.getOrDefault('w', 0)
'w' absent.
Returns: 0
Put
map.put('w', 1)

Map Now
{
  s=1,
  w=1
}
Visual
Head
 ↓
[s=1] ⇄ [w=1]

Iteration 3
char ch = 'i'
Execute

map.getOrDefault('i', 0)

Returns: 0
Put

map.put('i', 1)
Map Now
{
  s=1,
  w=1,
  i=1
}

Visual
[s=1] ⇄ [w=1] ⇄ [i=1]
Iteration 4 char ch = 's'
Execute

map.getOrDefault('s', 0)

's' exists. Returns: 1
Increment
1 + 1 = 2
Update Map
map.put('s', 2)

Map Now
{
  s=2,
  w=1,
  i=1
}

IMPORTANT

Insertion order remains SAME.
's' does NOT move.
Visual
[s=2] ⇄ [w=1] ⇄ [i=1]
Iteration 5
char ch = 's'
Execute
map.getOrDefault('s', 0)
Returns: 2
Increment
2 + 1 = 3
Update
map.put('s', 3)

Final Map
{
  s=3,
  w=1,
  i=1
}

Final Internal Linked Order
Head
 ↓
[s=3] ⇄ [w=1] ⇄ [i=1]
SECOND LOOP — Find First Non-Repeating
Traverse entrySet()
for(Map.Entry<Character, Integer> entry : map.entrySet())

Traversal order:
s → w → i

because LinkedHashMap preserves insertion order.

Entry 1
s=3
Check
entry.getValue() == 1
Result: false
Continue.
Entry 2
w=1
Check
entry.getValue() == 1
Result: true
Return return 'w'
Final Output w

Generics in Java Interview Q&A

Tapas Pal — Tue, 12 May 2026 20:05:24 +0000

Java Generics is one of the MOST important Java concepts.
If you understand Generics properly:
collections become safer code becomes reusable compile-time bugs reduce dramatically
A generic type is a generic class or interface that is parameterized over types.

What Are Generics?
Generics allow classes, interfaces, and methods to work with:
different data types safely
without rewriting code.
The Diamond
In Java SE 7 and later, you can replace the type arguments required to invoke the constructor of a generic class with an empty set of type arguments (<>) as long as the compiler can determine, or infer, the type arguments from the context. This pair of angle brackets, <>, is informally called the diamond. For example, you can create an instance of Box with the following
statement:

Box<Integer> integerBox = new Box<>();

Generic Class

class Box<T> {
    T value;
    void set(T value) {
        this.value = value;
    }
    T get() {
        return value;
    }
}

Usage

Box<String> box =
        new Box<>();
box.set("Hello");
String s = box.get();

What Does Mean?
T means:Type parameter
Placeholder for actual type.
Common Generic Type Names
Symbol - Meaning
T - Type
E - Element
K - Key
V - Value
N - Number

Same class reused.

Box<Integer> intBox = new Box<>();
Box<String> strBox = new Box<>();

DISADVANTAGES OF GENERICS
Now let us discuss the IMPORTANT limitations.

1. Type Erasure
MOST IMPORTANT limitation.
Java removes generic type information at runtime.
Example

List<String> list = new ArrayList<>();

At runtime becomes: List
Generic type removed. Why?
Backward compatibility with old Java.
Consequences of Type Erasure
Cannot Do This

if(obj instanceof List<String>)

Compile-time error.

Cannot Create Generic Array

T[] arr = new T[10];

Not allowed. Why?
Because runtime type unknown.

2. Primitive Types Not Allowed
Cannot use: List<int>
Only objects allowed.
Correct List<Integer>
Uses wrapper classes.
Problem
Wrapper classes add:
memory overhead
boxing/unboxing cost
Example

List<Integer> list = new ArrayList<>();
list.add(10);

Actually becomes:
Integer.valueOf(10)
Auto-boxing.

3. Cannot Create Static Generic Fields
Invalid

class Test<T> {
    static T value;
}

Why?
A static field belongs to the class, but a generic type belongs to the object instance/type parameter.
These two concepts conflict.
First Understand Static Variables
Static variables are:shared across ALL objects
Only ONE copy exists.

Difference Between HashMap and ConcurrentHashMap

Tapas Pal — Tue, 12 May 2026 19:35:30 +0000

HashMap is non-thread-safe and optimized for single-threaded performance, while ConcurrentHashMap is designed for concurrent access using fine-grained synchronization and CAS operations. HashMap is preferable for local non-shared data, whereas ConcurrentHashMap is ideal for shared mutable state in multi-threaded applications.

Mutable Key Problem in HashMap

Tapas Pal — Tue, 12 May 2026 17:55:52 +0000

Mutable Key Problem in HashMap
HashMap depends on hashCode() remaining stable
If the key changes after insertion:

hashCode changes
bucket location changes
HashMap cannot find the object anymore

First Understand One Critical Rule
HashMap Stores Entry Based On: hashCode() + equals()
Simple Mutable Key Example
Employee Class

class Employee {
    String name;
    Employee(String name) {
        this.name = name;
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }
    @Override
    public boolean equals(Object obj) {
        Employee e = (Employee) obj;
        return this.name.equals(e.name);
    }
}

Step 1 — Create Object

Employee emp = new Employee("John");

Current value:

name = "John"
Step 2 — Put into HashMap

Map<Employee, String> map = new HashMap<>();
map.put(emp, "Developer");

What Happens Internally?
A. HashMap Calls hashCode()
emp.hashCode()
Suppose:

"John".hashCode() = 2314539

B. Bucket Index Calculated

Formula:index = (n - 1) & hash
Suppose result: bucket = 5
Internal Structure

Bucket 5
   ↓
(Employee{name="John"}, "Developer")

Everything works correctly.

Step 3 — Retrieve Object

map.get(emp);

HashMap again calculates:
"John".hashCode()
Gets same bucket: bucket 5
Finds object successfully.
Output:Developer
NOW THE DANGEROUS PART
Step 4 — Modify Key Object
emp.name = "David";
Now object becomes: Employee{name="David"}
Important Thing The SAME object reference exists.
But: hashCode has changed
Step 5 — Try Retrieval Again
map.get(emp);
What Happens Internally Now?
A. HashMap Calls hashCode()
Now:"David".hashCode() = 65805908
Different hashCode.
B. New Bucket Calculated Now: bucket = 12
HashMap Searches Wrong Bucket HashMap now checks:Bucket 12
BUT object actually stored in:Bucket 5
BEFORE Mutation

Bucket 5
   ↓
(Employee{name="John"}, "Developer")

hashCode based on:John
AFTER Mutation Object becomes:Employee{name="David"} Now HashMap calculates: bucket 12
So retrieval searches: Bucket 12 → EMPTY
Final Result

System.out.println(map.get(emp));

Output: null
This is called:Hash-based collection corruption
Even Worse Scenario
Now try: map.containsKey(emp);
Output:false even though object exists inside map.
Another Dangerous Problem
Suppose: map.put(emp, "Manager");
Now HashMap inserts NEW entry.
Internal State Becomes

Bucket 5
   ↓
(Employee{name="David"}, "Developer")

Bucket 12
   ↓
(Employee{name="David"}, "Manager")

Same object reference appears logically duplicated.
Why Immutable Objects are Safe

Example: String key = "John"; as Strings are immutable.
Meaning:value never changes

hashCode stable
bucket stable So retrieval always works. Best Practice Always Use Immutable Keys Recommended: String Integer UUID Immutable custom objects For Custom class use instance variable as final How to Create Immutable Key Object

final class Employee {
    private final String name;
    Employee(String name) {
        this.name = name;
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }
    @Override
    public boolean equals(Object obj) {
        Employee e = (Employee) obj;
        return this.name.equals(e.name);
    }
}

Now object cannot change after insertion.Safe for HashMap.

Real Production Problems Caused

Mutable keys can cause:
Memory leaks Duplicate entries Data inconsistency Cache corruption Hard-to-debug production issues
Especially dangerous in:
caching systems distributed systems Hibernate microservices concurrent systems

Q1: Why does retrieval fail even though same object reference is used?
Answer: Because HashMap first locates bucket using hashCode(). Reference equality is irrelevant until bucket found.

Q2: Can equals() alone solve this?
Answer: No.
Because equals() is checked only AFTER correct bucket located.

Q3: Can mutable keys ever be safe?
*Answer: * Only if fields used in hashCode()/equals() never change.

Q4: Is there any advantages of using mutable key?
*Answer: * Mostly used for:
`- object graph traversal

serialization frameworks
proxy systems
JVM internals` "Mutable keys are only safe if the mutable state is excluded from equals() and hashCode(). In practice, immutable or effectively immutable keys are preferred because HashMap bucket placement depends on stable hash codes."

Using StringBuilder as a HashMap Key — Why It Is Dangerous
"StringBuilder is a poor HashMap key because it uses reference-based equals/hashCode from Object and is mutable. Even though mutating it does not change the bucket location, the logical identity of the key changes, leading to unpredictable behavior, failed lookups, duplicate logical keys, and corrupted business semantics."

Q. If I have to use a custom class as a key, what precaution I need to take it?
Using a Custom Class as a HashMap Key — Precautions You MUST Take
This is a very common experienced-level Java interview question.
If you use a custom object as a HashMap key, the MOST important rule is:
equals() and hashCode() must be implemented correctly and consistently.

Otherwise you get:

failed retrievals
duplicate keys
memory leaks
corrupted collections
unpredictable behavior Golden Rules for Custom Keys Rule 1 — Override BOTH equals() and hashCode() Never override only one. WRONG Example

class Employee {
    int id;
    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

This breaks HashMap contract.
Correct Rule

If:
a.equals(b) == true
then:
a.hashCode() MUST equal b.hashCode()

Rule 2 — Use Immutable Fields for Equality

Fields used in:

`- equals()

hashCode()`

should NEVER change after insertion.
Best Practice Example

final class Employee {
    private final int id;
    private final String name;
    Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }
    @Override
    public boolean equals(Object obj) {
        if(this == obj)
            return true;
        if(obj == null || getClass() != obj.getClass())
            return false;
        Employee e = (Employee) obj;
        return id == e.id;
    }
    @Override
    public int hashCode() {
        return Integer.hashCode(id)}}

Why This Is Safe because:
id never changes hashCode stable bucket stable
HashMap works correctly forever.

Be Careful with Lombok
Dangerous Lombok Example

@Data
class Employee {
    int id;
    String name;
}

plaintext

@Data includes ALL fields.
If name changes:

hashCode changes
HashMap breaks Better @EqualsAndHashCode(of = "id")

Q. Why do we need to increase the size of the hash map and who determines when to increase it? Although we have hash collision, if we have hash collision, why do we need to increase the size?

Collisions can be handled, but too many collisions destroy performance.
Resizing exists to maintain:
near O(1) lookup/insertion performance
First Understand the Core Structure

A HashMap internally has:Array of buckets
Example:table[16]
Each bucket may contain:

empty
one node
linked list
tree
Visual Example Suppose capacity:16 Good Distribution

Bucket 0 → A
Bucket 1 → empty
Bucket 2 → B
Bucket 3 → C
Bucket 4 → empty
Bucket 5 → D

Very few collisions.Operations close to: O(1) Fast.
What Happens If Map Keeps Growing Without Resize?
Suppose:
still only 16 buckets but now 10,000 entries inserted Internal Structure Becomes Bucket 0 → A → B → C → D → E → F Bucket 1 → G → H → I → J Bucket 2 → K → L → M → N → O ...
Huge collision chains.Now Lookup Becomes Slow
Suppose searching: O(n)
instead of:O(1)
Important PointCollision handling does NOT eliminate performance degradation.
It only prevents data loss.

Why Resize Helps, Suppose capacity increases:
16 → 32 Now more buckets available.
Entries redistribute.
BEFORE Resize Bucket 5 ↓ A → B → C → D → E AFTER Resize Bucket 5 → A → C Bucket 21 → B → D → E
Collision chains smaller.
Performance improves.
Main Goal of Resizing
Reduce: collision density
This keeps:
lookup fast insertion fast deletion fast
Who Decides When Resize Happens?
HashMap uses:
load factor
Default Load Factor
0.75
Formula
threshold = capacity × loadFactor
Bucket Index Calculation
Java internally uses:
index = (n - 1) & hash
Where: n = array capacity
hash = processed hashCode
This is fixed.You cannot override it in normal HashMap.
The bucket calculation algorithm in Java HashMap is fixed internally and cannot be overridden. Java uses (capacity - 1) & hash for fast bucket computation. However, developers indirectly influence bucket placement through the quality of their hashCode() implementation.

How does HashMap work internally?

Tapas Pal — Mon, 11 May 2026 22:11:57 +0000

Day-1
1. How does HashMap work internally?
Answer:
High-Level Internal Structure
Internally, HashMap uses:
Array + LinkedList + Red-Black Tree (Java 8+)

Internal Data Structure

transient Node<K,V>[] table;

class Node<K, V> {
     int hash;
     K key;
     V value;
   Node<K, V> next;
}

This is an array of buckets.
Each bucket stores:
single node linked list tree nodes

Basic Working Flow
When you do:

map.put(key, value);

HashMap performs:

Calculate hashCode()
Calculate bucket index
Store value in bucket
Handle collision if needed

Step-by-Step Example

Map<Integer, String> map = new HashMap<>();
map.put(101, "John");
map.put(102, "David");
map.put(103, "Alex");

Now let us understand internally what happens.
Step 1: Create HashMap

Map<Integer, String> map = new HashMap<>();

Internally:
capacity = 16 loadFactor = 0.75 threshold = 12

Meaning:
resize after 12 elements
Internal Array

Initially: table[16]
Like:

All buckets empty initially.
Step 2: Insert First Entry

map.put(101, "John");
//
{
  int hash = 101;
  Key key = {101};
  String value = "John";
  Node next = null;
}

Internal Working
A. Calculate hashCode()
For Integer:

hash = key.hashCode()

For 101: hash = 101
B. Calculate Bucket Index
Formula:

index = (n - 1) & hash

Where: n = capacity = 16
So: 15 & 101
Binary:
15 = 00001111 101 = 01100101

Result: 5
So element stored in: bucket 5

Internal Structure

table[5] → Node(101, "John")

Step 3: Insert Another Entry
map.put(102, "David");
Hash: 102
Index: 15 & 102 = 6
Stored at: bucket 6

Current Structure
table[5] → (101, John) table[6] → (102, David)

What is a Node Internally?
Simplified internal class:

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

Collision Handling
Now suppose:

map.put(117, "Mike");

Why Collision Happens?
Index formula: 15 & 117 = 5
Same bucket as 101.

Now What Happens?
HashMap creates linked list.
table[5] ↓ (101, John) ↓ (117, Mike)
This is collision handling.
How Retrieval Works
Suppose:

map.get(117);

Step-by-Step Retrieval

Step 1: Calculate hash hash = 117 Step 2: Find bucket 15 & 117 = 5

Go to bucket 5.
Step 3: Traverse nodes
Bucket contains:

(101, John)
(117, Mike)

HashMap checks: equals()
until matching key found.
Returns: Mike
Why equals() is Important?
Hash collision possible.
So HashMap uses:
`1. hashCode()

equals()`

Both are mandatory.
Internal Put Logic (Simplified)

public V put(K key, V value) {
    int hash = hash(key);
    int index = (table.length - 1) & hash;
    Node<K,V> node = table[index];
    if(node == null) {
        table[index] = new Node<>(hash, key, value);
    } else {
        // collision handling
        // traverse linked list
        // compare using equals()
        // update or append
    }
}

Java 8 Optimization

Before Java 8:
collisions stored as linked list only
Problem: worst-case O(n)

Java 8 Improvement
If bucket size becomes: > 8
Linked list converts to: Red-Black Tree
called: Treeification
Now complexity becomes: O(log n)
instead of: O(n)
Visual Example
Before Treeify
Bucket 5:
A → B → C → D → E → F → G → H → I
Search slow.

After Treeify
          D
        /   \
       B     G
      / \   / \
     A  C  F  I

Faster searching.
Important Interview Point
Why Capacity Always Power of 2?
Because index calculation:

(n - 1) & hash

is faster than modulo:

hash % n

Load Factor Default: 0.75

Meaning: resize when 75% full

Rehashing
When threshold exceeded:

New bigger array created
Entries redistributed Example: 16 → 32

*Why Immutable Keys Recommended?
*
Suppose:

class Employee {

    String name;
}

If name changes:

hashCode changes
retrieval fails

Very dangerous.
That is why:

String
Integer
immutable objects

recommended as keys.

**Real Interview Example
**Bad Mutable Key

class Employee {
    String name;
    Employee(String name) {
        this.name = name;
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }
    @Override
    public boolean equals(Object obj) {
        Employee e = (Employee) obj;
        return this.name.equals(e.name);
    }
}

Problem

Employee e = new Employee("John");
map.put(e, "Developer");
e.name = "David";
map.get(e); // FAILS

Because:

bucket changed
object unreachable

Time Complexity
Operation Average Worst put O(1) O(n) get O(1) O(n) remove O(1) O(n)
Java 8 treeification improves worst case:

O(log n)

Internal Hash Function
Java improves hash distribution:

static final int hash(Object key) {
    int h;
    return (key == null)
            ? 0
            : (h = key.hashCode()) ^ (h >>> 16);
}

This avoids poor bucket distribution.
*Null Handling *
HashMap allows:

one null key
multiple null values

Null key always stored in: bucket 0
Important Differences Feature Thread-safe Null-allowed Performance HashMap No Yes. Faster Hashtable Yes No Slower