HashTable

Question 1

Hash Table

Separate Chaining LinkedList

Answer 1

Find: O(n) — If all the keys mapped to the same index (assuming Linked List) Insert: O(n) — If all the keys mapped to the same index (assuming Linked List) and we check for duplicates

Remove: O(n) — If all the keys mapped to the same index (assuming Linked List

class Node
attr_accessor :value, :next
def initialize(v)
@value = v
@next = nil
end
end

class SeparateChaining
attr_reader :array
H = 31
def initialize
@array = Array.new(137)
end

def better_hash_function(s)
total = 0
for i in (0…s.size) do
total = total*H + s[i].ord
end
return total % @array.size
end

def put(s)
pos = self.better_hash_function(s)
if @array[pos].nil?
@array[pos]= Node.new(s)
else
current_node = @array[pos]
while current_node.next
current_node = current_node.next
end
current_node.next = Node.new(s)
end
end
def get(key)
pos = self.better_hash_function(key)
current_node = @array[pos]
while current_node
return current_node.value if current_node.value == key
current_node = current_node.next
end
return nil
end

def show
for i in (0…@array.size) do
p @array[i] unless @array[i].nil?
end
end
end