Where to store the data for which the search is needed?

Question

.NET

Each number corresponds to another number.
1 = 10
2 =15
3 = 15
9 = 11
8 = 11
The numbers are in order, but there may be gaps.
What functionality is needed:
1) Find the maximum, if there are several, then select a random one. Those.
maximum (2 = 15, 3 = 15), then 2 or 3 is randomly selected
. . For this is a rather narrow point in performance.
var my_data = new Dictionary<int, int>();
Methods, writing to the structure, I can find myself, for me now the storage format is important.
Although if there are non-obvious and fast methods for specific structures, then I will be grateful.

Answer 1

Well, asymptotically, adding an element to the HashMap (And Dictionary is what it is) is O (n)
(Actually, no. If the code is not for CodeForces, then we can assume that O (1), because the probability the collision is not large)
If you are satisfied with this, then it is quite possible to use it.
And remember the maximum when inserting. Then getting the max will be O(1).