If you mean by "Fetching a digit" the operation m[str[i]], using a hashmap makes this an O(1) operation, so that is not the bottleneck. But the operation 4.1 will probably have a running time proportional to the length of x which is proportional to str_digits.len, and putting this into a loop with str_digits.len iterations results in an O(N²) operation.

Is my algorithm correct

If I ignore some minor glitches like writing {0,1,...,14,15} instead of {0,1,...,E,F}, it looks correct at a first glance. But honestly, implement it and use a debugger, the code will probably be not much longer that your text above.

is specifically the digit storing part [..] efficient?

If you mean by "Fetching a digit" the operation m[str[i]], using a hashmap makes this an O(1) operation, so that is not the bottleneck. But the operation 4.1 will probably have a running time proportional to the length of x which is proportional to str_digits.len, and putting this into a loop with str_digits.len iterations results in an O(N²) operation.

Is this efficient? Not as efficient as it could be, of course. But you should better ask yourself "is it efficient enough for my purpose", and that is something you can only find out by profiling.