The docs say it uses a hash trie, which I suspect is more specifically a hash array mapped trie. Clojure also uses a HAMT map and describes performance characteristics as “effectively constant-time”. I’ve seen some good Clojure talks on the topic, although it seems I didn’t save links to any of them.