Contents

require 'singleton'

module DataStructures101
    class ProbeHashTable < Hash::BaseHashTable

        attr_reader :probe_lambda

        def initialize(capacity = 31, prime = 109345121, 
                        hash_lambda = nil, probe_lambda = nil)
            super(capacity, prime, hash_lambda)

            @probe_lambda = if probe_lambda.nil?
                                ->(h, i) { return (h + i) % @capacity }
                            else
                                probe_lambda
                            end
        end

        private

        Sentinel = Class.new do 
            include Singleton
        end

        def bucket_find(hash_code, key)
            idx = find_slot(hash_code, key)
            
            slot_available?(idx) ? nil : @table[idx].last
        end

        def bucket_insert(hash_code, key, value)
            idx = find_slot(hash_code, key)

            if !slot_available?(idx)
                old_value = @table[idx].last
                @table[idx] = [key, value]
                return old_value
            end
            
            @table[idx] = [key, value]
            @size += 1

            nil
        end
        
        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

        def find_slot(h, key)
            idx = -1

            j = 0
            loop do
                i = @probe_lambda.call(h, j)
                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

        def slot_available?(i)
            @table[i].nil? || @table[i] == Sentinel.instance
        end
    end
end

Version data entries

1 entries across 1 versions & 1 rubygems

Version	Path
data_structures_101-0.2.1	lib/data_structures_101/probe_hash_table.rb