# Introduction to HAMT

DevFeed: [Introduction to HAMT](<https://devfeed.tech/articles/introduction-to-hamt-38908.md>)

Original publisher: [Read original article](<https://idea.popcount.org/2012-07-25-introduction-to-hamt>)

Author: Marek

Published: 2012-07-24T22:00:00Z

Content type: tutorial

Language: en

Sources: [Marek Majkowski](<https://devfeed.tech/sources/marek-majkowski.md>)

Topics: [Data structures](<https://devfeed.tech/topics/data-structures.md>), [hash](<https://devfeed.tech/topics/hash.md>), [Compression](<https://devfeed.tech/topics/compression.md>)

Tags: [array](<https://devfeed.tech/tags/array.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [compression](<https://devfeed.tech/tags/compression.md>), [data-structure](<https://devfeed.tech/tags/data-structure.md>), [data-structures](<https://devfeed.tech/tags/data-structures.md>), [hash](<https://devfeed.tech/tags/hash.md>), [memory](<https://devfeed.tech/tags/memory.md>), [trees](<https://devfeed.tech/tags/trees.md>)

## AI overview

This tutorial introduces Hash Array Mapped Tries (HAMTs) as a memory-efficient alternative to binary trees. It explains how tries store values, how naive array representations waste space, and how bitmap-based compression reduces the memory footprint while preserving efficient lookup proportional to prefix length.

## Source excerpt

Introduction to HAMT In the previous post I explained that a binary tree wasn't the best data structure for my needs - it wastes too much memory. I looked for a memory-efficient data structures and I found a gem: Hash Array Mapped Trie (HAMT). The author, Phil Bagwell, wrote two papers related to the subject: - Fast And Space Efficient Trie Searches, 2000 (pdf) (source) - In this paper the author is comparing various implementations of Tries and introduces Array Mapped Trie.