Hash Structures

Everything placed in the store up to this point has been a single piece: a session record is a whole, a counter is a number, a list entry is a string. The library’s actual record is not like that. A book has a title, an author, a shelf code, a status, a loan count, a date added, and a number. These fields also do not change at the same rate: status changes many times a day, the title never changes.

In a holistic value, the store has no concept of a field; updating a single field means reading the whole record and writing it back — and the lost-update problem measured in the previous lesson comes from exactly this. The hash structure is the alternative: the store knows the record’s fields, reads by name, writes by name. This lesson asks the price of that knowledge.

The Same Record, Three Shapes

Three shapes are compared. A holistic value holds the record as a single serialized string. A dense hash holds the fields consecutively in one block, but the store knows the field boundaries; a single-field request is served by scanning the block. A hash structure holds every field as its own entry and accesses it by name in a single step.

DS1: the catalog carries 200,000 books, each record has seven fields, and field values come from deterministic functions. DS2: overhead per structure is 56 bytes, overhead per field is 40 bytes (hash bucket pointer, pointers for the field name and value, length fields). DS3: bytesRead and bytesWritten are the bytes the store touches for that operation, roundTrips is the client’s call count, steps is the number of fields resolved or compared. DS4: during the day, 119,993 loan/return events update two fields (status and loan count), 400,000 status queries read one field, 60,000 book pages read the whole record.

// memory/hash.mjs — the same book record in three shapes. read/written = bytes the
// store touches for that operation, roundTrips = client call count, steps = field
// lookup/comparison count. The workload is deterministic.
const OVERHEAD = 56, FIELD_OVERHEAD = 40, BOOKS = 200_000;   // DS2
const bl = (x) => Buffer.byteLength(String(x));
const key = (i) => `book:${100_000 + i}`;
const record = (i) => ({
  title: `Notes on Book ${100_000 + i}`, author: `Author ${i % 997}`,
  shelf: `K-${1 + (i % 20)}-${String(i % 400).padStart(3, "0")}`,
  status: i % 3 === 0 ? "on_loan" : "on_shelf", loan_count: String(1 + (i * 7919) % 4096),
  added: `20${10 + (i % 15)}-${String(1 + (i % 12)).padStart(2, "0")}-14`,
  isbn: String(9_780_000_000_000 + i),
});

