Class: RubyLabs::HashLab::HashTable

Inherits:
Object
  • Object
show all
Defined in:
lib/hashlab.rb

Overview

HashTable

A HashTable object is an array of strings. When an object is created, it is given a specified number of rows, and each row is initially empty. The class has methods to add strings to the table, look to see if a string is in the table, and various methods for displaying information about the table.

Example:

>> t = HashTable.new(10)
=> #<RubyLabs::HashLab::HashTable: 10 rows, :hr>
>> TestArray.new(5, :cars).each { |x| t.insert(x) }
=> ["oldsmobile", "maserati", "porsche", "lotus", "saturn"]
>> puts t
   2: ["porsche", "lotus"]
   6: ["oldsmobile"]
   7: ["saturn"]
   8: ["maserati"]
=> nil
>> t.lookup("lotus")
=> 2
>> t.lookup("lexus")
=> nil

Constant Summary collapse

@@hash_functions = 
[:h0, :h1, :hr]

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n, f = :hr) ⇒ HashTable

Make a hash table with n rows. Each row is a bucket that will expand to hold new items that hash to that row.

By default the hash function is the one implemented by the method hr. The optional parameter is a symbol specifying an alternative hash function, either :h0 or :h1.



308
309
310
311
312
 
# File 'lib/hashlab.rb', line 308

def initialize(n, f = :hr)
  raise "HashTable: hash function must be one of #{@@hash_functions.inspect}" unless @@hash_functions.include?(f)
  @table = Array.new(n)
  @hash = f
end

Instance Attribute Details

#drawing ⇒ Object

Returns the value of attribute drawing.



300
301
302
 
# File 'lib/hashlab.rb', line 300

def drawing
  @drawing
end

#table ⇒ Object (readonly)

Returns the value of attribute table.



299
300
301
 
# File 'lib/hashlab.rb', line 299

def table
  @table
end

Instance Method Details

#insert(s) ⇒ Object

Add string s to the table. Collisions are resolved by appending s to the end of the bucket in the row for s.



325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
 
# File 'lib/hashlab.rb', line 325

def insert(s)
  i = send(@hash, s, @table.length)
  @table[i] = Array.new if @table[i].nil?
  @table[i] << s
  if @drawing
    options = @drawing.options
    if @drawing.buckets[i]
      @drawing.buckets[i].update( @table[i].join(", ") )
    else
      y0 = options[:tableY] + i * (options[:cellHeight] + options[:cellYSpace])
      @drawing.buckets[i] = Canvas::Text.new(@table[i], options[:textX], y0, {:font => :bucketfont})
      @drawing.cells[i].fill = 'white'
    end
  end
  return i
end

#inspect ⇒ Object

Return a string that contains essential information about a table (number of rows and the hash function used to insert or look up strings).



351
352
353
 
# File 'lib/hashlab.rb', line 351

def inspect
  sprintf '#<RubyLabs::HashLab::HashTable: %d rows, :%s>', @table.size, @hash.to_s
end

#long_rows(cutoff = 5) ⇒ Object

Return a list of indices for buckets that have more than cutoff entries.



381
382
383
384
385
386
387
 
# File 'lib/hashlab.rb', line 381

def long_rows(cutoff = 5)
  rows = Array.new
  @table.each_with_index do |row, i| 
    rows << i if !row.nil? && row.length > cutoff
  end
  return rows
end

#lookup(s) ⇒ Object

Look up string s in the table. Return the row number where s is found, or nil if s is not in the table.



317
318
319
320
 
# File 'lib/hashlab.rb', line 317

def lookup(s)
  i = send(@hash, s, @table.length)
  return ( @table[i] && @table[i].include?(s) ) ? i : nil
end

#print_stats ⇒ Object

Print usage statistics for the table: the lengths of longest and shortest buckets, number of empty buckets, and mean bucket length.



358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
 
# File 'lib/hashlab.rb', line 358

def print_stats
  max = 0
  min = Float::MAX
  nzero = 0
  sum = 0
  @table.each do |bucket|
    n = bucket.nil? ? 0 : bucket.length
    min = n if n < min
    max = n if n > max
    sum += n
    nzero += 1 if n == 0
  end
  printf "shortest bucket: %d\n", min
  printf "longest bucket:  %d\n", max
  printf "empty buckets:   %d\n", nzero
  if max > 0
    printf "mean bucket length:  %.2f\n", sum.to_f / (@table.length - nzero)
  end
  return nil
end

#to_s ⇒ Object

Call HashLab#print_table to display the contents of the table.



344
345
346
 
# File 'lib/hashlab.rb', line 344

def to_s
  print_table(self)
end