Computer Graphics & Visualization @ufrj.br
Point k-d trees with queriesHash table with open addressing and double hashingPoint 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 separate chaining
demo = {
reset;
let ht = new HashTable();
let result = htl.html`<div>`;
let inserted = [];
for (let i = 0; i < 8; i++) {
const k = 1 + Math.floor(random() * 100);
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;
}
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);
}
}
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 += `<tr>`;
for (let i = 0; i < m; i++) {
gv += `<th style="font:10px monospace;text-align:center;max-width:3em;">${i}</th>`;
}
gv += `</tr>`;
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 += `<TD style="max-width:3em;border:1px solid black;text-align:center;">${cell}</TD>`;
else if (row == 0)
tds += `<TD style="max-width:3em;border:1px solid black;text-align:center;">-</TD>`;
else tds += `<TD></TD>`;
}
gv += `<TR>` + tds + `</TR>\n`;
row++;
} while (row < 10);
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.
