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