The map iteration order was always "random", but imperfectly so prior to Go 1.3. From memory, it picked a random initial bucket, but then always iterated over that bucket in order, so small maps (e.g. only a handful of elements) actually got deterministic iteration order. We fixed that in Go 1.3, but it broke a huge number of tests across Google that had inadvertently depended on that quirk; I spent quite a few weeks fixing tests before we could roll out Go 1.3 inside Google. I imagine there was quite a few broken tests on the outside too, but the benefit was deemed big enough to tolerate that.