Class: DataStructures101::Hash::BaseHashTable

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/data_structures_101/hash/base_hash_table.rb

Direct Known Subclasses

ChainedHashTable, ProbeHashTable

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(capacity:, prime:, hash_lambda:) ⇒ BaseHashTable

Returns a new instance of BaseHashTable.



8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 8

def initialize(capacity:, prime:, hash_lambda:) 
    @capacity = capacity
    @size = 0
    @table = Array.new(@capacity)
               
    @hash_lambda = hash_lambda
    
    if @hash_lambda.nil?      
        random = Random.new
        scale = random.rand(prime - 1) + 1
        shift = random.rand(prime)                             
        @hash_lambda = ->(key) { return (((key.hash * scale + shift) % prime) % @capacity).abs }
    end
end

Instance Attribute Details

#capacity ⇒ Object (readonly)

Returns the value of attribute capacity.



6
7
8
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 6

def capacity
  @capacity
end

#hash_lambda ⇒ Object (readonly)

Returns the value of attribute hash_lambda.



6
7
8
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 6

def hash_lambda
  @hash_lambda
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



6
7
8
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 6

def size
  @size
end

Instance Method Details

#[](key) ⇒ Object 



36
37
38
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 36

def [](key)
    bucket_find(hash_lambda.call(key), key)
end

#[]=(key, value) ⇒ Object 



23
24
25
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 23

def []=(key, value)
    insert(key, value)
end

#delete(key) ⇒ Object 



40
41
42
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 40

def delete(key)
    bucket_delete(hash_lambda.call(key), key)
end

#each ⇒ Object 



44
45
46
47
48
49
50
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 44

def each
    return enum_for(:each) unless block_given?

    bucket_each do |key, value|
        yield(key, value) 
    end
end

#insert(key, value) ⇒ Object 



27
28
29
30
31
32
33
34
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 27

def insert(key, value)
    old_value = bucket_insert(hash_lambda.call(key), key, value)

    # keep load factor <= 0.5
    resize(new_capacity) if @size > @capacity / 2

    old_value
end