Module: RubyLabs::HashLab

Defined in:
lib/hashlab.rb

Defined Under Namespace

Classes: HashTable, TableView

Constant Summary collapse

@@tableOptions =

Default options for drawing a hash table on the canvas

{
  :tableX => 20,
  :tableY => 20,
  :cellHeight => 15,
  :cellYSpace => 2,
  :cellWidth => 30,
  :cellColor => :lightgray,
  :textX => 70,
  :maxRows => 26,
}

Instance Method Summary collapse

Instance Method Details

#h(s, n = 10) ⇒ Object

Simple hash function used in the first project, to introduce the idea of hashing. Uses the first letter in tring s to find where it would go in a table of size n (which has a default value of 10).

Example:

>> ?z.ord
=> 25
>> h("zymurgy")
=> 5
>> h("zymurgy", 15)
=> 10

– :begin :h



126
127
128
 
# File 'lib/hashlab.rb', line 126

def h(s, n = 10)
  return s[0].ord % n
end

#h0(s, n) ⇒ Object

Trival hash function that uses only the first letter in the input string. s is the string to hash, n is the size of the hash table.

Example:

>> ?b.ord
=> 1
>> h0("beer", 10)
=> 1

– :begin :h0



74
75
76
 
# File 'lib/hashlab.rb', line 74

def h0(s, n)
  return s[0].ord % n  
end

#h1(s, n) ⇒ Object

A hash function that uses the first two letters in the input string, weighing the first letter by 26**1 = 26 and the second by 26**0 = 1. s is the string to hash, n is the size of the hash table.

Example:

>> ?b.ord * 26 + ?e.ord
=> 30
>> h1("beer", 10)
=> 0

– :begin :h1



91
92
93
 
# File 'lib/hashlab.rb', line 91

def h1(s, n)
  return ((s[0].ord * 26) + s[1].ord) % n  
end

#hr(s, n) ⇒ Object

A hash function based on the radix-26 representation of the full input string. s is the string to hash, n is the size of the hash table.

Example:

>> radix26("beer")
=> 20401
>> hr("beer", 10)
=> 1

– :begin :hr



107
108
109
 
# File 'lib/hashlab.rb', line 107

def hr(s, n)
  return radix26(s) % n  
end

#insert(s, t) ⇒ Object

Insert string s into array t. The location for s is determined by the hash function implemented in method h.

If s can be added to t (i.e. if there is no collision) return the location where s is stored, otherwise return nil.

This method is intended to be used to demonstrate how hash fucnctions work; for a more complete implementation see HashTable#insert.

Example:

>> t = Array.new(10)
=> [nil, nil, nil, nil, nil, nil, nil, nil, nil, nil]
>> insert("delta", t)
=> 3
>> t
=> [nil, nil, nil, "delta", nil, nil, nil, nil, nil, nil]
>> insert("derp", t)
=> nil

– :begin :insert



151
152
153
154
155
156
157
158
159
 
# File 'lib/hashlab.rb', line 151

def insert(s, t)
  i = h(s, t.length)
  if t[i].nil?
    t[i] = s
    return i
  else
    return nil
  end
end

#lookup(s, t) ⇒ Object

Look for string s in array t, returning the location where s is stored if it is in the array, otherwise nil. If s is in t it will be in the row computed by the hash function implmeneted in method h.

This method is for demonstrations of simple hash tables; for experiments use tHashTable#insert and #HashTable#lookup.

Example:

>> t
=> [nil, nil, nil, "delta", nil, nil, nil, nil, nil, nil]
>> lookup("delta", t)
=> 3
>> lookup("epsilon", t)
=> nil

–

:begin :lookup



179
180
181
182
183
184
185
186
 
# File 'lib/hashlab.rb', line 179

def lookup(s, t)
  i = h(s, t.length)
  if t[i] == s
    return i
  else
    return nil
  end
end

#print_row(n, row) ⇒ Object

Helper method called by print_table. Print a row number followed by the contents of the row.



214
215
216
 
# File 'lib/hashlab.rb', line 214

def print_row(n, row)
  printf "%4d: %s\n", n, row.inspect
end

#print_table(t, max = nil) ⇒ Object

Print a nicely formatted representation of table +t. The argument t can be an array or a HashTable object. To make the table structure easier to see only non-empty rows are printed, one row per line. The row number is printed at the front of the line. The optional parameter max is the number of rows to print.

Example:

>> t
=> ["upsilon", nil, nil, "delta", "omega", nil, nil, nil, nil, nil]
>> print_table(t)
   0: "upsilon"
   3: "delta"
   4: "omega"
=> nil



204
205
206
207
208
209
 
# File 'lib/hashlab.rb', line 204

def print_table(t, max = nil)
  t = t.table if t.class == HashTable
  max = t.length unless max
  max.times { |i| print_row(i, t[i] ) unless t[i].nil? }
  return nil
end

#radix26(s) ⇒ Object

Compute the wighted sum of the ordinal values of characters in a string, where the weight for a character is defined by its position in the string: the weight for the character i positions from the right is 26**i. The numeric value of a character is determined by Fixnum#ord, an extension to the Fixnum class, which is defined in rubylabs.rb. Upper and lower case letters are mapped to integer from 0 to 25, while other characters are unchanged.

Examples:

>> radix26("be")
=> 30
>> radix26("bee")
=> 784
>> radix26("beetle")
=> 13792718
>> radix26("beethoven")
=> 242419173737

– :begin :radix26



54
55
56
57
58
59
60
 
# File 'lib/hashlab.rb', line 54

def radix26(s)
  x = 0
  s.each_byte do |b|
    x = x * 26 + b.ord
  end
  return x
end

#view_table(t, userOptions = {}) ⇒ Object

Initialize the RubyLabs Canvas and draw a picture of hash table t. Subsequent calls to this table’s insert method will update the drawing to show where the new item is placed.

Table drawing parameters can be passed as optional arguments. The defaults are:

:tableX => 20
:tableY => 20
:cellHeight => 15
:cellYSpace => 2
:cellWidth => 30
:cellColor => :lightgray
:textX => 70
:maxRows => 26

Example: to make a drawing of a table t, showing only the first 10 rows and using light blue to show empty rows:

>> view_table(t, :cellColor => :lightblue, :maxRows => 10)
=> true



237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
 
# File 'lib/hashlab.rb', line 237

def view_table(t, userOptions = {} )
  options = @@tableOptions.merge(userOptions)
  
  height = 2 * options[:tableX] + options[:maxRows] * (options[:cellHeight] + options[:cellYSpace] )
  Canvas.init(400, height, "HashLab")
  
  Canvas::Font.new('bucketfont', :family => 'Helvetica', :size => 11)
  tbl = t.table
  x0 = options[:tableX]
  x1 = x0 + options[:cellWidth]
  cells = []
  buckets = []
  nrows = min(tbl.size, options[:maxRows])
  
  nrows.times do |i|
    y0 = options[:tableY] + i * (options[:cellHeight] + options[:cellYSpace])
    y1 = y0 + options[:cellHeight]
    cells << Canvas::Rectangle.new(x0, y0, x1, y1)
    if tbl[i]
      buckets << Canvas::Text.new(tbl[i].join(", "), options[:textX], y0, {:font => :bucketfont})
      cells[i].fill = 'white'
    else
      cells[i].fill = options[:cellColor]
    end
  end
  
  t.drawing = TableView.new(cells, buckets, nrows, options)
  return true    
  
end