Class: DataStructures101::Hash::BaseHashTable
- Inherits:
-
Object
- Object
- DataStructures101::Hash::BaseHashTable
show all
- Includes:
- Enumerable
- Defined in:
- lib/data_structures_101/hash/base_hash_table.rb
Overview
Abstract class for shared HashTable functionalities.
Instance Attribute Summary collapse
Instance Method Summary
collapse
Constructor Details
#initialize(capacity:, prime:, compression_lambda:) ⇒ BaseHashTable
Returns a new instance of BaseHashTable.
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
# 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
|
Instance Attribute Details
#capacity ⇒ Object
15
16
17
|
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 15
def capacity
@capacity
end
|
#compression_lambda ⇒ Object
15
16
17
|
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 15
def compression_lambda
@compression_lambda
end
|
#size ⇒ Object
15
16
17
|
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 15
def size
@size
end
|
Instance Method Details
#[](key) ⇒ Object
48
49
50
|
# 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) ⇒ Object
34
35
36
|
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 34
def []=(key, value)
insert(key, value)
end
|
#delete(key) ⇒ Object
52
53
54
|
# 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 ⇒ Object
56
57
58
59
60
61
62
|
# 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) ⇒ Object
38
39
40
41
42
43
44
45
46
|
# 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)
resize(new_capacity) if @size > @capacity / 2
old_value
end
|