Hashmap with time values, want to find value at specific second

Question

I have a Linked Hash Map (My query orders the points by time) that contains stock data from a database, the time is in (int) seconds after midnight and the values are double values in both MYSQL and Java. I have attached a sample of the data below. The amount of data we get on a specific day varies but it is usually close to 10k entries.

30607,   131.46
30608,   131.44
30608,   131.45
30609,   131.46
30611,   131.48
30613,   131.49
30615,   131.51
30615,   131.5

We are graphing the data and I don't have enough reputation to show you a picture but it basically looks a lot like the a yahoo finance chart. One of the things yahoo does which is cool is that it detects the mouse location then tells you the value (dollar amount) of the graph at a specific time, I am trying to mimic that effect. (For other reasons, we cannot use any free graphing utility we have found and the commercial grade ones are a bit outside of our price range.

So I have a LinkedHashMap and I have a function that turns the xvalue of a pixel into an approximate time (approximate if 1 pixel is worth more than one second)

public static final int getTimeFromPixel(Settings window, final int pixel) {
    return (int) Math.round((window.getTimeStart() + window.getXPixelValue()
        * (pixel - YAXIS)));
}

Here are the three options I am thinking about (two are functions like the ones below - all pseudo-code and uncompiled but I tried to get them close to correct)

/**
 * Start at the beginning of my linkedhashmap "points" and then stop when the
 * key is as close as possible. Break the for loop when the keys are past
 * the time we are looking for since this is a linked hashmap and I know
 * that the times were placed into the linkedhashmap in order.
 * @param pixel_x the xvalue of a pixel (from a mouse event)
 * @return the value at our stock at the closest before time we have data for
 */
public double iterateThroughLinkedHashMapToFindValue(int pixel_x) {
    int pixelTime = Settings.getTimeFromPixel(window, pixel_x);
    int closestTimeWeHave = 0;
    for (int second : points.keySet()) {
        if (Math.abs(pixelTime - second)
                < Math.abs(pixelTime - closestTimeWeHave)) {
            closestTimeWeHave = second;
        }
        if (second > pixelTime) {
            break;
        }
    }
    return points.get(closestTimeWeHave);
}

/**
 * Start as close as possible to a key we want then start checking
 * backwards until we find a value we have. Since we get values almost
 * every 3 seconds, it shouldn't have to check very far to get a value.
 * @param pixel_x the xvalue of a pixel (from a mouse event)
 * @return the value at our stock at the closest before time we have data for    
 */
public double tryToGetCloseToValueInHashMap(int pixel_x) {
    // Go to the next pixel, subtract 1 second from that pixel (should put
    // us at the far end of our current pixel if a pixel represents more
    // than one second on our graph
    int pixelTime = Settings.getTimeFromPixel(window, pixel_x + 1) - 1;
    // count backwards until we find a time we have a value for.
    while (!points.containsKey(pixelTime)) {
        pixelTime--;
    }
    return points.get(pixelTime);
}

My third option is to create a double[] array while I am iterating through the points to draw them on screen and make basically a value map for each pixel on screen so I can just call a function like this

 public double getValueFromPixel(int pixel_x) {
     return valueMap[pixel_x];
 }

My question is which one, if any, would be best. As you can see, I get data fairly often (on average every 3.5 seconds) so using the second options theoretically wouldn't have to scan very far before it found something it could use. The value map is nice but do I want to create that for every point every time I redraw or grab those values on the fly using one of the other two functions?

I use stackoverflow all the time via google searches but I can't find a good answer to this question so I am actually asking one. Thanks in advance! If there is a better way to do this, I am all ears.

Answer 1

You don't need a (Linked)HashMap for this job. Use a NavigableMap (TreeMap would be the standard implementation) that provides a lot of useful operations for such use-cases: floor/ceiling, higher/lower, first/last and so on.

// get the value at this specific time or the last one before that
Double valueAtTheTime = map.floorEntry(theTime).getValue();