How to calculate 95 percentile in Java using the datasets in Map

Question

I am trying to calculate 95% percentile from my datasets in Java. My datasets will have something like this-

I will be having a ConcurrentHashMap that will have key value pair like this-

Key = 30
Value = 10

which means 10 calls came back in 30 milliseconds

Another Example-

Key = 20
Value = 5

which means , 5 calls came back in 20 milliseconds

So from the above Map, I am trying to calculate 95% Percentile in Java.

Can anyone provide any example how to do that in Java from my above Map? Thanks for the help

Updated Code:-

Below is the code I have got which will calculate the 95th percentile from the Map-

/**
 * A simple method to log 95th percentile information
 */
private static void logPercentileInfo() {

    double total = 0;
    for (Map.Entry<Long, Long> entry : CassandraTimer.histogram.entrySet()) {
        long value = entry.getKey() * entry.getValue();
        total += value;
    }

    double sum = 0.95*total;

    double totalSum = 0;

    SortedSet<Long> keys = new TreeSet<Long>(CassandraTimer.histogram.keySet());
    for (long key : keys) {

        totalSum += CassandraTimer.histogram.get(key);

        if(totalSum >= sum) {
            System.out.println(key);
        }
    }

}

Can anyone take a look and let me know whether I have written correctly?

Answer 1

Algorithm is: sum all values from your map, calculate 95% of the sum, iterate the map keys in ascending order keeping a running total of values, and when sum equals or exceeds the previously calculated 95% of the total sum, the key should be the 95th percentile.