Add me to the list of people who have noticed the problem with the shuffle feature. It tends to prefer a small subset of songs out of a larger playlist. Out of a playlist of a thousand songs, it is surprising how many times the same songs will reappear. But I may have found a workaround.
I haven't done a statistical analysis (and don't plan to), but it seems to me that whenever I have completely powered down my mobile device and restarted it, the songs chosen by the shuffle feature are completely new. If the playlist is reshuffled without powering off the device, many of the songs that were recently played will still be near the top of the list. It's as if the randomization algorithm is flawed in some way. But when the device is powered off and then on again, whatever seed it used last time gets changed, and the shuffle feature chooses brand new songs for the top of the list. I would like others to try this and let me know if they are getting similar results.
One other effect I have noticed relates to the crossfade slider. If this slider is set to anything other than 0 seconds and the shuffled playlist is paused for a long time (e.g. several hours), then sometimes the playlist will "reset." What this means is that the playlist will have to be restarted in shuffle mode. This gives the algorithm a chance to replay a song that has recently played. It seems that the program cannot hold its place in the playlist when the crossfade feature is activated. When the crossfade slider is set to 0 seconds, though, the playlist will almost always hold its place, and when you start playing it again, it will continue without having to refresh the playlist. This has the effect of preventing the same song from reappearing too soon.
I don't use playlist, I go to Your music/Songs and shuffle that. But Spotify is playing a couple of same songs again and again and some songs from my collection are not being played at all (I got over 1300 songs).
I'm switching pages and sometimes adding songs to queue, but on my iPhone i don't do that often and I'm experiencing same behaviour (I'm plugging my iPhone into car radio if that's relevant). Even when I click repeatedly on "Shuffle play" button I'm hearing the same songs
I've had this problem since the moment I got Spotify. 1000's of songs in a playlist and it plays the same exact 50-100 songs over and over again. Same exact songs, whether I'm on mobile or desktop, same exact songs no matter how many times I restart/reboot/log out/reinstall/whatever. One thing that no one else has mentioned, and I think it's very important to, the songs that it hasn't "picked", NEVER get played. No matter how long I keep the shuffle going, no matter how many times I hit the next button, those songs never actually get played. This isn't just some algorithm problem, this has gotta be some kinda bug. But then why has it been happening for years? I've seen posts describing this issue since like 2012. I'm guessing most users just don't notice it's happening. Is this some kinda royalty conspiracy? Either way, very lame Spotify.
I've considered switching from Spotify several times. The way it "shuffles" tracks is still absolutely terrible.
The easiest, best way to shuffle songs (like almost every other music player does): assign each track a number. Randomize that list of numbers. Done. You won't have any duplicates and the order of everything would actually be different each time.