Implement String Interning Pool to Reduce Memory

Topic Overview

One Copy Per Distinct String

Compilers, JVMs, and Python intern identifiers and literal strings so equality checks become pointer compares. Parsing millions of JSON keys benefits when the same field name like status appears on every row.

Intern Pool Design

Hash table maps string content to canonical storage. On insert, return existing pointer if hash and bytes match.

cCopy
Loading…

• Store length with hash to avoid strcmp on collision
• Immutable canonical strings enable pointer equality
• Lifetimes are usually process-long; plan teardown carefully
• Measure memory before/after on duplicate-heavy input

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a string intern table and show reduced memory on repetitive input. This exercise asks you to verify that equal strings share one address.

Your Task

Compilers, interpreters and parsers see the same identifiers thousands of times. String interning stores each distinct string once and hands out a small integer id. Equal strings then compare as equal ids, and duplicates cost nothing. Build an interning table on an open-addressing hash table with FNV-1a hashing and linear probing, which grows to keep the load factor at or below 3/4.

Input

cCopy
Loading…

Rules

• FNV-1a (32-bit): h = 2166136261; for each byte: h ^= byte; h *= 16777619 (mod 2^32).
• Slot = h & (capacity − 1). Probe the following slots with wrap-around until you find an equal string (existing) or an empty slot (new). The probe count is the number of slots examined, including the last one.
• Growth. Before inserting a new string, if (count + 1) * 4 > capacity * 3, double the capacity and reinsert every string in id order, then find the new string's slot. Ids are assigned 0, 1, 2… in order of first appearance.
• Stats:
  • unique strings, intern calls, capacity, load = count / capacity (rounded half up to 1 decimal), resizes, and total probes (summed over all intern calls);
  • bytes stored = the sum of (length + 1) over the unique strings, compared with keeping one copy per intern call.
• Errors: capacity: table already in use, capacity: power of two, 1..4096, and WORD -> table full (1024 strings at most).

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Compare full strings only after the hashes match, and store each string exactly once, in the id array. The table itself holds only ids.
2. Keep the capacity a power of two, so the slot index is a mask rather than a modulo.

Hidden tests cover repeated resizes starting from a capacity of 1, repeated words, lookups of missing words, and invalid capacity commands.