7. HASH TABLE (DICTIONARY INTERNALS)

Definition

• A hash table is a data structure that stores key-value pairs

• Uses a hash function to map keys to indices (buckets)

• Average lookup, insert, delete → O(1)

---

Internal Structure (.NET Dictionary)

Dictionary:

int[] buckets
Entry[] entries

Entry:
    int hashCode
    int next
    TKey key
    TValue value

---

Buckets

• Array of indices

• Each bucket points to an index in entries

buckets:
[0] = -1
[1] = 2
[2] = -1
[3] = 0

---

Entries

entries:

[0]: hash=23, key=K1, value=V1, next=-1
[1]: hash=45, key=K2, value=V2, next=-1
[2]: hash=23, key=K3, value=V3, next=0

---

Insert Flow

1. Compute hashCode = key.GetHashCode()
2. bucketIndex = hashCode % buckets.Length
3. Check bucket
4. If empty → insert
5. If collision → chain via "next"

---

Example

var dict = new Dictionary<int, string>();

dict[1] = "A";
dict[2] = "B";

---

Collision Handling

• Uses separate chaining

• Linked via next index

Bucket[3]:

index 2 → index 0 → null

---

Lookup Flow

1. Compute hash
2. Find bucket
3. Traverse chain
4. Compare using Equals()

---

Complexity

Case	Time
Average	O(1)
Worst	O(n)

---

Mutable Key Issue

class Key
{
    public int Id;
    public override int GetHashCode() => Id;
}

var k = new Key { Id = 1 };

var dict = new Dictionary<Key, string>();
dict[k] = "A";

k.Id = 2;

dict.ContainsKey(k); // false

---

Why it fails

Original:
hash = 1 → bucket A

After change:
hash = 2 → different bucket

→ lookup fails

---

Equals vs GetHashCode

• Hash → bucket selection

• Equals → final match

Equal objects MUST have same hash

---

Interview Answer

A dictionary in .NET is implemented as a hash table using two arrays: buckets and entries. Keys are hashed using GetHashCode to determine the bucket, and collisions are handled using chaining through indices. Lookup is O(1) on average but can degrade if many collisions occur.

---

---

8. IEnumerable (ITERATOR INTERNALS)

Definition

• Represents a sequence of elements

• Uses iterator pattern

• Supports deferred execution

---

Key Interfaces

IEnumerable<T>
IEnumerator<T>

---

Execution Flow

GetEnumerator()
    ↓
MoveNext()
    ↓
Current

---

Example

IEnumerable<int> Get()
{
    yield return 1;
    yield return 2;
}

---

Compiler Transformation

State machine:

state = 0 → return 1
state = 1 → return 2
state = -1 → end

---

LINQ Chain

var result = list
    .Where(x => x > 2)
    .Select(x => x * 2);

---

Internal Representation

SelectIterator
    holds reference to WhereIterator

WhereIterator
    holds reference to List

---

Execution

foreach triggers:

Select.MoveNext()
    → calls Where.MoveNext()
        → calls List enumerator

---

Deferred Execution

var query = list.Where(x => x > 2);

No execution yet

---

query.ToList();

Execution happens here

---

Interview Answer

IEnumerable represents a lazy sequence of elements where execution is deferred until enumeration. LINQ operations form a chain of iterators, and each element flows through the pipeline during iteration.

---

---

9. IQueryable

Definition

• Represents query as expression tree

• Execution deferred to provider (e.g., EF, LINQ to SQL)

---

Example

var q = db.Users.Where(x => x.Age > 18);

---

Expression Tree

Where(
    source: Users,
    predicate: x => x.Age > 18
)

---

Execution Flow

Expression tree
    ↓
Provider translates (e.g., SQL)
    ↓
Database executes
    ↓
Results returned

---

Difference vs IEnumerable

Feature	IEnumerable	IQueryable
Execution	In-memory	External
Representation	Delegates	Expression trees

---

Example Difference

// IEnumerable
users.Where(x => x.Age > 18).ToList();

Fetch all → filter in memory

---

// IQueryable
db.Users.Where(x => x.Age > 18);

Translate → SELECT * WHERE Age > 18

---

Interview Answer

IQueryable builds expression trees that are translated by a provider into optimized queries such as SQL, allowing filtering and execution at the data source rather than in memory.

---

---

10. GARBAGE COLLECTION (GC)

Definition

• Automatic memory management system

• Frees memory of objects that are no longer reachable

---

Key Concept — Reachability

Roots:
- stack variables
- static fields
- CPU registers

GC:
    marks reachable objects
    removes unreachable ones

---

Example

var obj = new Person();

Stack:
obj → 0x100

Heap:
0x100 → Person

---

obj = null;

Heap object now unreachable → eligible for GC

---

Generational Model

Gen0 → new objects
Gen1 → survivors
Gen2 → long-lived

---

Flow

New object → Gen0

If survives:
    → Gen1
    → Gen2

---

Collection Behavior

Generation	Frequency	Cost
Gen0	frequent	cheap
Gen1	medium	moderate
Gen2	rare	expensive

---

GC Phases

1. Mark

Traverse object graph
Mark reachable objects

---

2. Sweep

Remove unreachable objects

---

3. Compact

Move objects to remove gaps

---

Example — Compaction

Before:
[Obj][free][Obj][free]

After:
[Obj][Obj][free space]

---

Large Object Heap (LOH)

• Objects > ~85 KB

• Allocated directly in Gen2

• Not compacted frequently

---

Example

var arr = new byte[100000];

---

Trigger Conditions

• Allocation threshold exceeded

• Memory pressure

• System conditions

---

IDisposable vs GC

using var file = new FileStream(...);

---

GC:
    manages memory

IDisposable:
    releases unmanaged resources

---

Finalizer

~MyClass()
{
}

---

• Runs during GC

• Non-deterministic

• Performance cost

---

Memory Leak Example

static List<object> cache = new();

Objects always referenced → never collected

---

Interview Answer

The .NET garbage collector is a generational, mark-and-compact system that tracks object reachability starting from root references. Objects are allocated in Gen0 and promoted if they survive collections. Short-lived objects are collected frequently, while long-lived objects are collected less often to optimize performance. The GC manages memory automatically, but unmanaged resources must be handled using IDisposable.

---

---