After considerable amounts of benchmarking we've found that for small maps (<= 8 keys) a specific PersistentArrayMap type outperforms a full blown PersistentHashMap. A PersistentArrayMap type also has the advantage of being quickly constructed from an array a la Immutable.Vector - particularly handy in a deserialization context.