Learn Ruby The Hard Way Ex39 - Understanding Buckets

Question

Can somebody please explain the concept of buckets simply to me. I understand a Dict is an array of arrays, I cannot for the life of me make sense of this first block of code though and can't find anything online that explains num_buckets. If you could explain it line by line that would be great.

module Dict
  def Dict.new(num_buckets=256)
  # Initializes a Dict with the given number of buckets.
  aDict = []
  (0...num_buckets).each do |i|
    aDict.push([])
  end

  return aDict
end

Answer 1

The code is meant to implement a data structure called Hash table. It is the data structure of Ruby's built-in Hash class.

Hash tables use the hashing of keys as indexes. Because there are limited number of possible indexes, collision (i.e, different keys have the same hashing) happens. Separate chaining is one common method for collision resolution. Keys are inserted into buckets. num_buckets here is the number of buckets. Different keys with the same hashing are in the same bucket.

An image illuatrating separate chaining from Wikipedia: