1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

LOAD FACTOR OVERHEAD EXAMPLE:
═══════════════════════════════════════════════════════════════════
 
Hash table with 750 elements
Target load factor: 0.75
Required buckets: 750 / 0.75 = 1000 buckets
 
MEMORY ALLOCATION:
┌───────────────────────────────────────────────────────────────────┐
│ Bucket Array (1000 slots × 8 bytes pointer) = 8,000 bytes         │
├───────────────────────────────────────────────────────────────────┤
│ 250 EMPTY SLOTS (25% wasted)                                      │
│ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░   │
│                                                                   │
│ These empty slots consume memory but hold nothing!                │
│ Empty slot cost: 250 × 8 = 2,000 bytes                            │
└───────────────────────────────────────────────────────────────────┘
 
AT DIFFERENT LOAD FACTORS:
─────────────────────────────────────────────────────────────────────
Load Factor  │ Buckets for 750 elements │ Empty Slots │ Empty %
─────────────┼──────────────────────────┼─────────────┼───────────
    1.0      │         750              │      0      │    0%
    0.75     │        1000              │    250      │   25%
    0.5      │        1500              │    750      │   50%
    0.25     │        3000              │   2250      │   75%
 
Lower load factor = Better performance = More wasted space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

CHAINING STRUCTURE (Conceptual):
═══════════════════════════════════════════════════════════════════
 
Bucket Array:
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│ Ptr(8B) │ Ptr(8B) │ Ptr(8B) │ Ptr(8B) │ Ptr(8B) │ Ptr(8B) │ ...
│  ●      │  null   │  ●      │  null   │  null   │  ●      │
└────┬────┴─────────┴────┬────┴─────────┴─────────┴────┬────┘
     │                   │                             │
     ▼                   ▼                             ▼
  ┌─────┐             ┌─────┐                       ┌─────┐
  │Entry│             │Entry│                       │Entry│
  │Key  │8B           │Key  │8B                     │Key  │8B
  │Value│8B           │Value│8B                     │Value│8B
  │Next │8B  ●───▶    │Next │8B null                │Next │8B null
  └─────┘    ┌─────┐  └─────┘                       └─────┘
             │Entry│
             │Key  │8B
             │Value│8B
             │Next │8B null
             └─────┘
 
MEMORY BREAKDOWN for entry (int key, int value):
─────────────────────────────────────────────────────────────────────
Actual data:           4 + 4 = 8 bytes (key + value)
Plus entry overhead:
  - Next pointer:      8 bytes
  - Object header:     12-16 bytes (JVM) or malloc header (C)
  - Alignment padding: 0-8 bytes
  
Total per entry:       ~32-40 bytes for 8 bytes of data!
Overhead ratio:        4-5× the actual data size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

POWER-OF-TWO SIZING EXAMPLE:
═══════════════════════════════════════════════════════════════════
 
Scenario: Need to store 1,025 elements, load factor 1.0
 
Ideal table size:     1,025 buckets
Power-of-two size:    2,048 buckets (next power of 2)
Wasted capacity:      1,023 buckets (50% waste!)
 
With load factor 0.75:
Required capacity:    1,025 / 0.75 = 1,367 buckets
Power-of-two size:    2,048 buckets
Wasted capacity:      681 buckets
 
