寫在前面
這篇是翻譯LearnRubyTheHardWay, Exercise 39: Hashes, Oh Lovely Hashes的後半段,因為對我來說實在有點難搞懂,就花了點時間翻譯與反覆推敲,來檢視我是否了解這個概念,Array跟Hash也是Ruby中滿核心的組成,完全搞懂是必要的,其實這段滿有意思的,程式碼部分就沒有貼過來了。
建立屬於你自己的Hash Module
本練習的最後一段程式碼,讓你知道如何僅僅利用array來達到與Hash相同的資料結構組成,這段程式碼或許不好理解,但請耐下性子花點時間把它搞懂,這段程式碼裡也並沒有引入任何新的概念,但是具有一定的複雜度,也有些部分需要你額外在做些參考資料的尋找。
這個Hash module將命名為Dict
,是與Hash
有相同資料結構的別名,指的也就是一對一的映對關係,檔案請命名為dict.rb
,後面會在範例檔ex39_test.rb
中使用。
程式碼說明
” Dict
其實只不過是由一堆bucket所組成的array,bucket中有一個個slot,而這些slot中存放著key/value對 “,讓我花個幾分鐘來拆解上面這段論述。
“一堆bucket所組成的array“
在Dict
function裡,先生成一個array叫aDict
,接著在這個array中再塞進更多的array!
[[] [] [] [] [] [] ....]
“bucket由一個個slot組成”
而這些更多的array(bucket),一開始都是空的,但當我們在bucket中這些slot塞進key/value對的時候....
[[slot, slot] [] [] [] [] [] ....]
”這些slot當中存放著key/value對“
指的是每個slot中都存在著一個(key, value)
元組(tuple)或pair。
如果對於上述的這種資料結構,仍沒有任何感覺,沒關係慢慢來,試著動手在紙上畫看看,直到你搞懂它!事實上,動手在紙上描繪出來或寫出來,是個理解演算法的好方式。
現在你已經知道資料的結構組成,再來你只需要知道演算法中的每個操作。而演算法是由步驟操作與資料結構所組成,也是讓這個資料結構可以正常運作的程式碼。我們將透過編寫程式碼來實現每個操作,而Dict
的說明如下:
- 將key轉換成一個integer,轉換的方式是利用function:
hash_key
。 - 將這個hash轉換成一個bucket number,轉換的方式是利用
% (modulus)運算子
- 從
aDict
這個array所包含的眾多bucket中取得該bucket,再取得裡面的slot,再找到我們所需要的key!
在'set'這個function中,我們所做的是取代原本或以append的方式加入新的key。
接下來透過說明Dict中的各個function讓你瞭解到底發生了什麼事,確認你搞懂每行程式碼,並在旁寫下註解確認你完全瞭解了,我建議你可以花點時間在Ruby shell試試看這些程式碼的作用或試著在紙上練習看看。
new
首先建立一個function來為你新增一個Dict,也稱為initializer。我所做的就是新增一個名為aDict的array,然後再放入數量num_buckets
的array!這些bucket將用來存放Dict的內容,之後在其他function我會使用aDict.length
來確認aDict有幾個bucket存在。hash_key
這個function是一個hash
如何運作的核心概念,其實他做的事是利用一個Ruby內建的function來將一個字串(string)轉換成一組數字。Ruby利用這個function來實作Hash的資料結構,這邊只是重新引用這個方式,建議你應該開一個Ruby console來試著操作看看,瞭解一下他如何運作的,一旦我取得這組數字作為key,我再借用一個%
的運算子與aDict.length
運算,將原本很龐大的一組數字轉換成相當較小的一組數字,最後得到我可使用的key,如果不太清楚上述的轉換過程,建議可利用Ruby console實作做看看這個過程。get_bucket
之後由這個function利用hash_key
找到包含我們需要的key的對應bucket,而由於我們在hash_key中利用%
與aDict.length
做了一些轉換,我知道不管我得到什麼bucket_id
都可以讓我對應到aDict
array中的位置,利用這個bucket_id就可以找到需要的key所對應的該bucket。get_slot
這個function先用get_bucket
找到所需bucket,然後搜尋bucket中的每個元素直到找到符合的key,一旦找到,就會回傳(i,k,v)
,也就是index,key本身,與其映對的value。現在你應該可以知道這個資料結構是如何運作的。這個過程透過key與hash的轉換找到bucket,再搜尋該bucket找到目標。透過這些function執行有效率分工達到資料結構上必要的搜尋,最後找到目標資料。get
這事實上是大部分使用者希望透過Dict
能實現的function。利用了get_slot
找到(i,k,v)
,然後僅回傳v
也就是value,確認你已了解default變數的運作原理,與get_slot
中的(i,k,v)
是如何放到get
的i, k, v
中。set
要設定或存放一組key/value對,首先找到bucket然後在將新的(key, value)以append的方式丟進去,這樣之後就可以取用。但我們這裡希望Dict一次只允許存在一個key,為了滿足這個條件,就必須先找到bucket確認這個key是否已經存在,如果是就直接以我們設定的(key, value)取代,如果不是那就以append的方式丟進去。這種方式的執行速度會比以單純appending的方式慢一些,但可能會更貼近使用者對於Dict運作方式的期待。而如果你希望一個key可以映對取得不只一個的value,只要讓get
搜尋該bucket的每一個slot後,回傳一結果array即可,這裡是個設計module上的參考示範。目前是get
的執行速度上比較快,而set
相對慢一些。delete
要刪除一個key,我只需要找到bucket,找尋到bucket對應的那個key,將他從array中刪除即可,但這是因為在這裡我選擇讓set
只允許每個key僅存在一key/value對,所以我只要找到對應的key刪除就結束了,但是如果我決定讓每個key可以有多個不同的value的話(也就是在set
終以單純appending的方式,而先不確認key是否唯一),delete
的設計就必須搜尋bucket中的每個slot完後,找到對應的key把他砍掉,而這會讓delete的執行變慢。list
最後一個function只是個小小的debug功能,可以列出Dict
中的物件,找到每個bucket,然後走遍bucket的每個solt。
最後ex39_test.rb
是一段測試碼來驗證這些function正常運作。
三層Array!(Three Levels of Arrays)
[[slot, [] ] [] [] [] [] [] ...]
如同在先前討論中所提到的,set
會以新的value覆寫或取代原本key所對應的value,在這個例子中,我已經設計讓set
的執行速度慢一些,但這代表其他的function會跑快一些,但如果我很想讓Dict
這個類別的每個key都可以具有多個value呢?
我需要做的就是在每個bucket中的slot改成可存放多個value的array。這表示我要加入第三層的bucket,接著slot中改放一個可存放多個value的array。這也符合先前我對於這種Dict的描述,"每個key可以具有多個values",或者說是"每個key都有映應一個存放多個value的array",一個slot放key,而另一個slot改成可存放多個value的array,就完成啦!
如果你想做更進一步的研究,可以試著改寫程式碼,使每個key都可以有多個values吧。
什麼時候該用Hash?什麼時候該用Array?
如同在練習38所提到的,array具備一些特性可幫助你以array的資料架構形式保存或組織資料,Hash也是,但他所具備的特性與array有些不同,因為他是由key映對到values,也就說在下列情況你會使用到hash:
- 你需要基於一些非整數的identifier幫助你取得映對的資料,像是姓名、地址、或任何可以當作key的東西。
- 你不需要資料有順序(order)的排列時,Hash中沒有順序的概念,而array有。
- 你需要新增或移除資料中的各個value與其映對的key。
也就是說當你需要用非整數的key時,使用hash,而如果你希望存放的資料是依順序排列,使用array。