typescript(bun): robin hood hash map

README.md

% bun run index.ts
Inserting items: 6e340b9cffb37a98, 4bf5122f344554c5, dbc1b4c900ffe48d, 084fed08b978af4d, e52d9c508c502347, e77b9a9ae9e30b0d, 67586e98fad27da0, ca358758f6d27e6c
Are all items in the map? true
Ascending order: 084fed08b978af4d, 4bf5122f344554c5, 67586e98fad27da0, 6e340b9cffb37a98, ca358758f6d27e6c, dbc1b4c900ffe48d, e52d9c508c502347, e77b9a9ae9e30b0d
Descending order: e77b9a9ae9e30b0d, e52d9c508c502347, dbc1b4c900ffe48d, ca358758f6d27e6c, 6e340b9cffb37a98, 67586e98fad27da0, 4bf5122f344554c5, 084fed08b978af4d

Deleting item: ca358758f6d27e6c
Was the item found and deleted? true
Ascending order: 084fed08b978af4d, 4bf5122f344554c5, 67586e98fad27da0, 6e340b9cffb37a98, dbc1b4c900ffe48d, e52d9c508c502347, e77b9a9ae9e30b0d
Descending order: e77b9a9ae9e30b0d, e52d9c508c502347, dbc1b4c900ffe48d, 6e340b9cffb37a98, 67586e98fad27da0, 4bf5122f344554c5, 084fed08b978af4d

Deleting item: 6e340b9cffb37a98
Was the item found and deleted? true
Ascending order: 084fed08b978af4d, 4bf5122f344554c5, 67586e98fad27da0, dbc1b4c900ffe48d, e52d9c508c502347, e77b9a9ae9e30b0d
Descending order: e77b9a9ae9e30b0d, e52d9c508c502347, dbc1b4c900ffe48d, 67586e98fad27da0, 4bf5122f344554c5, 084fed08b978af4d

Deleting item: e77b9a9ae9e30b0d
Was the item found and deleted? true
Ascending order: 084fed08b978af4d, 4bf5122f344554c5, 67586e98fad27da0, dbc1b4c900ffe48d, e52d9c508c502347
Descending order: e52d9c508c502347, dbc1b4c900ffe48d, 67586e98fad27da0, 4bf5122f344554c5, 084fed08b978af4d

Deleting item: ca358758f6d27e6c
Was the item found and deleted? false
Ascending order: 084fed08b978af4d, 4bf5122f344554c5, 67586e98fad27da0, dbc1b4c900ffe48d, e52d9c508c502347
Descending order: e52d9c508c502347, dbc1b4c900ffe48d, 67586e98fad27da0, 4bf5122f344554c5, 084fed08b978af4d

Deleting item: dbc1b4c900ffe48d
Was the item found and deleted? true
Ascending order: 084fed08b978af4d, 4bf5122f344554c5, 67586e98fad27da0, e52d9c508c502347
Descending order: e52d9c508c502347, 67586e98fad27da0, 4bf5122f344554c5, 084fed08b978af4d

Deleting item: 084fed08b978af4d
Was the item found and deleted? true
Ascending order: 4bf5122f344554c5, 67586e98fad27da0, e52d9c508c502347
Descending order: e52d9c508c502347, 67586e98fad27da0, 4bf5122f344554c5

Deleting item: dbc1b4c900ffe48d
Was the item found and deleted? false
Ascending order: 4bf5122f344554c5, 67586e98fad27da0, e52d9c508c502347
Descending order: e52d9c508c502347, 67586e98fad27da0, 4bf5122f344554c5

Deleting item: 67586e98fad27da0
Was the item found and deleted? true
Ascending order: 4bf5122f344554c5, e52d9c508c502347
Descending order: e52d9c508c502347, 4bf5122f344554c5

Deleting item: 67586e98fad27da0
Was the item found and deleted? false
Ascending order: 4bf5122f344554c5, e52d9c508c502347
Descending order: e52d9c508c502347, 4bf5122f344554c5

Deleting item: 084fed08b978af4d
Was the item found and deleted? false
Ascending order: 4bf5122f344554c5, e52d9c508c502347
Descending order: e52d9c508c502347, 4bf5122f344554c5

Deleting item: 6e340b9cffb37a98
Was the item found and deleted? false
Ascending order: 4bf5122f344554c5, e52d9c508c502347
Descending order: e52d9c508c502347, 4bf5122f344554c5

Deleting item: 4bf5122f344554c5
Was the item found and deleted? true
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: e77b9a9ae9e30b0d
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: 67586e98fad27da0
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: ca358758f6d27e6c
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: e77b9a9ae9e30b0d
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: 084fed08b978af4d
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: 6e340b9cffb37a98
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: 084fed08b978af4d
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: 4bf5122f344554c5
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: 6e340b9cffb37a98
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: ca358758f6d27e6c
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: 6e340b9cffb37a98
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: dbc1b4c900ffe48d
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: ca358758f6d27e6c
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: ca358758f6d27e6c
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: 084fed08b978af4d
Was the item found and deleted? false
Ascending order: e52d9c508c502347
Descending order: e52d9c508c502347

Deleting item: e52d9c508c502347
Was the item found and deleted? true
Ascending order: 
Descending order: 

index.ts

// Author: Kenta Iwasaki
// % bun run index.ts

