Brandon Brandon - 1 month ago 17
Ruby Question

Learn ruby the hard way Ex39: Adding key to Array

I'm very stuck at this exercise, so I would be grateful for a very detailed answer.

Question:

At what point is a key added to the aDict array? I can only see the created index of the key being added to the array.
(return aDict [bucket-id]?)

I'm looking at this code:

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

def Dict.delete(aDict, key)
#Deletes the given key from Dict.

bucket = Dict.get_bucket( aDict, key)


(0...bucket.length).each do |i|
k,v = bucket[i]
if key == k
bucket.delete_at(i)
break
end
end
end

def Dict.list(aDict)
#Prints out what's in Dict.

aDict.each do |bucket|

if bucket
bucket.each {|k,v| puts k,v}
end
end
end
end


Let's say I import Dict.rb to another file and I want it to run:

require .\dict.rb

#create mapping of state to abbreviation

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


When is the key (Oregon) in the bucket so that it can be returned by states[index]?

Answer

Ok, so first the structure of the hash table aDict will look like this with some keys in it:

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

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

[2] => []

0,1,2 are the indices. At each index position, you have another array and each element of this array is a two element array containing a key and value. For example, this means that k3 is at aDict[1][0][0]

So, when you want to insert a key and value in the hash, the Dict.set method gets called

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

  bucket = Dict.get_bucket(aDict, key)

get_bucket calculates the first index by taking the mod of the key hash with the size of the array. It then returns the array stored at that index. (For example: bucket = aDict[1])

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

get_slot finds out which index in bucket array has your key and returns the index number along with the key and value. If it does not exist, it returns -1 for no index, the key and the default value (nil)

(For example: i, k, v will be 0, k3, v3 because [k3, v3] is at aDict[1][0]. If you were looking for k4, i, k, v would have been -1, k4, nil)

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

This bit is easy. If i is not -1, then you update the location with your key and value otherwise you push new two element array at the end of the array.

Comments