Есть такая структура префиксное дерево. Для него Фил Бэгвел придумал очень хорошую реализацию AMT. Но в ней искать можно только по строке, что не всегда удобно. Часто хочется класть в мапу любой тип в качестве ключа. Поэтому Фил придумал следующую реализацию HAMT. Его идею подхватили и сделали успешную реализацию HAMT на Java. Обзор последней можно почитать у Кольера.

Очень интересная тема, осталось понять почему этого добра до сих пор нет в стандартной библиотеке.