Class: DataStructures101::Hash::BaseHashTable

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

Overview

Abstract class for shared HashTable functionalities.

See Also:

Author:

  • Rene Hernandez

Since:

  • 0.2

Direct Known Subclasses

ChainedHashTable, ProbeHashTable

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

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

Returns a new instance of BaseHashTable.

Since:

  • 0.2



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 (readonly)

Since:

  • 0.2



15
16
17
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 15

def capacity
  @capacity
end

#compression_lambda ⇒ Object (readonly)

Since:

  • 0.2



15
16
17
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 15

def compression_lambda
  @compression_lambda
end

#size ⇒ Object (readonly)

Since:

  • 0.2



15
16
17
 
# File 'lib/data_structures_101/hash/base_hash_table.rb', line 15

def size
  @size
end

Instance Method Details

#[](key) ⇒ Object

Since:

  • 0.2



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

Since:

  • 0.2



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

Since:

  • 0.2



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

Since:

  • 0.2



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

Since:

  • 0.2



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)

  # Keep load factor below 0.5.
  resize(new_capacity) if @size > @capacity / 2

  old_value
end