Springok's Blog

LearnRubyTheHardWay, Exercise 39: Hashes, Oh Lovely Hashes

| Comments

寫在前面

這篇是翻譯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的說明如下:

  1. 將key轉換成一個integer,轉換的方式是利用function: hash_key
  2. 將這個hash轉換成一個bucket number,轉換的方式是利用% (modulus)運算子
  3. 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)是如何放到geti, 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。

Comments

comments powered by Disqus