Purposeful random memory allocations

Question

For an experiment, I want to measure time it takes to find a given record with random memory access. The record is a simple class:

template<class TKey, class TData>
class Record {
  TKey key;
  TData data;
public:
  Record(TKey key, TData data) {
    this->key = key;
    this->data = data;
  }
};

Now I simply allocate memory and insert some records. (Please ignore some syntax mistakes...)

const int size = 1_000_000;
Record<int, int> ** data = new Record<int, int>*[size];

for (int i = 0; i < size; ++i) {
  // allocates sizeof(Record<int, int>) on heap
  data[i] = new Record<int, int>(i, i);
}

The issue is, when allocating these new Record objects, the are actually stored sequentially in memory. I want these memory locations to be random. Does C++ have any ways to accomplish this?