Most efficient way of storing objects with corresponding indices

Question

I want to store a collection of Points, which are objects of the class Point. (Point contains properties as positionX, positionY, electricalPotential, etc.) Each of them should have an index i, but the don't need to be ordered in any way. This is why I used a dictionary Dictionary<int, Point> meshpoints in the first place.

First Question:
Is a dictionary the most efficient way of storing my data if I only want to store the object with a certain index/key, especially if it comes to performance issues as adding, searching and looping for each element?

Second Question:
If I want to add a new Point, how do I get the "next" free key? Like if I have dictionary with the hash-keys 0, 1, 2, 3 and 4, how do I get the 5 for the next item-key?

Option 1: meshpoints.Keys.Max() and meshpoints.Keys.Last() take a lot of time in my tests.

Dictionary<int, string> meshpoints = new Dictionary<int, string>();

meshpoints.Add(meshpoints.Keys.Max() + 1, "itemA");

meshpoints.Add(meshpoints.Keys.Max() + 1, "itemB");

Option 2: Creating a seperate variable counter is pretty fast in my performance test, but is it really the most elegant way? I mean, you always have a carry a seperate integer value with dictionary to all methods, etc. ...

Dictionary<int, string> meshpoints = new Dictionary<int, string>();
int counter = 0;

meshpoints.Add(counter, "itemA");
counter++;

meshpoints.Add(counter, "itemB");
counter++;

Option 3: meshpoints.Count() won't work, when I also delete items at any point.

Answer 1

If you don't like having two separate variables, then make a new structure to bind them together:

struct MeshPointContainer
{
    private int _counter = 0;
    private List<Point> _pts = new List<Point>();

    public int Add(Point pt) {
        _pts.Add(pt);
        return ++counter;
    }
}

Then use it like this:

var meshPoints = new MeshPointContainer();
meshPoints.Add(new Point(-1f));

This will be a little more complicated if you want to be able to remove points, but so far you have not indicated that you do.