From the docs for values (my emphasis):

The values are returned in an apparently random order. The actual random order is subject to change in future versions of perl, but it is guaranteed to be the same order as either the "keys" or "each" function would produce on the same (unmodified) hash.