Tại sao một khóa chuỗi cho một mã băm bị đóng băng?

Question

Theo số specification, các chuỗi được sử dụng làm khóa để băm được nhân đôi và đóng băng. Các đối tượng có thể thay đổi khác dường như không có sự xem xét đặc biệt như vậy. Ví dụ, với một phím mảng, sau đây là có thể.

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

Mặt khác, điều tương tự không thể thực hiện bằng khóa chuỗi.

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

Tại sao chuỗi được thiết kế khác với các đối tượng có thể thay đổi khác khi nói đến khóa băm? Có trường hợp sử dụng nào trong đó đặc điểm kỹ thuật này trở nên hữu ích không? Các đặc điểm kỹ thuật này có những hậu quả nào khác?

---

Tôi thực sự có trường hợp sử dụng khi không có đặc điểm kỹ thuật đặc biệt đó về chuỗi có thể hữu ích. Tức là, tôi đọc bằng đá quý yaml một tệp YAML được viết theo cách thủ công mô tả một băm. các phím có thể là chuỗi, và tôi muốn cho phép phân biệt chữ hoa chữ thường trong tập tin YAML gốc. Khi tôi đọc một tập tin, tôi có thể nhận được một hash như thế này:

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

Và tôi muốn bình thường hóa những chìa khóa để giảm trường hợp để có được điều này:

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

bằng cách làm một cái gì đó như thế này:

h.keys.each(&:downcase!) 

nhưng trả về lỗi vì lý do được giải thích ở trên.

Answer 1

Tóm lại chỉ là Ruby cố gắng trở nên tốt đẹp.

Khi một khóa được nhập vào một Hash, một số đặc biệt được tính toán, sử dụng phương pháp hash của khóa. Đối tượng Hash sử dụng số này để lấy khóa. Ví dụ, nếu bạn hỏi giá trị của h['a'] là gì, hàm Hash gọi phương thức hash của chuỗi 'a' và kiểm tra xem nó có giá trị được lưu trữ cho số đó hay không.Vấn đề nảy sinh khi ai đó (bạn) thay đổi đối tượng chuỗi, vì vậy chuỗi 'a' bây giờ là cái gì đó khác, hãy nói 'aa'. Hash sẽ không tìm thấy số băm cho 'aa'.

Các loại khóa phổ biến nhất cho băm là chuỗi, ký hiệu và số nguyên. Ký hiệu và số nguyên là không thay đổi, nhưng chuỗi không. Ruby cố gắng bảo vệ bạn khỏi hành vi khó hiểu được mô tả ở trên bằng cách duỗi và đóng băng các phím chuỗi. Tôi đoán nó không được thực hiện cho các loại khác vì có thể có hiệu ứng phụ hiệu suất khó chịu (suy nghĩ của mảng lớn).

Answer 2

Xem this thread on the ruby-core mailing list để được giải thích (freakily, nó đã xảy ra là thư đầu tiên tôi stumbled khi tôi mở danh sách gửi thư trong ứng dụng thư của tôi!).

Tôi không biết về phần đầu của câu hỏi của bạn, nhưng h Đây là một câu trả lời thiết thực cho phần 2:

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

    h.replace new_hash 

Có rất nhiều các hoán vị của loại mã,

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

bị khác (và có lẽ bạn đang nhận thức được những, nhưng đôi khi nó là tốt nhất để đi theo con đường thực tế :)

Answer 3

bạn đang askin 2 câu hỏi khác nhau: lý thuyết và thực tế. Lain là người đầu tiên trả lời, nhưng tôi muốn cung cấp những gì tôi xem xét một hợp lý, giải pháp lazier cho câu hỏi thực tế của bạn:

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) 
} 

Khối sử dụng với Hash.new constructor chỉ gọi những chiếc chìa khóa mất tích, mà là thực sự yêu cầu. Giải pháp trên cũng chấp nhận các ký hiệu.

Answer 4

Các khóa không thay đổi có ý nghĩa nói chung vì mã băm của chúng sẽ ổn định.

Đây là lý do tại sao các chuỗi được đặc biệt-chuyển đổi, trong phần này của mã MRI:

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); 
} 

Tóm lại, trong trường hợp chuỗi-key, st_insert2 được thông qua một con trỏ đến một chức năng mà sẽ kích hoạt dup và đóng băng.

Vì vậy, nếu chúng ta theo lý thuyết muốn hỗ trợ danh sách bất biến và băm bất biến như phím băm, sau đó chúng ta có thể sửa đổi mã đó để một cái gì đó như thế này:

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); 
} 

đâu freeze_obj sẽ được xác định như sau:

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

Vì vậy, điều đó sẽ giải quyết sự mâu thuẫn cụ thể mà bạn quan sát được, trong đó khóa mảng có thể thay đổi. Tuy nhiên để thực sự nhất quán, nhiều loại đối tượng sẽ cần phải được thực hiện bất biến là tốt.

Không phải tất cả các loại, tuy nhiên. Ví dụ, sẽ không có điểm để đóng băng các đối tượng ngay lập tức như Fixnum vì chỉ có một thể hiện của Fixnum tương ứng với mỗi giá trị số nguyên. Đây là lý do tại sao chỉ String cần phải được đặt theo cách đặc biệt theo cách này, không phải là Fixnum và Symbol.

Chuỗi là ngoại lệ đặc biệt đơn giản chỉ là vấn đề thuận tiện cho các lập trình viên Ruby, bởi vì các chuỗi thường được sử dụng làm khóa băm.

Ngược lại, lý do mà các loại đối tượng khác là không đông lạnh như thế này, mà phải thừa nhận là dẫn đến hành vi không phù hợp, chủ yếu là một vấn đề thuận tiện cho Công ty Matz & để không ủng hộ các trường hợp cạnh. Trong thực tế, tương đối ít người sẽ sử dụng một đối tượng container như một mảng hoặc một băm như một khóa băm. Vì vậy, nếu bạn làm như vậy, nó thuộc vào bạn để đóng băng trước khi chèn. Lưu ý rằng đây không phải là nghiêm chỉnh về hiệu suất, bởi vì các hành động đóng băng một đối tượng không ngay lập tức chỉ đơn giản là liên quan đến lật bit FL_FREEZE trên bitcoin basic.flags có mặt trên mọi đối tượng. Quay lại đầu trang | Đó là tất nhiên một hoạt động giá rẻ.

Cũng nói về hiệu suất, lưu ý rằng nếu bạn định sử dụng khóa chuỗi và bạn đang ở trong phần mã quan trọng về hiệu suất, bạn có thể muốn cố định chuỗi của mình trước khi thực hiện chèn. Nếu bạn không làm vậy, thì một số tiền được kích hoạt, đó là một hoạt động đắt tiền hơn.

Cập nhật @sawa đã chỉ ra rằng để mảng khóa của bạn đơn giản đóng băng có nghĩa là mảng ban đầu có thể bất ngờ ngoài ngữ cảnh sử dụng, điều này cũng có thể gây bất ngờ khó chịu (mặc dù otoh nó sẽ phục vụ bạn ngay để sử dụng một mảng như một khóa băm, thực sự).Do đó, nếu bạn phỏng đoán rằng việc đóng băng hai chiều là cách thoát khỏi điều đó, thì thực tế bạn sẽ phải chịu chi phí hiệu năng đáng chú ý. Trên bàn tay thứ ba, để nó không bị đóng băng hoàn toàn, và bạn nhận được sự kỳ quặc ban đầu của OP. Lạ lùng xung quanh. Một lý do khác cho Matz et al để trì hoãn các trường hợp cạnh này cho lập trình viên.