In the newer Androids there's a feature called WiFi MAC Randomization. In its basic form, the mechanism calculates the random MAC for a given ESSID. Each time you connect to the same WiFi, Android will use the previously generated MAC. Even when you forget the WiFi network and add it anew, Android will use the same MAC as before. So where exactly is the WiFi MAC randomization data stored?
According to the Android documentation the persistent randomization is not stored anywhere.
Instead the "random MAC address" is generated every time you connect to the Wifi. This generation bases on the Wifi network parameters:
Android generates a persistent randomized MAC address based on the
parameters of the network profile including SSID, security type, or
FQDN (for Passpoint networks).
And I assume that additionally some secret factor that is unique to your device is included into the calculation, otherwise every Android device would generate the same random MAC address for the same network. Not sure what they actually use, may be ANDROID_ID or some random ~128 bit data stored somewhere in your user profile.
In such situations typically an HMAC algorithm is used to generate pseudorandom output that can then be used for the 46 bits of the MAC that are randomized. This makes it next to impossible to determine the used secret part based on the randomized MAC address and to calculate MAC addresses you would use in other networks.
Note that this answer is only about AOSP. Android manufacturer may change the randomization. According to a study on WiFi MAC randomization Motorola e.g. implements a custom MAC randomization scheme (not the 46bit scheme described in AOSP).
Q & A