Does OrderedHash exist?

dubstep · July 15, 2011, 12:03am

Hello,
i know that in Ruby 1.9 Hash is ordered, but it seems to be a
controversial solution.
Does there exist by any chance any standard library with an OrderedHash
class?
I would prefer to call ordered hash an OrderedHash, rather than Hash.

I saw that there existed ActiveSupport::OrderedHash in Rails, but its
API page recently disappeared…

I think by the way that the current ordered implementation of Hash is
nice, but should have been called OrderedHash, so that in future
versions Hash could be made unordered again.

Thanks,

Alexey.

4zy · July 15, 2011, 12:06am

Alexey M. wrote in post #1010832:

Hello,
i know that in Ruby 1.9 Hash is ordered, but it seems to be a
controversial solution.
Does there exist by any chance any standard library with an OrderedHash
class?

After a long court battle, the ruby standard library has recently been
procured by Bloomberg News under a Freedom of Information Request, and
it is now publicly available.

I would prefer to call ordered hash an OrderedHash, rather than Hash.

Ruby allows you to call a class anything you want.

4zy · July 15, 2011, 12:15am

7stud – wrote in post #1010833:

Ruby allows you to call a class anything you want.

Thanks, but this is for a Rails application, and i wonder if i can rely
on Hash ordering to be compatible with future versions of Ruby.

A.

4zy · July 15, 2011, 12:29am

On Thu, Jul 14, 2011 at 4:03 PM, Alexey M. <
[email protected]> wrote:

Hello,
i know that in Ruby 1.9 Hash is ordered, but it seems to be a
controversial solution.
Does there exist by any chance any standard library with an OrderedHash
class?
I would prefer to call ordered hash an OrderedHash, rather than Hash.

I saw that there existed ActiveSupport::OrderedHash in Rails, but its
API page recently disappeared…

Yes, it has been marked with the #:nodoc: rdoc tag(?) so it is now
omitted
from the documentation. If I were you I’d go ask the guys in the “Ruby
on
Rails: Core” mailing-list/group (
Redirecting to Google Groups) if you can
expect
the class to stick around (and/or why it’s been nodoc-ed). After all,
since
your project is a rails one you’re right to look to leverage this
ActiveSupport class.

I think by the way that the current ordered implementation of Hash is
nice, but should have been called OrderedHash, so that in future
versions Hash could be made unordered again.

Or it is named correctly and you can just assume a Hash isn’t ordered
(even
if it is for a specific version) and code accordingly. Or just copy or
fork
ActiveSupport::OrderedHash for your own needs in your own project:

github.com

rails/rails/blob/main/activesupport/lib/active_support/ordered_hash.rb

# frozen_string_literal: true

require "yaml"

YAML.add_builtin_type("omap") do |type, val|
  ActiveSupport::OrderedHash[val.map { |v| v.to_a.first }]
end

module ActiveSupport
  # DEPRECATED: +ActiveSupport::OrderedHash+ implements a hash that preserves
  # insertion order.
  #
  #   oh = ActiveSupport::OrderedHash.new
  #   oh[:a] = 1
  #   oh[:b] = 2
  #   oh.keys # => [:a, :b], this order is guaranteed
  #
  # Also, maps the +omap+ feature for YAML files
  # (See https://yaml.org/type/omap.html) to support ordered items
  # when loading from YAML.

This file has been truncated. show original

4zy · July 15, 2011, 12:36am

Kendall G. wrote in post #1010836:

If I were you I’d go ask the guys in the “Ruby
on
Rails: Core” mailing-list/group (
Redirecting to Google Groups) if you can
expect
the class to stick around (and/or why it’s been nodoc-ed). After all,
since
your project is a rails one you’re right to look to leverage this
ActiveSupport class.

Thanks Kendall, i didn’t know about this mailing list.

I think by the way that the current ordered implementation of Hash is
nice, but should have been called OrderedHash, so that in future
versions Hash could be made unordered again.

