2010-08-18 42 views
2

說,如果有1000個散列陣列,對像{:id => 1, :name => 'something', :created_at => '2010-08-18'}當我使用一個循環來打印出這些1000條記錄,據說,散列的鍵/值對順序不保證爲什麼Ruby的1000個哈希數組中的鍵和值對總是按特定順序排列?

,但打印出的該表,它總是以相同的順序出現。爲什麼它可以被計算在內?否則,對鍵/值對進行排序有什麼好方法?

(我想映射:id to 10, and :name to 20, and :create_at to 30,然後通過這些映射值的鍵進行排序,以使得:id爲前:姓名,並且是前:created_at)

(散列是由a_hash.each_pair do |k, v| ...打印出來)

+0

你打印出你的散列?你打電話來檢查嗎? – 2010-08-18 20:07:11

+1

*我們在這裏談論什麼* Ruby? MRI 1.8? MRI 1.9? JRuby的? Rubinius的? MacRuby的?像這樣的實現細節必然因實現而異。 – Chuck 2010-08-18 20:08:38

+0

我正在使用'each_pair do | k,v |'請參閱上面的更新 – 2010-08-18 20:48:52

回答

3

散列的佈局是確定性。因此,對於某個特定版本的ruby,如果你總是以相同的順序添加/刪除一個哈希鍵,哈希的佈局將是相同的。這意味着遍歷數組中的哈希將具有所有按照相同順序的鍵。

+0

+1「不保證」意味着難以預測,而不是隨機的。 – 2010-08-18 20:38:08

1

紅寶石hashmaps(和hashmaps一般)沒有暗示的按鍵排序。但是,它們的實現方式可以使獲得一個關鍵值的高效操作(攤銷O(1))時間。

因此,在底層實現中,鍵總是以相同的方式構造,這使得它們看起來有順序。

0

雖然Ruby 1.9確實保留了插入順序,但Ruby並不保證哈希鍵的排序。

如果要以特定但任意的順序處理哈希鍵,最好的方法是創建一個指定順序的數組。所以你可能有一個像[:id, :name, :create_at]這樣的數組。如果你想按字母順序處理哈希,你可以使用sort,它會按順序爲你提供一組鍵值對。

0

爲什麼它可以算作?

任何哈希將有一個「自然排序」。

「自然排序」既可以在每個元素被插入時執行,也可以在第一次搜索之前執行。

如果沒有自然排序返回匹配特定鍵的值將需要詳盡的搜索。

的窮舉搜索,當然,將取n的比較,其中n是在哈希元素的數量(例如:65536個元件65536點的比較檢索。)

在另一方面,如果散列進行排序按KEY按字母順序排列,則二進制搜索可以在LOG2(n)比較中找到匹配項。 (例如在16個比較中搜索65536個元素)。

還有其他的排序方法,但它們都需要一些初始排序。這種排序可能是一個帶有隱藏索引的系統,它將鍵/值對元素排序。

例如在下面的部分實現中,鍵/值對作爲對象存儲在底層數組中。

myArray[0] = {"b", "Skies"} 
myArray[1] = {"c", "dog"} 
myArray[2] = {"a", "Jax"} 
myArray[3] = {"d", "gone"} 
myArray[4] = {"r", "run"} 
myArray[5] = {"q", "quit"} 

的第二陣列中,向其中紅寶石顯影劑沒有訪問,保持排序。

sortArray[0] = 2 
sortArray[1] = 0 
sortArray[2] = 1 
sortArray[3] = 3 
sortArray[4] = 4 
sortArray[5] = 5 

因此,內部到哈希對象

for(i=0 to 5) 
    print myArray[sortArray[i]] 

將打印的排序後的數組。

Ruby的規範顯然沒有指定使用哪種方法,按鍵排序,隱藏排序或其他方法,因此,不,您不能指望自然排序。

1

documentation在ruby-doc.org爲Ruby 1.9(不知道這是否是1.9.0或1.9.1)錯誤地認爲

中,你通過任何鍵或值遍歷一個哈希 順序可能看起來是 任意,並且在插入順序中通常不會是 。

但是1.9.1新聞says

哈希保持秩序。它按插入的鍵號 的順序列舉其元素。

我看了一下紅寶石的樹幹(什麼正在開發),它說

散列枚舉 爲了他們的價值是對應的鍵是 插入。

對文檔的更改是在September 25, 2009 commit中修復了不正確的文檔。

我不是100%確定有序的枚舉是ruby 1.9.1規範的一部分。 Rubyspec將是一種檢查方式。但是,如果主要實現提供了合同,那麼除非明確地另有說明,否則您會希望任何其他實施遵守該合同。

相關問題