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 = nil) ⇒ BaseHashTable

Returns a new instance of BaseHashTable.



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

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



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

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

#[]=(key, value) ⇒ Object 



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

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

#delete(key) ⇒ Object 



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

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

#each ⇒ Object 



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

def each
    return enum_for(:each) unless block_given?

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

#insert(key, value) ⇒ Object 



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

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