31:T879,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)); for (let i = 0; i < this.table.length; i++) this.table[i] = "E"; this.n = 0; this.deleted = 0; this.h = makeHash(this.m); this.g = makeHash2(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]; let j = this.g(key); while (cell !== "E" && (cell === "D" || cell.key != key)) { i = (i + j) % this.m; cell = this.table[i]; } if (cell !== "E" && cell !== "D") return cell.value; return null; } insert(key, value) { let i = this.h(key); let cell = this.table[i]; let j = this.g(key); while (cell !== "E" && cell !== "D") { if (cell.key == key) throw `${key} already in table`; i = (i + j) % this.m; cell = this.table[i]; } this.n++; this.table[i] = { key, value }; if (this.lambda > this.lambda_max) this.rehash(); } delete(key) { let i = this.h(key); let cell = this.table[i]; let j = this.g(key); while (cell !== "E") { if (cell !== "D" && cell.key == key) break; i = (i + j) % this.m; cell = this.table[i]; } if (cell == "E") throw `${key} not in table`; this.n--; this.deleted++; this.table[i] = "D"; if ( this.lambda < this.lambda_min || this.deleted / this.m >= 1 - this.lambda ) this.rehash(); } *cells() { for (let cell of this.table) { if (cell != "D" && cell != "E") yield cell; } } rehash() { const lambda_0 = (this.lambda_max + this.lambda_min) / 2; let 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); } }32:[] 2f:{"title":"Hash table with open addressing and double hashing","cells":[{"id":0,"value":"# Hash table with open addressing and double hashing\n\n_Note_: in this implementation we choose as a secondary hashing function (g) a prime greater than the table size, which is assumed to be smaller than 10000.","pinned":false,"hidden":false,"mode":"md"},{"id":102,"value":"viewof reset = Inputs.button(\"reset\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"demo = {\n reset;\n let ht = new HashTable(4, 0.3, 0.6);\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 console.log({ k, g: ht.g(k), ht });\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"},{"id":155,"value":"
\n## Implementation","pinned":false,"hidden":false,"mode":"md"},{"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"},{"id":127,"value":"smallPrimes = [\n 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,\n 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,\n 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,\n 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,\n 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,\n 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,\n 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,\n 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,\n 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,\n 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,\n 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":72,"value":"random = d3.randomLcg(1)","pinned":true,"hidden":false,"mode":"ojs"},{"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"},{"id":125,"value":"function makeHash2(m) {\n // let h = makeHash(m);\n // return (x) => {\n // let d = h(x);\n // if (d == 0 || m % d == 0) return 1;\n // return d;\n // };\n let p = largePrimes[Math.floor(random() * largePrimes.length)];\n return (x) => p;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":5,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":18,"value":"function showtable(ht) {\n const table = ht.table,\n m = ht.m;\n let gv = ``;\n gv += ``;\n for (let i = 0; i < m; i++) {\n gv += `${i}`;\n }\n gv += ``;\n let tds = \"\";\n for (let i = 0; i < m; i++) {\n let cell = table[i];\n if (cell.key) cell = cell.key;\n tds += `${cell}`;\n }\n gv += `` + tds + `\\n`;\n return `\\n${gv}

`;\n}","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}