In Kotlin’s standard library, there’s a class named kotlin.collections.builders.MapBuilder, which implements MutableMap using a hash table. Instances of this class are created using the buildMap function, introduced in Kotlin 1.6.
Unfortunately, the MapBuilder class lacks documentation, and I couldn’t find any description of this class online. I am curious to understand why buildMap uses this MutableMap implementation instead of the standard HashMap.
I find this question intriguing for the following reason: In the Guava library, there’s a method com.google.common.collect.Maps#capacity that calculates the capacity needed for a HashMap to store a known number of elements while considering the default load factor. I discovered that Kotlin stdlib has a similar function called mapCapacity, but it’s internal. Hence, I continued my research to determine what Kotlin suggests for creating a HashMap of a predetermined size. This search led me to the buildMap function, which has a version accepting capacity as an argument. Interestingly, with buildMap, it seems there’s no need for a function like mapCapacity because MapBuilder only extends internal structures when completely filled. Thus, you can simply pass the expected size of the map as capacity. In other words, MapBuilder behaves like a HashMap created with a load factor of 1.
On the other hand, perhaps buildMap should create a MapBuilder with a larger capacity than the expected number of elements to reduce the likelihood of collisions (after all, HashMap is created with a default load factor of 0.75 for this reason). So, why does the buildMap implementation not do this?
buildMap is intended to be used to build an immutable map. It’s similar to buildString which is used to build a String. buildMap exposes to its lambda a mutable version of the map so that you can fill it, and while the capacity parameter is indeed a suggestion, the expectation is that you’re likely to be around that capacity exactly, hence the 1 load factor. That’s also why its implementation is internal and undocumented: it’s an implementation detail.
I understand that buildMap creates an immutable map, but this doesn’t clarify why another map implementation (MapBuilder) is necessary for this purpose. In fact, MapBuilder is mutable; it’s just that buildMap declares it returns a Map instead of a MutableMap .
Similarly, buildMap could have used and returned a HashMap (as a Map) .
The same outcome could be achieved by wrapping the returned HashMap using java.util.Collections#unmodifiableMap.
After all why does Kotlin make this locking in this particular case? The mapOf function or the collections extension toMap returns a LinkedHashMap (which is mutable), even though they also declare that they return an immutable Map.
MapBuilder is not a copy of HashMap with added immutability features, so this doesn’t explain why a different hash table-based map implementation was necessary. I would be interested in knowing the authors’ perspective. What motivated them to create their own version of a hash table? What inspired this decision? In what ways is this implementation superior to HashMap?