Data structure recommendation?

["Martin v. Löwis"]

> I know that foo.get() will be called many times for each foo.put(). Is
> there any way to achieve O(1) performance for foo.get(), maybe via
> some kind of hash function? Or is the best thing to use some kind of
> binary search?

If you know something about the density of the input values, O(1) is
possible. E.g if there is a guarantee that there will be between 1
and 10 values per unit of input, then truncate the "event time" to
the next-lower int, and use that as an index k into a list; the list
item will be a list of events between k and k+1. As you know that
there is an upper bound to the number of such events (10), you
know that searching the list will take bounded (i.e. constant) time.
Likewise, as you know that there will be atleast one event per
(k,k+1) interval, you know that you have to scan only one list.

If you know no such thing, you'll have to use a binary search.

Regards,
Martin