class DataStructures101::Hash::BaseHashTable

Abstract class for shared HashTable functionalities. @see ChainedHashTable @see ProbeHashTable @author Rene Hernandez @since 0.2

Attributes

capacity[R]
compression_lambda[R]
size[R]

Public Class Methods

new(capacity:, prime:, compression_lambda:) click to toggle source
# File lib/data_structures_101/hash/base_hash_table.rb, line 17
def initialize(capacity:, prime:, compression_lambda:)
  @capacity = capacity
  @size = 0
  @table = Array.new(@capacity)

  @compression_lambda = compression_lambda

  return unless @compression_lambda.nil?

  random = Random.new
  scale = random.rand(prime - 1) + 1
  shift = random.rand(prime)
  @compression_lambda = lambda do |key, cap|
    return (((key.hash * scale + shift) % prime) % cap).abs
  end
end

Public Instance Methods

[](key) click to toggle source
# File lib/data_structures_101/hash/base_hash_table.rb, line 48
def [](key)
  bucket_find(compression_lambda.call(key, @capacity), key)
end
[]=(key, value) click to toggle source
# File lib/data_structures_101/hash/base_hash_table.rb, line 34
def []=(key, value)
  insert(key, value)
end
delete(key) click to toggle source
# File lib/data_structures_101/hash/base_hash_table.rb, line 52
def delete(key)
  bucket_delete(compression_lambda.call(key, @capacity), key)
end
each() { |key, value| ... } click to toggle source
# File lib/data_structures_101/hash/base_hash_table.rb, line 56
def each
  return enum_for(:each) unless block_given?

  bucket_each do |key, value|
    yield(key, value)
  end
end
insert(key, value) click to toggle source
# File lib/data_structures_101/hash/base_hash_table.rb, line 38
def insert(key, value)
  hash_code = compression_lambda.call(key, @capacity)
  old_value = bucket_insert(hash_code, key, value)

  # Keep load factor below 0.5.
  resize(new_capacity) if @size > @capacity / 2

  old_value
end

Private Instance Methods

new_capacity() click to toggle source
# File lib/data_structures_101/hash/base_hash_table.rb, line 66
def new_capacity
  2 * @capacity - 1
end
resize(new_cap) click to toggle source
# File lib/data_structures_101/hash/base_hash_table.rb, line 70
def resize(new_cap)
  @capacity = new_cap

  buffer = map { |key, value| [key, value] }

  @table = Array.new(@capacity)
  @size = 0

  buffer.each { |key, value| self[key] = value }
end