# mersenne-hash-table

> Fast Node.js hashtable which uses Mersenne primes to reduce modulo operations

Latest version **0.0.3** (published 2020-11-18) · MIT license · 0 weekly downloads

## Install

```sh
npm install mersenne-hash-table
pnpm add mersenne-hash-table
yarn add mersenne-hash-table
bun add mersenne-hash-table
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support; pre 1.0.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 0.0.3 |
| Published | 2020-11-18 |
| First published | 2020-11-18 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 0 |
| Unpacked size | 8.1 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 0 |
| Author | k-koehler |
| Maintainers | kevin-koehler |
| Keywords | hashmap, string, fast, map, hash, table, hashtable |

## Links

- npm: https://www.npmjs.com/package/mersenne-hash-table
- Repository: https://github.com/k-koehler/mersenne-hash-table
- Homepage: https://github.com/k-koehler/mersenne-hash-table#readme
- Issues: https://github.com/k-koehler/mersenne-hash-table/issues
- npm.io page: https://npm.io/package/mersenne-hash-table

## Alternatives

- [@lexical/table](https://npm.io/package/@lexical/table.md) — 3.0M weekly downloads
- [mantine-datatable](https://npm.io/package/mantine-datatable.md) — 98.2K weekly downloads
- [react-native-collapsible-tab-view](https://npm.io/package/react-native-collapsible-tab-view.md) — 70.6K weekly downloads
- [@handsontable/vue3](https://npm.io/package/@handsontable/vue3.md) — 16.1K weekly downloads
- [vuewordcloud](https://npm.io/package/vuewordcloud.md) — 7.2K weekly downloads

## Recent versions

- 0.0.3 (latest) — 2020-11-18
- 0.0.2 — 2020-11-18

## README

# mersenne-hash-table

## How it works

This hashtable uses a particular property of the mersenne numbers to reduce a typically large modulo (`%`) instruction to a blazing fast bitwise and (`&`) operation. Consider the typical use cases for a hash-table, when you have a bucket of size `k` and a hash function `f` s.t. `f(x) > k`: to determine the index `i` to place your data, likely you're doing something like `i = f(x) % k`. However, there exists a property of mersenne numbers (numbers which take the form `2^s - 1` for some natural number `s`) which can summarized as: for a mesenne prime `m`, while `m` is larger than `k`, `k % m = k & m`.

See the above (very small) sample set:

| `k`   | `m`   | `k % m` | `k & m` |
|-----|-----|-------|-------|
| 1   | 127 |   1   | 1     |
| 50  | 127 |   50  | 50    |
| 100 | 127 |   100 | 100   |

To see how this works, consider the form that mersenne primes take:

| `m` | `m` binary representation | `k` | `k` binary representation | `k & m` |
|-----|---------------------------|-----|---------------------------|---------|
| 7   | 111                       | 3   | 011                       | 011     |
| 15  | 1111                      | 5   | 0101                      | 0101    |
| 31  | 11111                     | 17  | 10001                     | 10001   |

Since a mersenne prime `m_s` is represented in binary as `s` repeating 1 bits, the result of any bitwise `&` between `k_i` and `m_i` is simply `k_i` since `k_i & 1 = k_i`.

---
_Source: https://npm.io/package/mersenne-hash-table · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._