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.



310
311
312
313
314
 
# File 'lib/hashlab.rb', line 310

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.



302
303
304
 
# File 'lib/hashlab.rb', line 302

def drawing
  @drawing
end

#table ⇒ Object (readonly)

Returns the value of attribute table.



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

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.



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

def insert(s)
  i = send(@hash, s, @table.length)
  @table[i] = Array.new if @table[i].nil?
  @table[i] << s
  if @drawing && i < @drawing.buckets.length
    options = @drawing.options
    if @drawing.buckets[i]
      # sprintf "adding '%s' to bucket %d", s, i
      @drawing.buckets[i].update( @table[i].join(", ") )
    else
      # sprintf "new bucket for '%s' in row %d", s, i
      y0 = options[:tableY] + i * (options[:cellHeight] + options[:cellYSpace])
      @drawing.buckets[i] = Canvas::Text.new(@table[i].join(", "), 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).



355
356
357
 
# File 'lib/hashlab.rb', line 355

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.



385
386
387
388
389
390
391
 
# File 'lib/hashlab.rb', line 385

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.



319
320
321
322
 
# File 'lib/hashlab.rb', line 319

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.



362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
 
# File 'lib/hashlab.rb', line 362

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.



348
349
350
 
# File 'lib/hashlab.rb', line 348

def to_s
  print_table(self)
end