keys - map repeat key java

Deduplicación para el método de cadena interna en ConcurrentHashMap

Question

Observé un código de JavaDays, el autor dijo que este enfoque con probabilidad es muy efectivo para almacenar cadenas como el método analógico al interno de cadenas

 public class CHMDeduplicator<T> {
    private final int prob;
    private final Map<T, T> map;

    public CHMDeduplicator(double prob) {
        this.prob = (int) (Integer.MIN_VALUE + prob * (1L << 32));
        this.map = new ConcurrentHashMap<>();
    }

    public T dedup(T t) {
        if (ThreadLocalRandom.current().nextInt() > prob) {
            return t;
        }
        T exist = map.putIfAbsent(t, t);
        return (exist == null) ? t : exist;
    }
}

Por favor, explícame, ¿cuál es el efecto de la probabilidad en esta línea?

if (ThreadLocalRandom.current().nextInt() > prob) return t;

Esta es una presentación original de Java Days https://shipilev.net/talks/jpoint-April2015-string-catechism.pdf (diapositiva 56)

Answer 1

El doble valor pasado al constructor está destinado a ser un valor de probabilidad en el rango de 0.0 a 1.0. Se convierte a un número entero tal que la proporción de valores enteros debajo de ella es igual al valor doble.

La expresión completa está diseñada para evaluar a true con una probabilidad igual a la del parámetro constructor. Al usar matemática entera será un poco más rápido que si se usara el valor doble sin procesar.

La intención de la implementación es que a veces no almacena en caché la cadena, sino que simplemente la devuelve. La razón para hacer esto es una compensación de rendimiento de CPU vs. memoria: si el proceso de almacenamiento en caché que ahorra memoria causa un cuello de botella en la CPU, puede aumentar la probabilidad de "no hacer nada" hasta que encuentre un equilibrio.

Answer 2

Si observa la siguiente diapositiva que tiene una tabla con datos con diferentes probabilidades, o escucha la charla , verá / escuchará el razonamiento: los deduplicadores probabilísticos equilibran el tiempo dedicado a desduplicar las cadenas y los ahorros de memoria provenientes de la deduplicación. Esto permite ajustar el tiempo dedicado al procesamiento de cadenas, o incluso rociar los deduplicadores de bajo contenido alrededor del código, amortizando así los costos de deduplicación.

(Fuente: estas son mis diapositivas)