What are recommended ways to refactor the internal representation of a class?

Say I have a class which stores some data in a private variable 'data', e.g. an array. There are different methods of this class using the data variable and different unit tests testing these methods. Now for some reason you want to change the container type of data (e.g. a map instead of an array), which needs to be handled in a slightly different way. If one simply changes the type of data from array to map all the code in the methods gets broken and one would have to change them all before any unit tests can be run again. This usually is not what one wants. So what is the recommended way to do this iteratively without breaking all the code at once ?