Ideal Hash Trees (2001) [pdf]

infoscience.epfl.ch

60 pointsbrudgers4 comments

HAMT by mr Bagwell are great:

* https://idea.popcount.org/2012-07-25-introduction-to-hamt/

I was mostly surprised not by the CPU, but by the memory efficiency. From my experimentation it turns out that if you want to store X bits of data, HAMT will use ~1.5 * X bits per item.

In other words: thousand 8-byte pointers in HAMT will occupy around 12 thousand bytes of memory.

HAMT is cool! I'm maintaining an ORM objects cache server in my $dayjob that uses HAMT as it's core data structure and I really like the ram usage efficiency.

Closely related are Judy Arrays (aka Judy Trees):

https://en.wikipedia.org/wiki/Judy_array

The "tree" objects that git uses to track state, are they hash trees?

Reply on news.ycombinator.com