Combined waste breakdown:
├── Load factor slack: 342 buckets (from 1,025 to 1,367)
└── Power-of-two:      681 buckets (from 1,367 to 2,048)
    Total waste:       1,023 buckets (50% of actual capacity!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

CHAINING HASH TABLE MEMORY FORMULA:
═══════════════════════════════════════════════════════════════════
 
TotalMemory = BucketArrayMemory + EntryMemory + MetadataMemory
 
Where:
  BucketArrayMemory = num_buckets × pointer_size
  EntryMemory = num_entries × (data_size + entry_overhead)
  MetadataMemory = size_field + load_factor_field + etc. (negligible)
 
EXPANDED:
  num_buckets = next_power_of_2(num_entries / target_load_factor)
  
  For 64-bit systems:
    pointer_size = 8 bytes
    entry_overhead = header + next_pointer + padding ≈ 32 bytes (Java)
 
 
EXAMPLE CALCULATION:
═══════════════════════════════════════════════════════════════════
 
Storing 1,000,000 user sessions:
  - Key: 8-byte session ID (long)
  - Value: 8-byte timestamp (long)
  - Data size: 16 bytes per entry
 
Java HashMap calculation:
  Target load factor: 0.75
  Required capacity: 1,000,000 / 0.75 = 1,333,334
  Actual capacity (power of 2): 2,097,152 (2^21)
  
  Bucket array: 2,097,152 × 8 = 16,777,216 bytes (16 MB)
  
  Entry nodes: 1,000,000 × (16 + 32) = 48,000,000 bytes (48 MB)
  (16 bytes data + 32 bytes overhead)
  
  TOTAL: ~64 MB for 16 MB of actual data
  OVERHEAD RATIO: 4× the data size
 
COMPARISON TO FLAT ARRAY:
  Sorted array of 1M entries: 1,000,000 × 16 = 16 MB
  Binary search still provides O(log n) = 20 comparisons
  
  Hash table: 64 MB for O(1) access
  Sorted array: 16 MB for O(log n) access
  
  Is O(1) vs O(log 1M) worth 4× memory?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

OPEN ADDRESSING MEMORY FORMULA:
═══════════════════════════════════════════════════════════════════
 
TotalMemory = num_buckets × (entry_size + status_byte)
 
Where entry is stored directly in bucket (no pointers)
 
EXAMPLE: Same 1,000,000 sessions, open addressing
  
  Required capacity (load factor 0.5 for open addressing): 2,000,000
  Actual capacity (power of 2): 2,097,152
  
  Entry size: 16 bytes (key + value) + 1 byte status
  
  Total: 2,097,152 × 17 ≈ 35.6 MB
  
  COMPARISON:
  ├── Chaining:       64 MB
  ├── Open addressing: 36 MB
  └── Sorted array:    16 MB
  
Open addressing is more memory-efficient but has other tradeoffs
(deletion complexity, clustering sensitivity)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

SCALING ANALYSIS: Building a web index
═══════════════════════════════════════════════════════════════════
 
Indexing 10 billion unique URLs (average 50 bytes each)
Mapping URL → document ID (8 bytes)
 
DATA SIZE: 10B × (50 + 8) = 580 GB (raw data)
 
HASH TABLE OVERHEAD:
 
Using Java HashMap:
  Per-entry overhead: ~32 bytes (header + pointers)
  Additional data: 10B × 32 = 320 GB of overhead alone!
  
  Plus bucket array:
    Load factor 0.75: need 13.3B buckets → 16B (power of 2)
    Bucket array: 16B × 8 bytes = 128 GB
    
  TOTAL: 580 + 320 + 128 = 1,028 GB (1+ TB!)
  
  vs. raw data: 580 GB
  OVERHEAD: 448 GB (77% bloat)
 
AT CLOUD PRICES ($0.10/GB-month for memory):
  Extra memory cost: 448 GB × $0.10 = $45/month per server
  For a cluster of 100 servers: $4,500/month = $54,000/year
  
  That overhead cost can fund entire engineering initiatives!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

EMBEDDED SYSTEM EXAMPLE: WiFi-enabled sensor
═══════════════════════════════════════════════════════════════════
 
Available RAM: 64 KB (65,536 bytes)
Reserved for stack/heap: 16 KB
Network buffers: 8 KB
Operating system: 8 KB
Available for application: 32 KB
 
REQUIREMENT: Store 500 sensor readings with timestamps
  Reading: 4-byte value + 4-byte timestamp = 8 bytes
  Raw data: 500 × 8 = 4,000 bytes (fits easily!)
 
WITH HASH TABLE (for fast lookup by timestamp):
  Minimum overhead per entry: 12 bytes (embedded implementation)
  Total per entry: 8 + 12 = 20 bytes
  Bucket array (load factor 0.75): 700 × 4 = 2,800 bytes
  
  TOTAL: 500 × 20 + 2,800 = 12,800 bytes
  
  Still fits... but uses 40% of available application memory!
  Leaves little room for other features.
 
ALTERNATIVE: Sorted array with binary search
  Storage: 500 × 8 = 4,000 bytes
  Lookup time: O(log 500) ≈ 9 comparisons
  
  Saves 8,800 bytes (69% less memory)
  9 comparisons at embedded CPU speed: ~microseconds (acceptable)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

CACHE SIZING EXAMPLE: Application cache
═══════════════════════════════════════════════════════════════════
 
Memory budget: 1 GB
Cached items: API responses (~2 KB each average)
 
IDEAL (no overhead):
  Capacity = 1 GB / 2 KB = 500,000 items
 
WITH HASH TABLE OVERHEAD:
  Per-entry overhead: ~40 bytes
  Effective item size: 2 KB + 40 bytes ≈ 2,088 bytes
  
  Bucket array (500K entries / 0.75 load factor):
    Size: 670,000 × 8 = 5.4 MB
    
  Actual capacity = (1 GB - 5.4 MB) / 2,088 ≈ 488,000 items
  
  LOST CAPACITY: 12,000 items (2.4% reduction)
 
This seems small, but for cache hit rates:
  If 12,000 items would have been accessed 10 times each:
  That's 120,000 cache MISSES per hour
  Each miss = database query = ~10ms latency
  
  Impact: 1,200 seconds of added latency per hour
  That's 20 minutes of user-facing delays!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import bisect
 
class SortedArrayMap:
    """
    Memory-efficient key-value store using sorted arrays.
    
    Space: O(n) — minimal overhead, just the data
    Lookup: O(log n) — binary search
    Insert: O(n) — must shift elements (use for read-heavy workloads!)
    """
    def __init__(self):
        self.keys = []
        self.values = []
    
    def get(self, key):
        """O(log n) lookup via binary search."""
        idx = bisect.bisect_left(self.keys, key)
        if idx < len(self.keys) and self.keys[idx] == key:
            return self.values[idx]
        return None
    
    def put(self, key, value):
        """O(n) insertion — shifts elements."""
        idx = bisect.bisect_left(self.keys, key)
        if idx < len(self.keys) and self.keys[idx] == key:
            self.values[idx] = value
        else:
            self.keys.insert(idx, key)
            self.values.insert(idx, value)
    
    def range_query(self, low, high):
        """O(log n + k) range query — bonus functionality!"""
        left = bisect.bisect_left(self.keys, low)
        right = bisect.bisect_right(self.keys, high)
        return list(zip(self.keys[left:right], self.values[left:right]))
 
 
# MEMORY COMPARISON (1 million 8-byte key-value pairs):
# 
# Hash table:    ~64 MB (with overhead)
# Sorted array:  ~16 MB (just the data)
# 
# Space saved: 48 MB (75% reduction)
# 
# Time tradeoff:
#   Lookup: O(1) → O(log 1M) = O(20) — still microseconds!
#   Insert: O(1) → O(n) — only use if inserts are rare

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

STORING URL PATHS:
═══════════════════════════════════════════════════════════════════
 
URLs:
  /api/users/list
  /api/users/create
  /api/users/delete
  /api/products/list
  /api/products/create
 
HASH TABLE: Each URL stored in full
  Size: 5 URLs × ~30 chars × 2 bytes (UTF-16) = 300 bytes data
  Plus ~160 bytes overhead (32 per entry)
  TOTAL: ~460 bytes
 
TRIE: Shared prefixes stored once
                    [/]
                     |
                   [api]
                   /    \
             [users]    [products]
             / | \        /    \
        [list][create]  [list]  [create]
              [delete]
 
Nodes: 10 (not 5 × 6 = 30 path segments)
Storage: ~200-250 bytes (depending on implementation)
 
SAVINGS: ~45% less memory
BONUS: Prefix-based operations (autocomplete, etc.) are O(k) not O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import hashlib
import math
 
class BloomFilter:
    """
    Space-efficient probabilistic set membership.
    
    False positives possible, false negatives impossible.
    Space: O(n) with small constant (bits, not bytes per element)
    """
    def __init__(self, expected_elements, false_positive_rate):
        # Optimal size calculation
        self.size = int(-expected_elements * math.log(false_positive_rate) 
                        / (math.log(2) ** 2))
        self.num_hashes = int(self.size / expected_elements * math.log(2))
        self.bits = [False] * self.size
    
    def _hashes(self, item):
        """Generate multiple hash values for an item."""
        hashes = []
        for i in range(self.num_hashes):
            h = hashlib.sha256(f"{item}{i}".encode()).hexdigest()
            hashes.append(int(h, 16) % self.size)
        return hashes
    
    def add(self, item):
        for h in self._hashes(item):
            self.bits[h] = True
    
    def might_contain(self, item):
        return all(self.bits[h] for h in self._hashes(item))
 
 
# SPACE COMPARISON: 1 million elements
# ═══════════════════════════════════════════════════════════════════
# 
# HashSet (Java, 8-byte elements):   ~40 MB
# Bloom filter (1% false positive):  ~1.2 MB
# 
# SPACE SAVINGS: 97%!
# 
# Tradeoff: 1% of "yes, it's there" answers are wrong
# Use case: Cache checking ("might be in cache, worth looking")
#           Spam filtering ("might be spam, check further")
#           Database queries ("might exist, query database")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.lang.instrument.Instrumentation;
import java.util.HashMap;
 
// Method 1: Using Java Object Layout (JOL) library
// Add dependency: org.openjdk.jol:jol-core:0.16
 
import org.openjdk.jol.info.GraphLayout;
 
public class HashMapMemory {
    public static void main(String[] args) {
        HashMap<Long, Long> map = new HashMap<>();
        
        // Populate with 100,000 entries
        for (long i = 0; i < 100_000; i++) {
            map.put(i, i * 2);
        }
        
        // Measure deep size (including all referenced objects)
        long size = GraphLayout.parseInstance(map).totalSize();
        System.out.println("HashMap size: " + size + " bytes");
        System.out.println("Per entry: " + (size / 100_000) + " bytes");
        
        // Expected output approximately:
        // HashMap size: ~5,600,000 bytes (5.6 MB)
        // Per entry: ~56 bytes
        // 
        // For 16 bytes of data (two longs), that's 3.5× overhead!
    }
}
 
// Method 2: VisualVM or JMC profiling
// 1. Attach profiler to running JVM
// 2. Take heap dump
// 3. Analyze HashMap and HashMap$Node instances
// 4. Compare retained size to expected data size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import sys
from pympler import asizeof  # pip install Pympler
 
def measure_dict_memory():
    # Create dict with 100,000 entries
    d = {i: i * 2 for i in range(100_000)}
    
    # Method 1: sys.getsizeof (shallow - just the dict object)
    shallow_size = sys.getsizeof(d)
    print(f"Shallow size: {shallow_size:,} bytes")
    
    # Method 2: pympler asizeof (deep - includes all referenced objects)
    deep_size = asizeof.asizeof(d)
    print(f"Deep size: {deep_size:,} bytes")
    print(f"Per entry: {deep_size // 100_000} bytes")
    
    # Compare to data alone
    data_size = 100_000 * (sys.getsizeof(0) * 2)  # key + value
    print(f"Raw data size: {data_size:,} bytes")
    print(f"Overhead ratio: {deep_size / data_size:.2f}x")
 
measure_dict_memory()
 
# Typical output (Python 3.9+):
# Shallow size: 5,242,960 bytes
# Deep size: 8,697,472 bytes  
# Per entry: 86 bytes
# Raw data size: 5,600,000 bytes (28 bytes per int × 2)
# Overhead ratio: 1.55x (Python dicts are quite efficient)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// Method 1: Process memory (rough estimate)
function measureMapMemory() {
    // Force GC if available (node --expose-gc)
    if (global.gc) global.gc();
    
    const before = process.memoryUsage().heapUsed;
    
    const map = new Map();
    for (let i = 0; i < 100000; i++) {
        map.set(i, i * 2);
    }
    
    if (global.gc) global.gc();
    const after = process.memoryUsage().heapUsed;
    
    const used = after - before;
    console.log(`Map memory: ${(used / 1024 / 1024).toFixed(2)} MB`);
    console.log(`Per entry: ${(used / 100000).toFixed(0)} bytes`);
}
 
measureMapMemory();
 
// Typical output:
// Map memory: 7.62 MB
// Per entry: 80 bytes
//
// For 16 bytes of data per entry (two numbers), that's 5× overhead!
 
// Method 2: Chrome DevTools
// 1. Open Chrome DevTools in Node.js (node --inspect)
// 2. Take heap snapshot
// 3. Filter for Map objects
// 4. Compare shallow vs retained size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// BAD: Let HashMap grow dynamically
HashMap<String, Integer> map = new HashMap<>();
// Initial capacity: 16, will resize at 12 elements (75% load factor)
// Each resize: allocates new array, copies elements, then frees old
// During resize: using 3× expected memory temporarily!
for (int i = 0; i < 1_000_000; i++) {
    map.put("key" + i, i);  // Multiple resizes: 16→32→64→...→2M
}
 
// GOOD: Pre-size based on expected elements
int expectedElements = 1_000_000;
float loadFactor = 0.75f;
int initialCapacity = (int) (expectedElements / loadFactor) + 1;
 
HashMap<String, Integer> presizedMap = new HashMap<>(initialCapacity, loadFactor);
// No resizing needed; memory usage is predictable and minimal
for (int i = 0; i < 1_000_000; i++) {
    presizedMap.put("key" + i, i);
}
 
// Memory difference during population:
// Dynamic: peaks at 3× final size during resizes
// Pre-sized: constant at final size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// Standard HashMap: BOXING OVERHEAD
import java.util.HashMap;
 
HashMap<Integer, Integer> boxed = new HashMap<>();
// Each Integer object: 16 bytes (4 bytes int + 12 bytes header)
// Per entry overhead: ~56 bytes for 8 bytes of data!
 
// Alternative: Eclipse Collections
import org.eclipse.collections.impl.map.mutable.primitive.IntIntHashMap;
 
IntIntHashMap primitive = new IntIntHashMap();
// No boxing: ints stored directly
// Per entry overhead: ~12-16 bytes for 8 bytes of data
 
 
// MEMORY COMPARISON (1 million int→int mappings):
// 
// HashMap<Integer, Integer>:     ~70 MB
// IntIntHashMap:                 ~25 MB
// 
// SAVINGS: 64% less memory!
 
 
// Other primitive collection libraries:
// - fastutil (IntInt2HashMap, Long2ObjectOpenHashMap, etc.)
// - koloboke (HashIntIntMap, HashObjLongMap, etc.)
// - Trove (TIntIntHashMap, TLongObjectHashMap, etc.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# KEY INTERNING: Reuse string instances
# Python already interns short strings, but explicit interning helps:
 
import sys
 
# Without interning:
data1 = [{"status": "active"} for _ in range(100000)]
# Each "active" might be a separate string object
 
# With interning:
STATUS_ACTIVE = sys.intern("active")
STATUS_INACTIVE = sys.intern("inactive")
 
data2 = [{"status": STATUS_ACTIVE} for _ in range(100000)]
# All dicts share the SAME string object
 
 
# VALUE COMPRESSION: Store encoded values
import struct
 
class CompactUserCache:
    """
    Store user data compactly instead of as dict per user.
    """
    def __init__(self):
        # Instead of: {user_id: {"age": 25, "score": 100, "verified": True}}
        # Store as:   {user_id: packed_bytes}
        self.data = {}
    
    def set_user(self, user_id, age, score, verified):
        # Pack into 5 bytes instead of ~200 bytes for nested dict
        packed = struct.pack("BHH", age, score, 1 if verified else 0)
        self.data[user_id] = packed
    
    def get_user(self, user_id):
        packed = self.data.get(user_id)
        if packed:
            age, score, verified = struct.unpack("BHH", packed)
            return {"age": age, "score": score, "verified": bool(verified)}
        return None
 
# Memory savings: ~10-40× for small structured values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

OFF-HEAP HASH TABLE OPTIONS:
═══════════════════════════════════════════════════════════════════
 
Java:
├── Chronicle Map     — Memory-mapped hash map, survives restarts
├── MapDB             — Off-heap collections with optional persistence
├── Caffeine          — Can use off-heap storage with custom serialization
└── Hazelcast         — Distributed, supports off-heap storage
 
C/C++:
├── LMDB              — Lightning Memory-Mapped Database (hash + B-tree)
├── RocksDB           — Embedded key-value with LSM tree
└── LevelDB           — Similar to RocksDB
 
Benefits of off-heap:
+ No GC pressure (no object headers, no garbage collection)
+ Can exceed heap size limits
+ Can be memory-mapped for persistence
+ Minimal per-entry overhead (just data + minimal bookkeeping)
 
Costs:
- Serialization overhead for complex objects
- Manual memory management complexity
- Cannot store managed references
- May need custom implementations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

DATA STRUCTURE TRADEOFF SPECTRUM:
═══════════════════════════════════════════════════════════════════
 
                    ◄───── MEMORY EFFICIENT ─────┼───── SPEED EFFICIENT ─────►
                    
                    Bloom      Sorted    Compact    Standard   Cache-
                    Filter     Array     Hash       Hash       Aligned
                    │          │         Table      Table      Hash
                    │          │         │          │          │
                    │          │         │          │          │
Space per entry:    1-2 bits   8-16B     16-24B     40-80B     100B+
                    │          │         │          │          │
Lookup time:        O(k)       O(log n)  O(1)       O(1)       O(1)
                    hashes     comparisons amortized amortized guaranteed
                    │          │         │          │          │
Use case:           Cache      Read-     General    Standard   Latency
                    lookups    heavy     purpose    use        critical
 
 
EXAMPLE DECISION PROCESS:
─────────────────────────────────────────────────────────────────────
 
Scenario: URL deduplication for web crawler
 
Requirements:
├── 1 billion URLs to check
├── Fast membership testing (is URL already crawled?)
├── Memory budget: 10 GB
├── False positives acceptable (recrawl is OK, missing is not)
 
Option analysis:
├── Standard HashMap<String, Boolean>:
│   Memory: ~100 bytes/entry × 1B = 100 GB ❌ (exceeds budget)
│   
├── Sorted array + binary search:
│   Memory: ~50 bytes/entry × 1B = 50 GB ❌ (exceeds budget)
│   
├── Bloom filter (1% false positive):
│   Memory: ~10 bits/entry × 1B = 1.25 GB ✓
│   Speed: O(k) hash lookups ✓
│   
CHOICE: Bloom filter — 10× under budget, meets all requirements