Hash array mapped trie

По крайней мере в scala для вектора используется AMT, а не HAMT. А вообще несколько не хватает примеров использования подобных структур. Как удачных, так и неудачных (что не менее важно). Потому что, если смотреть формально на тот же вектор, то, допустим время модификации элемента O(1) (ну т.е. создание нового вектора на основе старого), но на практике ~32 раза медленнее чем в обычном массиве. И хотя иммутабельность хорошо, но при частых модификациях врядли удасться себе такое позволить.

1. HashMap не потоко-безопасна. HAMT можно реализовать потоко-безопасным ( это не так уж сложно ). Конечно, есть ConcurrentHashMap. Я не пишу на Java, так что ничего не могу сказать про быстродействие.
2. К HAMT можно написать итераторы и обходить как простое дерево, HashMap обходить в определенном порядке, кажется, нельзя.
Еще хороший пример использования HAMT при передаче файлов.
Вообще, всё что я написал выше, применимо ко всем hash trees.
Можно поискать статьи типа «Hash map vs hash tree» для изучения.
Насчет производительности нашел такой набор слайдов. Тут, правда, Haskell, но можно взглянуть на приведенные на последнем слайде цифры.

Ещё одно важное отличие — поддержка персистентности. Т.е. если мы используем данную структуру для реализации иммутабельной структуры данных, то при необходимости создать копию с одним измененным элементом, мы можем не копировать всю структуру, а скопировать только один листовой узел с 32 элементами, что значительно экономит память в функциональных языках.