class HolisticStore {                            // the value is a single piece: the store does not know fields
  #table = new Map(); bytesRead = 0; bytesWritten = 0; roundTrips = 0; steps = 0;
  put(key, record) { this.#table.set(key, JSON.stringify(record)); }
  readAll(key) { this.roundTrips += 1; const s = this.#table.get(key); this.bytesRead += bl(s);
    const record = JSON.parse(s); this.steps += Object.keys(record).length; return record; }   // every field is parsed
  readField(key, field) { return this.readAll(key)[field]; }        // the whole value is read, one field used
  writeField(key, field, value) { const record = this.readAll(key); record[field] = value;      // read-modify-write
    const s = JSON.stringify(record); this.roundTrips += 1; this.bytesWritten += bl(key) + bl(s); this.#table.set(key, s); }
  bytes() { let b = 0; for (const [key, s] of this.#table) b += bl(key) + bl(s) + OVERHEAD; return b; }
}

class DenseHashStore {                          // fields sit consecutively in one blob; the store knows fields
  #table = new Map(); bytesRead = 0; bytesWritten = 0; roundTrips = 0; steps = 0;
  put(key, record) { this.#table.set(key, Object.entries(record).map(([k, v]) => `${k}=${v}`).join(";")); }
  #find(s, field) { for (const part of s.split(";")) { this.steps += 1; if (part.startsWith(`${field}=`)) return part; } return null; }
  readAll(key) { this.roundTrips += 1; const s = this.#table.get(key); this.bytesRead += bl(s);
    return Object.fromEntries(s.split(";").map((part) => part.split("="))); }
  readField(key, field) { this.roundTrips += 1; const s = this.#table.get(key); this.bytesRead += bl(s);
    const part = this.#find(s, field); return part === null ? undefined : part.slice(field.length + 1); }
  writeField(key, field, value) { this.roundTrips += 1; const s = this.#table.get(key); this.bytesRead += bl(s);
    const updated = s.split(";").map((part) => { this.steps += 1; return part.startsWith(`${field}=`) ? `${field}=${value}` : part; }).join(";");
    this.bytesWritten += bl(key) + bl(updated); this.#table.set(key, updated); }                        // the blob is rewritten
  bytes() { let b = 0; for (const [key, s] of this.#table) b += bl(key) + bl(s) + OVERHEAD; return b; }
}

class HashStore {                               // every field is its own entry: accessed by name
  #table = new Map(); bytesRead = 0; bytesWritten = 0; roundTrips = 0; steps = 0;
  put(key, record) { this.#table.set(key, new Map(Object.entries(record).map(([k, v]) => [k, String(v)]))); }
  readAll(key) { this.roundTrips += 1; const fields = this.#table.get(key);
    for (const [k, v] of fields) { this.steps += 1; this.bytesRead += bl(k) + bl(v); } return Object.fromEntries(fields); }
  readField(key, field) { this.roundTrips += 1; this.steps += 1;
    const v = this.#table.get(key).get(field); this.bytesRead += bl(v); return v; }
  writeField(key, field, value) { this.roundTrips += 1; this.steps += 1; this.bytesWritten += bl(key) + bl(field) + bl(value);
    this.#table.get(key).set(field, String(value)); }
  bytes() { let b = 0;
    for (const [key, fields] of this.#table) { b += bl(key) + OVERHEAD;
      for (const [k, v] of fields) b += bl(k) + bl(v) + FIELD_OVERHEAD; }
    return b; }
}

const sample = record(427);
console.log(`sample ${key(427)}: ${Object.keys(sample).length} fields, JSON ${bl(JSON.stringify(sample))} bytes, ` +
  `field names ${Object.keys(sample).reduce((t, k) => t + bl(k), 0)} bytes, ` +
  `field values ${Object.values(sample).reduce((t, v) => t + bl(v), 0)} bytes`);

const stores = [["holistic value", new HolisticStore()], ["dense hash", new DenseHashStore()],
  ["hash structure", new HashStore()]];
for (const [, store] of stores) for (let i = 1; i <= BOOKS; i += 1) store.put(key(i), record(i));

// daily load: 119,993 loan/return events update two fields, 400,000 status queries, 60,000 full reads
const LOANS = 119_993, STATUS_QUERIES = 400_000, PAGE_VIEWS = 60_000;
for (const [, store] of stores) {
  for (let j = 0; j < LOANS; j += 1) { const i = 1 + (j * 4241) % BOOKS;
    store.writeField(key(i), "status", j % 2 === 0 ? "on_loan" : "on_shelf");
    store.writeField(key(i), "loan_count", String(1 + (i * 7919) % 4096)); }
  for (let j = 0; j < STATUS_QUERIES; j += 1) store.readField(key(1 + (j * 7919) % BOOKS), "status");
  for (let j = 0; j < PAGE_VIEWS; j += 1) store.readAll(key(1 + (j * 4241) % BOOKS));
}

console.log(`\n${BOOKS} books; daily load ${2 * LOANS} field writes, ${STATUS_QUERIES} field reads, ${PAGE_VIEWS} full reads`);
console.log(`${"shape".padEnd(16)}${"bytes held".padStart(14)}${"per record".padStart(13)}` +
  `${"written".padStart(10)}${"read".padStart(11)}${"round trips".padStart(13)}${"steps".padStart(9)}`);
for (const [name, store] of stores)
  console.log(name.padEnd(16) + String(store.bytes()).padStart(14) + (store.bytes() / BOOKS).toFixed(1).padStart(13) +
    String(store.bytesWritten).padStart(10) + String(store.bytesRead).padStart(11) + String(store.roundTrips).padStart(13) +
    String(store.steps).padStart(9));

sample book:100427: 7 fields, JSON 156 bytes, field names 41 bytes, field values 72 bytes

200000 books; daily load 239986 field writes, 400000 field reads, 60000 full reads
shape               bytes held   per record   written       read  round trips    steps
holistic value        44547129        222.7  39998208  109012753       939972  4899902
dense hash            38547129        192.7  32798628   88013173       699986  3279902
hash structure        91947129        459.7   5907195    9786807       699986  1059986

The hash structure’s price shows up in the first column: the same 200,000 records hold 44.5 MB as a holistic value and 91.9 MB as a hash structure, 222.7 bytes per record against 459.7. The difference is a single line item: each of the seven fields is its own entry, and every entry carries 40 bytes of overhead along with a copy of the field name. Of the 237-byte increase per record, 280 bytes is field overhead — meaning more space than the record itself goes toward recognizing the fields separately.

What that buys is in the other four columns. A single-field update writes the entire record in a holistic value; 40.0 MB is written over the day. In a hash structure, only the key, the field name, and the new value are written: 5.9 MB, 6.8 times less. The gap on the read side is larger. Each of the 400,000 status queries reads out the entire 156-byte record in a holistic value; the total is 109.0 MB against 9.8 MB in a hash structure — 11.1 times. Round trips also fall: because a field update is read-modify-write in a holistic value, it needs two calls, 939,972 against 699,986. These 239,986 extra round trips are not just a traffic line item; the previous lesson’s lost update arises from exactly this gap. In a hash structure, a field update is a single call and cannot be split.

The middle row carries the lesson’s surprise. Even though the dense hash holds fields in a single block, it takes up less space than the holistic value (192.7 bytes, because there is no delimiter and quote overhead) while also preserving the concept of a field: round trips drop to 699,986, and updates become unsplittable. Across a seven-field record, there is no single column where the holistic value beats the dense hash. What the dense hash pays for is the step column: finding a single field means scanning the block, 3,279,902 steps. The hash structure finishes the same job in 1,059,986 steps.

Where the Threshold Is

At seven fields, the dense hash is a good choice; the scan is four steps. As field count grows, this changes. DS5: for comparison, the field name is 9 bytes and the field value is 7 bytes, and record kinds in the catalog come in four different sizes.

// memory/threshold.mjs — as field count grows, dense and hash representations
// diverge, and the catalog-wide cost of a threshold policy. All numbers are structural.
const OVERHEAD = 56, FIELD_OVERHEAD = 40;
const fieldName = (j) => `field_${String(j).padStart(3, "0")}`;
const fieldValue = (j) => String(1_000_000 + j * 7919);
const bl = (x) => Buffer.byteLength(String(x));
const KEY = bl("book:100427");

const denseBytes = (f) => KEY + OVERHEAD +
  bl(Array.from({ length: f }, (_, j) => `${fieldName(j)}=${fieldValue(j)}`).join(";"));
const hashBytes = (f) => KEY + OVERHEAD +
  Array.from({ length: f }, (_, j) => bl(fieldName(j)) + bl(fieldValue(j)) + FIELD_OVERHEAD).reduce((t, x) => t + x, 0);

console.log(`field name ${bl(fieldName(0))} bytes, field value ${bl(fieldValue(0))} bytes, ` +
  `field overhead ${FIELD_OVERHEAD} bytes, key ${KEY} bytes`);
console.log(`\n${"fields".padStart(6)}${"dense bytes".padStart(13)}${"hash bytes".padStart(12)}${"ratio".padStart(7)}` +
  `${"dense access steps".padStart(20)}${"dense field write".padStart(19)}${"hash field write".padStart(18)}`);
for (const f of [4, 7, 16, 64, 256]) {
  const dense = denseBytes(f), hash = hashBytes(f);
  console.log(String(f).padStart(6) + String(dense).padStart(13) + String(hash).padStart(12) +
    (hash / dense).toFixed(2).padStart(7) + `${((f + 1) / 2).toFixed(1)} / ${f}`.padStart(20) +
    String(dense - OVERHEAD).padStart(19) +
    String(KEY + bl(fieldName(0)) + bl(fieldValue(0))).padStart(18));
}

// catalog: four record kinds, three policies
const kinds = [["book record", 200_000, 7], ["member profile", 20_000, 12],
  ["branch daily counter", 5, 24], ["popular book tag counter", 2_000, 256]];
console.log(`\n${"record kind".padEnd(29)}${"count".padStart(8)}${"fields".padStart(7)}` +
  `${"all dense".padStart(13)}${"all hash".padStart(13)}${"threshold 64".padStart(14)}`);
let totalDense = 0, totalHash = 0, totalThreshold = 0;
for (const [name, n, f] of kinds) {
  const dense = n * denseBytes(f), hash = n * hashBytes(f), chosen = f <= 64 ? dense : hash;
  totalDense += dense; totalHash += hash; totalThreshold += chosen;
  console.log(name.padEnd(29) + String(n).padStart(8) + String(f).padStart(7) +
    String(dense).padStart(13) + String(hash).padStart(13) + String(chosen).padStart(14));
}
console.log("total".padEnd(29) + "".padStart(8) + "".padStart(7) +
  String(totalDense).padStart(13) + String(totalHash).padStart(13) + String(totalThreshold).padStart(14));
console.log(`threshold 64: %${(100 * totalThreshold / totalHash).toFixed(1)} of all-hash, %` +
  `${(100 * totalThreshold / totalDense).toFixed(1)} of all-dense; worst-case field access is 64 steps`);

field name 9 bytes, field value 7 bytes, field overhead 40 bytes, key 11 bytes

fields  dense bytes  hash bytes  ratio  dense access steps  dense field write  hash field write
     4          138         291   2.11             2.5 / 4                 82                27
     7          192         459   2.39             4.0 / 7                136                27
    16          354         963   2.72            8.5 / 16                298                27
    64         1218        3651   3.00           32.5 / 64               1162                27
   256         4674       14403   3.08         128.5 / 256               4618                27

record kind                     count fields    all dense     all hash  threshold 64
book record                    200000      7     38400000     91800000      38400000
member profile                  20000     12      5640000     14780000       5640000
branch daily counter                5     24         2490         7055          2490
popular book tag counter         2000    256      9348000     28806000      28806000
total                                            53390490    135393055      72848490
threshold 64: %53.8 of all-hash, %136.4 of all-dense; worst-case field access is 64 steps

The upper table sets two curves side by side. The memory ratio climbs from 2.11 to 3.08 as field count grows — the dense representation’s gain increases further on larger records. But two columns grow in opposite directions. In the dense representation, finding a field averages (f+1)/2 steps, rising to 128.5 steps at 256 fields and 256 steps in the worst case. Sharper still is the single-field write: the dense representation rewrites the entire block, 4,618 bytes at 256 fields. The same write in a hash structure is 27 bytes, independent of field count. The write multiplier from the list lesson returns here, and it grows in direct proportion to field count.

The lower table gives the decision at catalog scale. Keeping everything dense costs 53.4 MB, keeping everything as a hash structure costs 135.4 MB. A threshold policy — dense below 64 fields, hash structure above — holds steady at 72.8 MB: 53.8 percent of keeping everything as a hash structure. The price of the 62.5 MB saved in between is at most a 7-step scan across the 200,000 book records. The same policy, by keeping the 2,000 tag counters as a hash structure, avoids a 256-step scan and a 4,618-byte write. The threshold policy spends 36.4 percent more memory than keeping everything dense, and in return it caps the worst-case field access at 64 steps instead of 256. The decision is not choosing one representation over the other, it is choosing where the line runs.

Summary

• In a holistic value, the store has no concept of a field: a single-field update reads and writes the entire record and needs two round trips; the lost update arises from exactly this gap.
• 200,000 records hold 44.5 MB as a holistic value and 91.9 MB as a hash structure. Most of the 237-byte increase per record is the 40-byte overhead per field.
• What the hash structure buys is a drop in daily write traffic from 40.0 MB to 5.9 MB, in read traffic from 109.0 MB to 9.8 MB, and in round trips from 939,972 to 699,986.
• At seven fields, the dense hash loses to the holistic value in no column: 192.7 bytes, the same round-trip count, and an unsplittable field update. The only price it pays is the scan step count (3,279,902 against 1,059,986).
• As field count grows, the dense representation’s memory gain increases (ratio rising from 2.11 to 3.08), but access rises to an average of (f+1)/2 steps, and a single-field write climbs to 4,618 bytes at 256 fields; the same write is 27 bytes in a hash structure.
• A threshold policy (dense up to 64 fields) holds 72.8 MB catalog-wide: 53.8 percent of keeping everything as a hash structure, 136.4 percent of keeping everything dense. What that buys is capping the worst-case access at 64 steps.

Next Step

The hash structure separated a record’s fields, but they all still belonged to a single record. Some of the library’s questions do not belong to a single record: “is this book among the ones currently on loan,” “is this member on the fine list,” “which twenty books are borrowed the most.” The first is a membership question and its answer is yes or no; the last is a rank question and its answer is a sorted list. The next lesson takes up these two structures and measures three things: the step count of a membership check, the step count of a rank query in a sorted set, and the bytes-per-entry cost of both.