Computer Graphics & Visualization @ufrj.br
Point k-d trees with queriesHash table with separate chainingPoint k-d treesOmohundro balltree construction algorithmsCounting and radix sortMergeSort and QuickSortSkipListSplay TreesTreapsBinary Heaps2-3-TreesAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
Hash table with open addressing and double hashing
demo = {
reset;
let ht = new HashTable(4, 0.3, 0.6);
let result = htl.html`<div>`;
let inserted = [];
for (let i = 0; i < 8; i++) {
const k = 1 + Math.floor(random() * 100);
console.log({ k, g: ht.g(k), ht });
if (!ht.find(k)) {
result.append(md`**Inserting ${k}**`);
ht.insert(k, k);
inserted.push(k);
result.append(html`${showtable(ht)}`);
}
}
d3.shuffle(inserted);
for (let k of inserted.slice(1)) {
result.append(md`**Removing ${k}**`);
ht.delete(k);
result.append(html`${showtable(ht)}`);
}
return result;
}
random = d3.randomLcg(1)
function makeHash(m) {
if (m > largePrimes[0]) throw "Table too large";
const p = largePrimes[Math.floor(random() * largePrimes.length)];
const a = 1 + Math.floor(random() * (p - 1));
const b = Math.floor(random() * p);
return (x) => ((a * x + b) % p) % m;
}
function makeHash2(m) {
// let h = makeHash(m);
// return (x) => {
// let d = h(x);
// if (d == 0 || m % d == 0) return 1;
// return d;
// };
let p = largePrimes[Math.floor(random() * largePrimes.length)];
return (x) => p;
}
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);
}
}
function showtable(ht) {
const table = ht.table,
m = ht.m;
let gv = ``;
gv += `<tr>`;
for (let i = 0; i < m; i++) {
gv += `<th style="font:10px monospace;text-align:center;max-width:3em;">${i}</th>`;
}
gv += `</tr>`;
let tds = "";
for (let i = 0; i < m; i++) {
let cell = table[i];
if (cell.key) cell = cell.key;
tds += `<TD style="max-width:3em;border:1px solid black;text-align:center;">${cell}</TD>`;
}
gv += `<TR>` + tds + `</TR>\n`;
return `<TABLE style="table-layout:fixed;width:${m * 3}em">\n${gv}</TABLE>`;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
