Map.computeIfAbsent vs recursion vs duplicate keys

demonstrateDuplicateMapKeys.kt

package demo

val myMap = mutableMapOf<Int, String>()

fun main() {
    val myKeys = listOf(1, 2, 2)

    buildMap(myMap, myKeys)

    println("map size=${myMap.size}") // yields 3
    println("map keys size=${myMap.keys.size}") // yields 3
    println("to list, size=${myMap.toList().size}") // yields 3
    println("to set, size=${myMap.keys.toSortedSet().size}") // yields 2
    myMap.keys.sorted().reduce { acc, key ->
        key.also { if (it == acc) { println("dup => ${it}") }}
    }
    println(myMap)
    val surpriseMe = myMap.get(2)
    println("myMap.get(2) => ${surpriseMe}") // yields "string value for 2 at level 1"
}

fun buildMap(map: MutableMap<Int, String>, keyList: List<Int>, level: Int = 0) {
    if ( keyList.size > 0 ) {
        map.computeIfAbsent(keyList.get(0)) { key ->
            buildMap(map, keyList.subList(1, keyList.size), 1 + level)
            "string value for ${key} at level ${level}"
        }
    }
}

/* output:
map size=3
map keys size=3
to list, size=3
to set, size=2
dup => 2
{2=string value for 2 at level 2, 2=string value for 2 at level 1, 1=string value for 1 at level 0}
myMap.get(2) => string value for 2 at level 1
*/

I got duplicate key entries because I did not comply with the javadocs:

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#computeIfAbsent-K-java.util.function.Function-

If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null. The entire method invocation is performed atomically, so the function is applied at most once per key. Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.

This also reveals something about how the equals() and hashCode() assertions are being used behind computeIfAbsent(). The Map does not have any stateful notion of "pending transaction" for that key, and understandably so.

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l1086

Extension function FTW. Last one wins. Substitute assignWhenAbsent() in place of computeIfAbsent().

    fun <K, V> MutableMap<K, V>.assignWhenAbsent(key: K, compute: (key: K) -> V): V {
        return this.get(key) ?: compute.invoke(key).also { computedValue ->
            this.put(key, computedValue)
        }
    }