class DataStructures101::ProbeHashTable

HashTable implementation using probing strategy for collision-resolution It subclasses Hash::BaseHashTable @author Rene Hernandez @since 0.2

Constants

Sentinel

Attributes

probe_lambda[R]

Public Class Methods

new(capacity: 31, prime: 109_345_121, compression_lambda: nil, probe_lambda: nil) click to toggle source
# File lib/data_structures_101/probe_hash_table.rb, line 13
def initialize(capacity: 31, prime: 109_345_121,
               compression_lambda: nil, probe_lambda: nil)
  super(capacity: capacity, prime: prime,
        compression_lambda: compression_lambda)

  @probe_lambda = probe_lambda

  return unless @probe_lambda.nil?

  @probe_lambda = ->(h, i, cap) { return (h + i) % cap }
end

Private Instance Methods

bucket_delete(hash_code, key) click to toggle source
# File lib/data_structures_101/probe_hash_table.rb, line 52
def bucket_delete(hash_code, key)
  idx = find_slot(hash_code, key)
  return nil if slot_available?(idx)

  value = @table[idx].last
  @table[idx] = Sentinel.instance
  @size -= 1

  value
end
bucket_each() { |first, last| ... } click to toggle source
# File lib/data_structures_101/probe_hash_table.rb, line 63
def bucket_each
  @table.each do |elem|
    next if elem.nil? || elem == Sentinel.instance

    yield(elem.first, elem.last)
  end
end
bucket_find(hash_code, key) click to toggle source
# File lib/data_structures_101/probe_hash_table.rb, line 31
def bucket_find(hash_code, key)
  idx = find_slot(hash_code, key)

  slot_available?(idx) ? nil : @table[idx].last
end
bucket_insert(hash_code, key, value) click to toggle source
# File lib/data_structures_101/probe_hash_table.rb, line 37
def bucket_insert(hash_code, key, value)
  idx = find_slot(hash_code, key)

  unless slot_available?(idx)
    old_value = @table[idx].last
    @table[idx] = [key, value]
    return old_value
  end

  @table[idx] = [key, value]
  @size += 1

  nil
end
find_slot(h, key) click to toggle source
# File lib/data_structures_101/probe_hash_table.rb, line 71
def find_slot(h, key)
  idx = -1

  j = 0
  loop do
    i = @probe_lambda.call(h, j, @capacity)
    if slot_available?(i)
      idx = i if idx == -1
      break if @table[i].nil?
    elsif @table[i].first == key
      return i
    end
    j += 1
  end

  idx
end
slot_available?(i) click to toggle source
# File lib/data_structures_101/probe_hash_table.rb, line 89
def slot_available?(i)
  @table[i].nil? || @table[i] == Sentinel.instance
end