Class: DataStructures101::Hash::BaseHashTable

Inherits:
Object
  • Object
show all
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.



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

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

#hash_lambda ⇒ Object (readonly)

Returns the value of attribute hash_lambda.



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

def hash_lambda
  @hash_lambda
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



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

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

#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