// A simple robin-hood hash map implementation using open addressing and linear probing.
// All keys and values are strings. The map has a fixed capacity and does not support resizing.
// All entries are stored in a single array. The array is divided into two parts: the main part and the overflow part.
// The main part is used for storing the entries. The overflow part is used for storing entries that have been shifted to make room for new entries.
// All entries are naturally sorted by their keys. This is done by using a hash function that converts the first 8 bytes of the key to a 64-bit big-endian unsigned integer.
// Robin hood hashing is used to ensure that the entries are sorted by their hash, which in turn means that this map has its entries sorted by their keys.

// An optimization may be done to speed up scanning the entries when the hash map is not close to reaching its capacity.
// This can be done by storing the index of the first entry that is not empty.

const CAPACITY = 1 << 24; // The capacity must be a power-of-two.

const SHIFT = 31 - Math.floor(Math.log2(CAPACITY)) + 1;
const OVERFLOW = (CAPACITY / 10 + (31 - SHIFT + 1)) << 1;
const EMPTY_KEY = "\xff\xff\xff\xff";

type Entry = { key: string; value?: string };

const entries: Entry[] = Array.from(
  { length: CAPACITY + OVERFLOW },
  (_, i) => ({ key: EMPTY_KEY })
);

let len = 0;

// Convert first 8 bytes of the key to a 64-bit big-endian unsigned integer.
// If the key is shorter than 8 bytes, pad it with 0x00.
// This hash function will make it so that 'AA' < 'AB'. 'A' < 'B'.
function hash(key: string) {
  // if (key === EMPTY_KEY) {
  //   return 0xffffff;
  // }
  return (
    (key.charCodeAt(0) << 24) +
    (key.charCodeAt(1) << 16) +
    (key.charCodeAt(2) << 8) +
    key.charCodeAt(3)
  );
}

function hashToIndex(hash: number) {
  return hash >> SHIFT;
}

function get(key: string) {
  const h = hash(key);
  let i = hashToIndex(h);

  while (true) {
    const entry = entries[i];
    if (entry.key >= key) {
      if (entry.key === key) {
        return entry.value;
      }
      return null;
    }
    i++;
  }
}

function put(key: string, value: string) {
  const { index } = getOrPut(key);
  entries[index].key = key;
  entries[index].value = value;
}

function getOrPut(key: string) {
  if (len >= CAPACITY) {
    throw new Error("The map is full.");
  }

  let it: Entry = { key };
  let i = hashToIndex(hash(key));
  let insertedAt: number | undefined = undefined;

  while (true) {
    const entry = entries[i];

    if (entry.key >= key) {
      // If we found an existing entry, return it.
      if (entry.key === key) {
        return { exists: true, index: i } as const;
      }

      // If the entry is occupied, we need to shift it to make room for the new entry.
      entries[i] = it;

      // If we have a previous entry, we need to shift it to make room for the new entry.
      if (entry.key === EMPTY_KEY) {
        len += 1;
        return {
          exists: false,
          index: insertedAt !== undefined ? insertedAt : i,
        } as const;
      }
      if (insertedAt === undefined) {
        insertedAt = i;
      }

      // Continue with the shifted entry.
      it = entry;
    }

    i++;
  }
}

function del(key: string) {
  const h = hash(key);
  let i = hashToIndex(h);

  // Find the entry to delete.

  while (true) {
    const entry = entries[i];
    if (entry.key >= key) {
      if (entry.key !== key) {
        return null;
      }
      break;
    }
    i++;
  }

  const value = entries[i].value;

  // Perform backwards shift deletion to fill the gap.
  // This is done to ensure that the entries are sorted by hash.

  while (true) {
    const j = hashToIndex(hash(entries[i + 1].key));
    if (i < j || entries[i + 1].key === EMPTY_KEY) {
      entries[i] = entries[i + 1];
      break;
    }

    entries[i] = entries[i + 1];
    i++;
  }

  entries[i] = { key: EMPTY_KEY };
  len -= 1;

  return value;
}

function* scanAscending() {
  for (const entry of entries) {
    if (entry.key !== EMPTY_KEY) {
      yield entry;
    }
  }
}

function* scanDescending() {
  for (let i = entries.length - 1; i >= 0; i--) {
    const entry = entries[i];
    if (entry.key !== EMPTY_KEY) {
      yield entry;
    }
  }
}

const items = Array.from({ length: CAPACITY / 2 }, (_, i) => {
  return Bun.SHA256.hash(Uint8Array.of(i), "hex").slice(0, 16);
});

Bun.gc(true);

const now = performance.now();

// console.log(`Inserting items: ${items.join(", ")}`);
for (const [i, item] of items.entries()) {
  put(item, String(i));
}

// console.log(
//   `Are all items in the map? ${items.every((item) => get(item) !== null)}`
// );

// console.log(
//   `Ascending order: ${[...scanAscending()].map((o) => o.key).join(", ")}`
// );
// console.log(
//   `Descending order: ${[...scanDescending()].map((o) => o.key).join(", ")}`
// );

// console.log();

for (const item of items) {
  del(item);
}

// console.log(`Deleting item: ${itemToDelete}`);
// console.log(`Was the item found and deleted? ${del(itemToDelete) !== null}`);

// console.log(
//   `Ascending order: ${[...scanAscending()].map((o) => o.key).join(", ")}`
// );

// console.log(
//   `Descending order: ${[...scanDescending()].map((o) => o.key).join(", ")}`
// );

// console.log();

console.log(performance.now() - now);