Daniel J. Bernstein personal blog
Crit-bit Trees: the best way to store sets
A crit-bit tree can be used as a high-speed associative array. For example, an array mapping 54 to 1, 19 to 2, 99 to 3, 85 to 4, and 88 to 5 can be stored as a crit-bit tree containing 54=1, 19=2, 99=3, 85=4, and 88=5. The smallest string in the crit-bit tree larger than 85= is 85=4.
- Points
- 106
- HN comments
- 81
- Submissions
- 2
- Cited by
- 14 commenters
Math & AlgorithmsSoftware Engineering2011
On Hacker News
| Submitted | Title on HN | Points | Comments |
|---|---|---|---|
| Sep 19, 2011 | Crit-bit Trees: the best way to store sets by bumbledraven | 106 | 40 |
| Dec 17, 2013 | Crit-bit trees by siromoney | 98 | 41 |
Cited in comments
Linked from 15 Hacker News comments by 14 different people, from Jan 2008 to Jul 2025.
Most recent:
- jonstewart · Jul 4, 2025
- aidenn0 · Oct 7, 2024
- commandersaki · Jul 11, 2023
- stevenjgarner · Jul 22, 2022
- ignoramous · Dec 4, 2020
- tonyg · Oct 12, 2018
