29:null 2a:["$","title",null,{"children":"Hash table with separate chaining | Claudio Esperança | Observable"}] 2f:T73e,class HashTable { constructor(size = 0, lambda_min = 0.5, lambda_max = 0.75, size_min = 4) { this.table = new Array(Math.max(size, size_min)); this.n = 0; this.h = makeHash(this.m); Object.assign(this, { lambda_min, lambda_max, size_min }); } get m() { return this.table.length; } get lambda() { return this.n / this.m; } find(key) { let i = this.h(key); let cell = this.table[i]; while (cell && cell.key != key) cell = cell.next; if (cell) return cell.value; return null; } insert(key, value) { let i = this.h(key); let cell = this.table[i]; while (cell && cell.key != key) cell = cell.next; if (cell) throw `${key} already in table`; this.n++; this.table[i] = { key, value, next: this.table[i] }; if (this.lambda > this.lambda_max) this.rehash(); } delete(key) { let i = this.h(key); let cell = this.table[i]; let prev = null; while (cell && cell.key != key) { prev = cell; cell = cell.next; } if (!cell) throw `${key} not in table`; this.n--; if (prev) { prev.next = cell.next; } else { if (cell) this.table[i] = cell.next; else this.table[i] = undefined; } if (this.lambda < this.lambda_min) this.rehash(); } *cells() { for (let cell of this.table) { while (cell) { yield cell; cell = cell.next; } } } rehash() { const lambda_0 = (this.lambda_max + this.lambda_min) / 2; const newSize = Math.max(this.size_min, Math.round(this.n / lambda_0)); if (newSize == this.m) return; const newTable = new HashTable( newSize, this.lambda_min, this.lambda_max, this.size_min ); for (let cell of this.cells()) { newTable.insert(cell.key, cell.value); } Object.assign(this, newTable); } }30:T453,function showtable(ht) { const table = ht.table, m = ht.m; const getRow = (row) => { const result = []; for (let i = 0; i < m; i++) { let cell = table[i]; for (let j = 0; j < row; j++) { if (cell) cell = cell.next; else break; } if (cell) result[i] = `${cell.key}`; } return result; }; let row = 0; let gv = ``; gv += ``; for (let i = 0; i < m; i++) { gv += `${i}`; } gv += ``; do { let cells = getRow(row); if (cells.length == 0) break; let tds = ""; for (let i = 0; i < m; i++) { let cell = cells[i]; if (cell) tds += `${cell}`; else if (row == 0) tds += `-`; else tds += ``; } gv += `` + tds + `\n`; row++; } while (row < 10); return `\n${gv}

`; }31:[] 2d:{"id":"2d9c3c3724d255bc","slug":"hash-table-with-separate-chaining","title":"Hash table with separate chaining","thumbnail":"7e190f2a829ec4166952a2c59f882083e0769cd6b0d08a05114144c81f8b107c","access_level":"public","create_time":"$D2024-06-11T14:12:24.325Z","update_time":"$D2024-06-11T22:06:57.673Z","view_time":null,"first_public_time":"$D2024-06-11T19:55:57.286Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024"},"version":115,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"},{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":{"id":"25c80ce374eaa429","slug":"data-structures","title":"Data Structures","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"type":"notebook","body":{"title":"Hash table with separate chaining","cells":[{"id":0,"value":"# Hash table with separate chaining","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":102,"value":"viewof reset = Inputs.button(\"reset\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"demo = {\n reset;\n let ht = new HashTable();\n let result = htl.html`

`;\n let inserted = [];\n for (let i = 0; i < 8; i++) {\n const k = 1 + Math.floor(random() * 100);\n if (!ht.find(k)) {\n result.append(md`**Inserting ${k}**`);\n ht.insert(k, k);\n inserted.push(k);\n result.append(html`${showtable(ht)}`);\n }\n }\n d3.shuffle(inserted);\n for (let k of inserted.slice(1)) {\n result.append(md`**Removing ${k}**`);\n ht.delete(k);\n result.append(html`${showtable(ht)}`);\n }\n return result;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"
\n## Implementation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"largePrimes = [\n 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109,\n 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221,\n 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341,\n 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437,\n 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547,\n 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679,\n 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791,\n 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901,\n 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"random = d3.randomLcg(1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"function makeHash(m) {\n if (m > largePrimes[0]) throw \"Table too large\";\n const p = largePrimes[Math.floor(random() * largePrimes.length)];\n const a = 1 + Math.floor(random() * (p - 1));\n const b = Math.floor(random() * p);\n return (x) => ((a * x + b) % p) % m;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2e:"$2d:body"