There are at least 4 different types of ordering behavior in a map: 1. Returning in insertion order. Quite strange thing to do as it requires extra bookkeeping

There are at least 4 different types of ordering behavior in a map: 1. Returning in insertion order. Quite strange thing to do as it requires extra bookkeeping. 2. An order unrelated to insertion order that is consistently the same for a given set of keys. Using a hash it would be sorting by the hash value, in a balanced tree, sorting by the value itself. 3. An order unrelated to insertion order and that can be different for the same set of keys but is always the same on repeated iterations on the same map. This could be a hash table where on creation a random salt is generated on creation and hashed together. 4. An order that actually changes on every iteration. Is there an efficient way of doing this? From the discussion here and some quick testing: Type1: Ruby 1.9.3 (very strange) Type2: Ruby 1.8.3, python 2.7.3, Perl <5.18 Does anyone know if Go and Perl 5.18 are doing 3 or 4? Ruby >1.9 behavior is also quite strange but seems to be intended, they've implemented a hash together with a doubly linked list[1]. [1] http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/ http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-h...