ルビーの難しい方法を学ぶEx39：配列にキーを追加する

Question

私はこの演習で非常に固執していますので、非常に詳細な答えに感謝します。

質問：

aDict配列にどのような点が追加されましたか？私は作成されたキーのインデックスが配列に追加されているのを見ることしかできません。 （aDict [バケット-ID]を返す？）

私はこのコードを探しています：

module Dict 

    def Dict.new(num_buckets = 256) 
    #Initializes Dict with the given number of buckets. 

    aDict = [] 

    (0...num_buckets).each do |i| 
     aDict.push([]) 
    end 

    return aDict 
    end 

    def Dict.hash_key(aDict,key) 
    #given a key this will create a number 
    #turning it into an index for one of aDicts buckets 

    return key.hash % aDict.length 
    end 

    def Dict.get_bucket(aDict, key) 
    #Given a key, find the bucket where it would go. 

    bucket_id = Dict.hash_key(aDict,key) 
    return aDict[bucket_id] 
    end 

    def Dict.get_slot(aDict, key, default=nil) 
    #Returns the index, key and 
    #value of a slot found in a bucket. 

    bucket = Dict.get_bucket(aDict,key) 

    bucket.each_with_index do |kv, i| 
     k, v = kv 
     if key == k 
     return i, k, v 
     end 
    end 

    return -1, key, default 
    end 

    def Dict.get(aDict, key, value) 
    #Gets the value in a bucket for the given key or the default 

    i, k, v = Dict.get_slot (aDict,key, Value, default = default) 
     return v 
    end 

    def Dict.set(aDict,key,value) 
    #Sets the key to the value, 
    #replacing any existing value. 

    bucket = Dict.get_bucket(aDict, key) 

    i,k,v = Dict.get_slot(aDict, key) 

     if [i] >= 0 
     bucket[i] = [key,value] 
     else 
     bucket.push([key,value]) 
     end 
    end 

はのは、私は別のファイルにDict.rbをインポートし、私はそれを実行したいとしましょう：

require .\dict.rb 

#create mapping of state to abbreviation 

states Dict.new() 
Dict.set(states, Oregon, OR) 

バケット内のキー（オレゴン）がaDict [bucket_id]によって返されるのはいつですか？

Answer 1

オクラホマので、最初のハッシュテーブルaDictの構造が、その中にいくつかのキーで次のようになります。

[0] => [[k1, v1], [k2, v2]] 

[1] => [[k3, v3]] 

[2] => [] 

0,1,2はインデックスです。各インデックス位置に別の配列があり、各要素がの場合配列はキーと値を含む2要素配列です。あなたは、ハッシュ内のキーと値を挿入したい場合たとえば、これはk3だからaDict[1][0][0]

であることを意味し、Dict.set方法は

def Dict.set(aDict,key,value) 
    #Sets the key to the value, 
    #replacing any existing value. 

    bucket = Dict.get_bucket(aDict, key) 

get_bucketはMODを取ることによって、最初のインデックスを算出し、呼び出されますキーのハッシュ値を配列のサイズと比較します。次に、そのインデックスに格納されている配列を返します。 （例：bucket = aDict[1]）

i,k,v = Dict.get_slot(aDict, key) 

get_slot

は鍵を持っており、キーと値とともにインデックス番号を返しbucketアレイ内のどのインデックス見つけ出し。それが存在しない場合、それは-1を返していないインデックスのために、キーとデフォルト値（nil）

（例：[k3, v3]がaDict[1][0]であるため、i, k, vは0, k3, v3になりますあなたがk4を探していた場合は、i, k, vだろう。ありました-1, k4, nil）

if i >= 0 
     bucket[i] = [key,value] 
    else 
     bucket.push([key,value]) 
    end 
end 

このビットは簡単です。 iが-1でない場合は、キーと値で位置を更新します。そうでない場合は、配列の最後に新しい2要素配列を押します。