2c:null 2d:["$","title",null,{"children":"An unholy PACT 𖤐 Combining Tries and Cuckoo hashing into one persistent datastructure. | port.studio | Observable"}] 32:T9dd,HashTable = class { constructor() { this.keyBits = 0n; this.hashBits = 0n; this.hasherByKey = new Array(256); this.hasherByHash = new Array(256); this.sizeExp = 2; this.buckets = new Array(1 << this.sizeExp); this.random = 0; } get(key) { if (this.keyBits & (1n << BigInt(key))) { const expMask = ~(0b11111111 << this.sizeExp); const hi = this.hasherByKey[key]; const hash = hashers[hi][key]; return this.buckets[hash & expMask]; } return undefined; } displace(key) {} put(key, value) { this.random = pearsonTable[this.random ^ value]; let keyBit = 1n << BigInt(key); if (this.keyBits & keyBit) return true; let displacementCount = 0; while (true) { const expMask = ~(0b11111111 << this.sizeExp); let displacedHasher = this.random & 0b11; let displacingHash; let displacedBucket; let displacedCollidingBit; for (let i = 0; i < hashers.length; i++) { const hash = hashers[i][key]; const bucket = hash & expMask; const collidingBit = this.hashBits & collidingPositions(this.sizeExp, bucket); if (!collidingBit) { this.buckets[bucket] = value; this.hashBits = this.hashBits | (1n << BigInt(hash)); this.keyBits = this.keyBits | keyBit; this.hasherByKey[key] = i; this.hasherByHash[hash] = i; return; } if (i === displacedHasher) { displacingHash = hash; displacedBucket = bucket; displacedCollidingBit = collidingBit; } } const displacedHash = 255 - countLeadingZeros(displacedCollidingBit); const displacedKey = hashers[this.hasherByHash[displacedHash]][displacedHash]; this.random = pearsonTable[this.random ^ displacedKey]; const displacedValue = this.buckets[displacedBucket]; this.buckets[displacedBucket] = value; this.hashBits = (this.hashBits & ~displacedCollidingBit) | (1n << BigInt(displacingHash)); this.keyBits = this.keyBits | keyBit; this.hasherByKey[key] = displacedHasher; this.hasherByHash[displacingHash] = displacedHasher; key = displacedKey; keyBit = 1n << BigInt(key); value = displacedValue; if (displacementCount++ > 32) { if (this.sizeExp === 8) throw Error(`Couldn't insert!`); this.sizeExp++; this.buckets.push(...this.buckets); displacementCount = 0; } } } }33:[{"id":"ca2c59b3bb6ccaddd09d1a58a51aec93c4910967f4590e7c363d1a134236ef2202a5128a38fbc453373091bce8d8e431ee0b06fe797716a158388017fdb6085f","href":"https://static.observableusercontent.com/files/ca2c59b3bb6ccaddd09d1a58a51aec93c4910967f4590e7c363d1a134236ef2202a5128a38fbc453373091bce8d8e431ee0b06fe797716a158388017fdb6085f","name":"Paradise_Lost_12.jpg","type":"image/jpeg","lastModified":1618581219026.917,"size":1772411}] 30:{"id":"deaa8574d8a8b5ca","slug":"an_unholy_pact","title":"An unholy PACT 𖤐 Combining Tries and Cuckoo hashing into one persistent datastructure.","thumbnail":"1e5a6ae4fa4280a46ebe98fe99bbada4d6141efb5475e5da3d1f63071c98c68b","access_level":"public","create_time":"$D2021-02-25T19:12:13.994Z","update_time":"$D2021-06-15T13:52:02.094Z","view_time":null,"first_public_time":"$D2021-03-04T10:19:10.744Z","has_unpublished_edits":null,"fork":true,"stars":1,"starred":false,"owner":{"type":"team","id":"881937d4acbb2f00","login":"port","name":"port.studio","avatar_url":"https://avatars-next.observableusercontent.com/b014222f47dd07bcc0889cdfc7f1bb7ec557d2da16995108aa1f233a3939cf97","tier":"starter_2024"},"version":634,"publish_version":634,"role":null,"authored":false,"authors":[{"type":"individual","id":"7aa2b2f3f4c45532","login":"somethingelseentirely","name":"","avatar_url":"https://avatars-next.observableusercontent.com/5c84375e303cfe995944d31a295628df714f891ba8ae3db413da319a8f74e8f1","tier":null}],"members":[{"type":"individual","id":"7aa2b2f3f4c45532","login":"somethingelseentirely","name":"","avatar_url":"https://avatars-next.observableusercontent.com/5c84375e303cfe995944d31a295628df714f891ba8ae3db413da319a8f74e8f1","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"An unholy PACT 𖤐 Combining Tries and Cuckoo hashing into one persistent datastructure.","cells":[{"id":628,"value":"md`# An unholy PACT 𖤐 Combining Tries and Cuckoo hashing into one persistent datastructure.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":612,"value":"html`

\n ${await FileAttachment(\"Paradise_Lost_12.jpg\").image()}\n

Image: Paradise Lost

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"md`## Hashing\n\nThere are various novel hashing and replacement schemes for hash tables.${ref(\n \"Herlihy, Shavit, Tzafrir 2008\",\n \"Hopscotch Hashing\",\n \"http://mcg.cs.tau.ac.il/papers/disc2008-hopscotch.pdf\"\n)}\n\n${ref(\n \"Mitzenmacher2009\",\n \"Some Open Questions Related to Cuckoo Hashing\",\n \"http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pdf\"\n)}\n\n${ref(\n \"ERLINGSSON, MANASSE, MCSHERRY 2006\",\n \"A Cool and Practical Alternative to Traditional Hash Tables\",\n \"http://www.ru.is/faculty/ulfar/CuckooHash.pdf\"\n)}\n\n${ref(\n \"Zukowski, Hemann, Boncz 2006\",\n \"Architecture-Conscious Hashing\",\n \"https://www.cs.cmu.edu/~damon2006/pdf/zukowski06archconscioushashing.pdf\"\n)}\n\n${ref(\n \"Fotakis, Pagh, Sanders, Spirakis 2003\",\n \"Space Efficient Hash Tables with Worst Case Constant Access Time\",\n \"https://www.researchgate.net/publication/225818961_Space_Efficient_Hash_Tables_with_Worst_Case_Constant_Access_Time\"\n)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":584,"value":"md`### References\n${bibliography()}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"randomChoice = arr => {\n const index = Math.floor(Math.random() * arr.length);\n return arr[index];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":177,"value":"generate_involute_hash_LUT = function generate_hash_LUT(\n dependencies,\n remaining = [...Array(256).keys()],\n lut = new Uint8Array(256)\n) {\n if (remaining.length === 0) return lut;\n const i = remaining[0];\n while (true) {\n const forbidden = new Set(dependencies.map(d => d[i]));\n forbidden.add(i);\n const dependentCandidates = remaining.filter(c => !forbidden.has(c));\n if (dependentCandidates.length === 0) return null;\n const val = randomChoice(dependentCandidates);\n const filter = new Set([val, i]);\n const nremaining = remaining.filter(item => !filter.has(item));\n lut[i] = val;\n lut[val] = i;\n if (generate_hash_LUT(dependencies, nremaining, lut)) return lut;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":247,"value":"generate_hash_LUT = function generate_hash_LUT(\n dependencies,\n i = 0,\n remaining = [...Array(256).keys()],\n lut = new Uint8Array(256)\n) {\n if (i === 256) return lut;\n while (true) {\n const forbidden = new Set(dependencies.map(d => d[i]));\n const candidates = remaining.filter(c => !forbidden.has(c));\n if (candidates.length === 0) return null;\n const val = randomChoice(candidates);\n const nremaining = remaining.filter(item => item !== val);\n lut[i] = val;\n if (generate_hash_LUT(dependencies, i + 1, nremaining, lut)) return lut;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"hasher1 = generate_involute_hash_LUT([])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":231,"value":"hasher2 = generate_involute_hash_LUT([hasher1])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":233,"value":"hasher3 = generate_involute_hash_LUT([hasher1, hasher2])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":237,"value":"hasher4 = generate_involute_hash_LUT([hasher1, hasher2, hasher3])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":408,"value":"pearsonTable = generate_hash_LUT([])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":396,"value":"hashers = [hasher1, hasher2, hasher3, hasher4]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":268,"value":"collidingPositions = (sizeExp, pos) => {\n let baseBit = 1n << BigInt(pos);\n for (let i = sizeExp; i < 8; i++) {\n baseBit = baseBit | (baseBit << BigInt(1 << i));\n }\n return baseBit;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":559,"value":"function shuffleArray(array) {\n for (let i = array.length - 1; i > 0; i--) {\n const j = Math.floor(Math.random() * (i + 1));\n [array[i], array[j]] = [array[j], array[i]];\n return array;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":310,"value":"{\n const h = new HashTable();\n [...new Array(1).keys()].forEach(v => h.put(v, v.toString(16)));\n return h;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":349,"value":"{\n const a = [1, 2, 3];\n a.push(...a);\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"nth1 = n => 1n << BigInt(n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"countLeadingZeros = n => {\n let count = 0;\n for (let i = 7; 0 <= i; i--) {\n const c = Math.clz32(Number((n >> BigInt(i * 32)) & 0xFFFFFFFFn));\n if (c !== 32) return count + c;\n count = count + c;\n }\n return count;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"countTrailingZeros = n => {\n // count trailing zeros\n n = n | (n << 128n);\n n = n | (n << 64n);\n n = n | (n << 32n);\n n = n | (n << 16n);\n n = n | (n << 8n);\n n = n | (n << 4n);\n n = n | (n << 2n);\n n = n | (n << 1n);\n // 2. Now, inversing the bits reveals the lowest bits\n return 256 - countLeadingZeros(~n);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"countOnes = bigintPopcnt.fastpopcnt(128)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"variableBits = (...ns) => {\n let bits = 0n;\n for (let i = 0; i < ns.length - 1; i++) {\n bits = bits | (ns[i] ^ ns[i + 1]);\n }\n return bits;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"bits = n => n.toString(2).padStart(128, '0')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"node = ({\n refCount: 0, // 4 byte\n keyCount: 0, // 8 byte\n hash: 0n, // 16 byte TODO: use instance keyed xxHash\n maskBits: 0n, // 16 bytes\n commonBits: 0n, // 16 bytes\n partialKeys: new Array(16),\n children: new Array(16) // 128 byte top 16 bit of 64bit pointer are partial key;\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":133,"value":"countTrailingZeros(nth1(127))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"countLeadingZeros(nth1(120))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"bits(countLeadingZeros(variableBits(nth1(0), nth1(1))))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"({ discriminating: 0n, children: [], childCount: 0 })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":68,"value":"bigintPopcnt = require('https://bundle.run/bigint-popcnt@1.0.1')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"import { Table } from \"@observablehq/inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":580,"value":"import { bibliography, ref } from \"@somethingelseentirely/papers\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 31:"$30:body"