Why is a string key for a hash frozen?

问题:

According to the specification, strings that are used as a key to a hash are duplicated and frozen. Other mutable objects do not seem to have such special consideration. For example, with an array key, the following is possible.

a = [0]
h = {a => :a}
h.keys.first[0] = 1
h # => {[1] => :a}
h[[1]] # => nil
h.rehash
h[[1]] # => :a

On the other hand, a similar thing cannot be done with a string key.

s = "a"
h = {s => :s}
h.keys.first.upcase! # => RuntimeError: can't modify frozen String

Why is string designed to be different from other mutable objects when it comes to a hash key? Is there any use case where this specification becomes useful? What other consequences does this specification have?

---

I actually have a use case where absence of such special specification about strings may be useful. That is, I read with the yaml gem a manually written YAML file that describes a hash. the keys may be strings, and I would like to allow case insensitivity in the original YAML file. When I read a file, I might get a hash like this:

h = {"foo" => :foo, "Bar" => :bar, "BAZ" => :baz}

And I want to normalize the keys to lower case to get this:

h = {"foo" => :foo, "bar" => :bar, "baz" => :baz}

by doing something like this:

h.keys.each(&:downcase!)

but that returns an error for the reason explained above.

回答1:

In short it's just Ruby trying to be nice.

When a key is entered in a Hash, a special number is calculated, using the hash method of the key. The Hash object uses this number to retrieve the key. For instance, if you ask what the value of h['a'] is, the Hash calls the hash method of string 'a' and checks if it has a value stored for that number. The problem arises when someone (you) mutates the string object, so the string 'a' is now something else, let's say 'aa'. The Hash would not find a hash number for 'aa'.

The most common types of keys for hashes are strings, symbols and integers. Symbols and integers are immutable, but strings are not. Ruby tries to protect you from the confusing behaviour described above by dupping and freezing string keys. I guess it's not done for other types because there could be nasty performance side effects (think of large arrays).

回答2:

See this thread on the ruby-core mailing list for an explanation (freakily, it happened to be the first mail I stumbled across when I opened up the mailing list in my mail app!).

I've no idea about the first part of your question, but hHere is a practical answer for the 2nd part:

  new_hash = {}
  h.each_pair do |k,v|
   new_hash.merge!({k.downcase => v}) 
  end

  h.replace new_hash

There's lots of permutations of this kind of code,

  Hash[ h.map{|k,v| [k.downcase, v] } ]

being another (and you're probably aware of these, but sometimes it's best to take the practical route:)

回答3:

Immutable keys make sense in general because their hash codes will be stable.

This is why strings are specially-converted, in this part of MRI code:

if (RHASH(hash)->ntbl->type == &identhash || rb_obj_class(key) != rb_cString) {
  st_insert(RHASH(hash)->ntbl, key, val);
}
else {
  st_insert2(RHASH(hash)->ntbl, key, val, copy_str_key);
}

In a nutshell, in the string-key case, st_insert2 is passed a pointer to a function that will trigger the dup and freeze.

So if we theoretically wanted to support immutable lists and immutable hashes as hash keys, then we could modify that code to something like this:

VALUE key_klass;
key_klass = rb_obj_class(key);
if (key_klass == rb_cArray || key_klass == rb_cHash) {
  st_insert2(RHASH(hash)->ntbl, key, val, freeze_obj);
}
else if (key_klass == rb_cString) {
  st_insert2(RHASH(hash)->ntbl, key, val, copy_str_key);
}
else {
  st_insert(RHASH(hash)->ntbl, key, val);
}

Where freeze_obj would be defined as:

static st_data_t
freeze_obj(st_data_t obj)
{
    return (st_data_t)rb_obj_freeze((VALUE) obj);
}

So that would solve the specific inconsistency that you observed, where the array-key was mutable. However to be really consistent, more types of objects would need to be made immutable as well.

Not all types, however. For example, there'd be no point to freezing immediate objects like Fixnum because there is effectively only one instance of Fixnum corresponding to each integer value. This is why only String needs to be special-cased this way, not Fixnum and Symbol.

Strings are a special exception simply as a matter of convenience for Ruby programmers, because strings are very often used as hash keys.

Conversely, the reason that other object types are not frozen like this, which admittedly leads to inconsistent behavior, is mostly a matter of convenience for Matz & Company to not support edge cases. In practice, comparatively few people will use a container object like an array or a hash as a hash key. So if you do so, it's up to you to freeze before insertion.

Note that this is not strictly about performance, because the act of freezing a non-immediate object simply involves flipping the FL_FREEZE bit on the basic.flags bitfield that's present on every object. That's of course a cheap operation.

Also speaking of performance, note that if you are going to use string keys, and you are in a performance-critical section of code, you might want to freeze your strings before doing the insertion. If you don't, then a dup is triggered, which is a more-expensive operation.

Update @sawa pointed out that leaving your array-key simply frozen means the original array might be unexpectedly immutable outside of the key-use context, which could also be an unpleasant surprise (although otoh it would serve you right for using an array as a hash-key, really). If you therefore surmise that dup + freeze is the way out of that, then you would in fact incur possible noticeable performance cost. On the third hand, leave it unfrozen altogether, and you get the OP's original weirdness. Weirdness all around. Another reason for Matz et al to defer these edge cases to the programmer.

回答4:

You are askin 2 different questions: theoretical and practical. Lain was the first to answer, but I would like to provide what I consider a proper, lazier solution to your practical question:

Hash.new { |hsh, key| # this block get's called only if a key is absent
  downcased = key.to_s.downcase
  unless downcased == key # if downcasing makes a difference
    hsh[key] = hsh[downcased] if hsh.has_key? downcased # define a new hash pair
  end # (otherways just return nil)
}

The block used with Hash.new constructor is only invoked for those missing keys, that are actually requested. The above solution also accepts symbols.