Accesing keys based on position in an association

Perhaps:

GetKey[assoc_, index_] := First @ Keys @ Take[assoc, {index}]

Your first example:

assoc = <|{1,1} -> 2, {1,2} -> 3, {2,1}->4, {2,2}->5|>;

GetKey[assoc, 1]
GetKey[assoc, 4]

{1, 1}

{2, 2}

Your large example:

a = 1024*1024;
keys = Table[i, {i, a}];
values = RandomReal[{0, 1000000}, {a}];
assoc = Association[MapThread[Rule, {keys, values}]];

AbsoluteTiming[Keys[assoc][[10000]]]
AbsoluteTiming[GetKey[assoc, 10000]] 

{0.373301, 10000}

{0.003779, 10000}

This is one of those questions where I suspect it wasn't put enough thought in the data-structures. You use associations for fast access to values based on a key. The association data structure is just not optimized for what you try to do.

Nevertheless, I believe Carl's solution is already very good if you want a function that purely works on your association. If you need to access the same association very often, I would prefer to extract the keys and directly access them. A simple function could look like this:

KeyGet[a_Association] := Module[{keys = Keys[a]},
  KeyGet[i_Integer] := keys[[i]]
]

You use it by initializing it once with your association and then you provide only the integers (or ranges).

assoc = Association @@ Flatten@Table[{x, y} -> RandomInteger[100], {x, 1024}, {y, 1024}];

KeyGet[assoc];
KeyGet[1234]
KeyGet[{1,10,34}]
KeyGet[45;;100]

The first call of KeyGet needs about 0.44 seconds here. As soon as you need to access several thousand indices, it will be faster than using Take like in Carls example, but in general, I would prefer his solution.

Refresh your memory about how Part works and then observe:

assoc = <|{1, 1} -> 2, {1, 2} -> 3, {2, 1} -> 4, {2, 2} -> 5|>;

assoc[[{1}]]

assoc[[{4}]]

<|{1, 1} -> 2|>

<|{2, 2} -> 5|>

This is equivalent to Take[assoc, {i}] and syntactically shorter. So I would write:

getKey[a_Association, p_Integer] := a[[{p}]] // Keys // First