HackerReposA FIELD GUIDE TO OPEN SOURCE
ProSponsor the shelf♧ 0
← Back to top all-time
mkirchner
hamt
C2022–2023
mkirchner / hamt

hamt

A hash array-mapped trie implementation in C

4Distinct people
5Mentions
0Explicit recommenders
334GitHub stars
REPOSITORY AT A GLANCE

What to know before exploring

What it is

A hash array-mapped trie implementation in C

GitHub

Where it is used

No documented product use has been verified yet.

What people are saying

No recommendation phrase was found in the indexed comments.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

No other repository is repeatedly linked in the same discussions.

This week on Hacker News

Nov 9–Nov 16 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/16/2026, 7:27:27 AM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by month5 dated mentions

Observed mentions: 2022-07-22 09:03:11 UTC to 2023-08-24 21:19:04 UTC.

0122022-07-01 00:00:00 UTC to 2022-08-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 commentsJul 20222022-08-01 00:00:00 UTC to 2022-09-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2022-09-01 00:00:00 UTC to 2022-10-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2022-10-01 00:00:00 UTC to 2022-11-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2022-11-01 00:00:00 UTC to 2022-12-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2022-12-01 00:00:00 UTC to 2023-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2023-01-01 00:00:00 UTC to 2023-02-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 commentsJan 20232023-02-01 00:00:00 UTC to 2023-03-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2023-03-01 00:00:00 UTC to 2023-04-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2023-04-01 00:00:00 UTC to 2023-05-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2023-05-01 00:00:00 UTC to 2023-06-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2023-06-01 00:00:00 UTC to 2023-07-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2023-07-01 00:00:00 UTC to 2023-08-01 00:00:00 UTC (exclusive): 2 mentions; 1 submissions, 1 comments2023-08-01 00:00:00 UTC to 2023-09-01 00:00:00 UTC (exclusive): 2 mentions; 0 submissions, 2 commentsAug 2023

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges
UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
PeriodStart (UTC)End (exclusive, UTC)MentionsSubmissionsComments
Jul 20222022-07-01 00:00:00 UTC2022-08-01 00:00:00 UTC101
Aug 20222022-08-01 00:00:00 UTC2022-09-01 00:00:00 UTC000
Sep 20222022-09-01 00:00:00 UTC2022-10-01 00:00:00 UTC000
Oct 20222022-10-01 00:00:00 UTC2022-11-01 00:00:00 UTC000
Nov 20222022-11-01 00:00:00 UTC2022-12-01 00:00:00 UTC000
Dec 20222022-12-01 00:00:00 UTC2023-01-01 00:00:00 UTC000
Jan 20232023-01-01 00:00:00 UTC2023-02-01 00:00:00 UTC000
Feb 20232023-02-01 00:00:00 UTC2023-03-01 00:00:00 UTC000
Mar 20232023-03-01 00:00:00 UTC2023-04-01 00:00:00 UTC000
Apr 20232023-04-01 00:00:00 UTC2023-05-01 00:00:00 UTC000
May 20232023-05-01 00:00:00 UTC2023-06-01 00:00:00 UTC000
Jun 20232023-06-01 00:00:00 UTC2023-07-01 00:00:00 UTC000
Jul 20232023-07-01 00:00:00 UTC2023-08-01 00:00:00 UTC211
Aug 20232023-08-01 00:00:00 UTC2023-09-01 00:00:00 UTC202

What Hacker News says

2 sources
This isn't a very good explanation. The wikipedia article isn't great either. I like this description: https://github.com/mkirchner/hamt#persistent-hash-array-mapp... The name does tell you quite a bit about what these are: * Hash - rather than directly using the keys to navigate the structure, the keys are hashed, and the hashes are used for navigation. This turns potentially long, poorly-distributed keys into short, well-distributed keys. However, that does mean you have to compute a hash on every access, and have to deal with hash collisions. The mkirchner implementation above calls collisions "hash exhaustion", and deals with them using some generational hashing scheme. I think i'd fall back to collision lists until that was conclusively proven to be too slow. * Trie - the tree is navigated by indexing nodes using chunks of the (hash
Read the rest
of the) key, rather than comparing the keys in the node * Array mapped - sparse nodes are compressed, using a bitmap to indicate which logical slots are occupied, and then only storing those. The bitmaps live in the parent node, rather than the node itself, i think? Presumably helps with fetching. A HAMT contains a lot of small nodes. If every entry is a bitmap plus a pointer, then it's two words, and if we use five-bit chunks, then each node can be up to 32 entries, but i would imagine the majority are small, so a typical node might be 64 bytes. I worry that doing a malloc for each one would end up with a lot of overhead. Are HAMTs often implemented with some more custom memory management? Can you allocate a big block and then carve it up? Could you do a slightly relaxed HAMT where nodes are not always fully compact, but sized to the smallest suitable power of two entries? That might let you use some sort of buddy allocation scheme. It would also let you insert and delete without having to reallocate the node. Although i suppose you can already do that by mapping a few empty slots.
In Grokking Hash Array Mapped Tries (HAMTs)

MAKE YOURSELF AT HOME

A few shortcuts

/
Search the collection
?
Open this guide
Esc
Close dialogs and navigation

Your saved repositories and interests stay in this browser.