Or it is named correctly and you can just assume a Hash isn’t ordered
(even
if it is for a specific version) and code accordingly.

Yes, my “problem” is exactly that i did not want to assume Hash to be
ordered.

Alexey.

4zy · July 15, 2011, 4:11am

On Jul 14, 6:36pm, Alexey M. [email protected]
wrote:

ActiveSupport class.
(even
if it is for a specific version) and code accordingly.

Yes, my “problem” is exactly that i did not want to assume Hash to be
ordered.

Insertion ordered is part of Ruby spec now. It is very unlikely to
change b/c a lot of people will be very pissed.

That said, there are other types of order. Consider hashery gem with
it’s Dictionary class (which is an evolution of the orderedhash gem).

4zy · July 16, 2011, 9:34am

Thomas,

I created a class called, HashArray which implements a pretty
straightforward Hash with order object. Content can be added, deleted,
reordered, etc, and then there is the as_array method that enables using
the object as an array.

I can send you the source if you want but I’d appreciate it if you (or
anyone else that reads this) could help me turn it into a gem…

Best,

Oren S.

4zy · July 16, 2011, 2:32pm

On Sat, Jul 16, 2011 at 9:34 AM, Oren S. [email protected]
wrote:

I created a class called, HashArray which implements a pretty
straightforward Hash with order object. Content can be added, deleted,
reordered, etc, and then there is the as_array method that enables using
the object as an array.

I’m curious how you manage to keep the data structure ordered and keep
access time O(1). It surely is O(1) since it’s called _Hash_Array,
isn’t it?

Kind regards

robert

4zy · July 16, 2011, 3:31pm

On Jul 16, 2011, at 2:32 PM, Robert K. wrote:

Kind regards

robert

Not speaking for the OP, but the naive solution by keeping book of key
ordering in an Array for ordered access (mostly iteration) and going
straight for a plain Hash for storage and unordered access already
fulfills that. Non-trivial insertion would suffer, because it has to
reorganize the keys.

Regards,
Florian

4zy · July 16, 2011, 6:11pm

On Sat, Jul 16, 2011 at 7:32 AM, Robert K.
[email protected]wrote:

Kind regards

robert

–
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

You don’t necessarily have to keep it ordered the whole time. Order only
matters when you try to access it. So you could keep all the hash
properties, then as soon as someone tries to do something ordered, build
a
heap O(n) and then iterate as you remove the minimum. Essentially heap
sort,
but yielding each object as you remove it.

If you track whether it is sorted, then the first iteration is O(n lg n)
and
the rest after that are O(n). Of course, if you keep adding lots of keys
and
iterating frequently, then iteration performance would suffer. Seems
like in
cases like that, you have to make a trade off somewhere

4zy · July 18, 2011, 9:58am

On Sat, Jul 16, 2011 at 6:10 PM, Josh C. [email protected]
wrote:

access time O(1). It surely is O(1) since it’s called _Hash_Array,
isn’t it?

Well, first of all I’d rather hear from Oren what he really did.

You don’t necessarily have to keep it ordered the whole time. Order only
matters when you try to access it. So you could keep all the hash
properties, then as soon as someone tries to do something ordered, build a
heap O(n) and then iterate as you remove the minimum. Essentially heap sort,
but yielding each object as you remove it.

If you track whether it is sorted, then the first iteration is O(n lg n) and
the rest after that are O(n). Of course, if you keep adding lots of keys and
iterating frequently, then iteration performance would suffer. Seems like in
cases like that, you have to make a trade off somewhere

The approach you describe is best suited for usage scenarios where
there are two phases: 1. manipulation (insert, delete) 2. usage
(ordered iteration). But for that an ordinary Hash is sufficient
which then is sorted once.

If ordered accesses are mixed with inserts and deletions then probably
a data structure with permanent ordering is better suited. You
typically can’t get both at the same time - updates with O(1) and
continuous ordering.

Kind regards

robert