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
Calls superclass method
DataStructures101::Hash::BaseHashTable::new
# 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