WeirdComputeIfAbsentBehaviour.java

import java.math.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;

/**
 * Seems to cause livelock in Java 8 ConcurrentHashMap transfer()
 * method and ConcurrentModificationException in Java 9 HashMap.
 */
public class WeirdComputeIfAbsentBehaviour {
  public static void main(String... args) {
    for (int i = 0; i < 30; i++) {
      System.out.println("i = " + i);
      show(new HashMap(), i);
      show(new LinkedHashMap(), i);
      show(new ConcurrentSkipListMap<>(), i);
      show(new ConcurrentHashMap<>(), i);
    }
  }

  private static void show(Map<Integer, BigInteger> map, int n) {
    System.out.println(map.getClass().getSimpleName() + ": " +
        new FibonacciCached(map).f(n));
  }


  public static class FibonacciCached {
    private final Map<Integer, BigInteger> cache;

    public FibonacciCached(Map<Integer, BigInteger> cache) {
      this.cache = cache;
      cache.put(0, BigInteger.ZERO);
      cache.put(1, BigInteger.ONE);
    }

    public BigInteger f(int n) {
      return cache.computeIfAbsent(n, key -> f(n - 1).add(f(n - 2)));
    }
  }
}

package livedemo;

import java.util.concurrent.*;
import java.math.BigInteger;
import java.util.Map;

public class FibonacciCached {
private final Map<Integer, CompletionStage> cache;

public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {
  this.cache = cache;
  cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));
  cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));
}

public CompletionStage<BigInteger> f(int n) {
  CompletableFuture<BigInteger> next = new CompletableFuture<>();
  CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);
  if (prev != null) return prev;
  else
    return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));
}

}