Why the address of my BluetoothDevice changes ever

I'm doing some simple scanning + advertising testing on bluetooth LE feature for Android using this sample-code

I'm testing it using a Samsung 6 and a Nexus 9, and for some reason if I leave the app running on the Samsung and restart the app on the Nexus, the next time the Samsung devices finds the other device, it has a different address.

In code:

On the device:

The funny thing it doesn't happen the other way around. (Samsung always has the same address when discovered from the Nexus 9)

Is this a common behavior between devices?
Is there another way to identify a specific device besides it's mac address?

As CommonsWare mentioned, as of Android 6.0, Android has removed access to the hardware address programmatically, and made it so that the address appears to be randomly generated to scanning devices. The change log can be found here:

http://developer.android.com/about/versions/marshmallow/android-6.0-changes.html#behavior-hardware-id

The fact that scanning devices see a random Bluetooth address rather than the actual one is a highly useful privacy feature. It was adopted by the Bluetooth specification as of BTv4.0 and is known as LE privacy:

"This feature causes the MAC address within the advertising packets to be replaced with a random value that changes at timing intervals determined by the manufacturer. Any malicious device(s), placed at intervals along your travel route, would not be able to determine that the series of different, randomly generated MAC addresses received from your device actually relates to the same physical device. It actually looks like a series of different devices, thus, it will not be possible to track you using the advertised MAC address"[1]

You can find a similar question here:-

Since marshmallow update Bluetooth discovery using BluetoothAdapter.getDefaultAdapter().startDiscovery(); is broken

[1] http://blog.bluetooth.com/bluetooth-technology-protecting-your-privacy/