Class: HashMap

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/simms_structures/hash_map.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(num_buckets = 8) ⇒ HashMap

Returns a new instance of HashMap.



10
11
12
13
 
# File 'lib/simms_structures/hash_map.rb', line 10

def initialize(num_buckets = 8)
  @store = Array.new(num_buckets) { LinkedList.new }
  @count = 0
end

Instance Attribute Details

#count ⇒ Object (readonly)

Returns the value of attribute count.



8
9
10
 
# File 'lib/simms_structures/hash_map.rb', line 8

def count
  @count
end

Instance Method Details

#bucket(key) ⇒ Object 



69
70
71
 
# File 'lib/simms_structures/hash_map.rb', line 69

def bucket(key)
  @store[key.hash % num_buckets]
end

#delete(key) ⇒ Object 



29
30
31
 
# File 'lib/simms_structures/hash_map.rb', line 29

def delete(key)
  @count-= 1 if bucket(key).remove(key)
end

#each(&block) ⇒ Object 



33
34
35
36
37
38
39
 
# File 'lib/simms_structures/hash_map.rb', line 33

def each(&block)
  @store.each do |bucket|
    bucket.each do |link|
      block.yield(link.key, link.val)
    end
  end
end

#get(key) ⇒ Object Also known as: [] 



25
26
27
 
# File 'lib/simms_structures/hash_map.rb', line 25

def get(key)
  bucket(key).get(key)
end

#include?(key) ⇒ Boolean

Returns:

  • (Boolean) 


15
16
17
 
# File 'lib/simms_structures/hash_map.rb', line 15

def include?(key)
  bucket(key).include?(key)
end

#num_buckets ⇒ Object

private



53
54
55
 
# File 'lib/simms_structures/hash_map.rb', line 53

def num_buckets
  @store.length
end

#resize! ⇒ Object 



57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/simms_structures/hash_map.rb', line 57

def resize!
  old_store = @store
  @store = Array.new( num_buckets * 2 ) { LinkedList.new }
  @count = 0

  old_store.each do |bucket|
    bucket.each do |link|
      self[link.key] = link.val
    end
  end
end

#set(key, val) ⇒ Object Also known as: []= 



19
20
21
22
23
 
# File 'lib/simms_structures/hash_map.rb', line 19

def set(key, val)
  resize! if @count == num_buckets
  include?(key) ? delete(key) : (@count += 1)
  bucket(key).insert(key, val)
end

#to_s ⇒ Object 



41
42
43
44
45
46
 
# File 'lib/simms_structures/hash_map.rb', line 41

def to_s
  pairs = inject([]) do |strs, (k, v)|
    strs << "#{k.to_s} => #{v.to_s}"
  end
  "{\n" + pairs.join(",\n") + "\n}"
end