hashMap.py

1.) What does a hashmap do? What are the methods that the client will use?
Hash Map are data structures that store key-value pairs. They perform get, put and contains operations all in O(1) runtime in the average case..

2.) Describe how a hashmap works concisely. Use less than 150 characters.
With a hash map, we store all of the keys and values in an array. To find the array index that a given key-value pair is stored, we will rely on 
a hash function to compte this array index

3.) What is a hash function?
A hash function is just a function that takes in a key and returns an integer value that is in the range [0,1,2,...., M-1].

4.) What is the most important quality of a good hash function?
- Deterministic = the same key wil always produce the same hash value
- Efficient = It should be fast to compute
- Uniform = The hash function should distribute the keys uniformly
  
5.) Please write a good hash function for the following keys. Keep in mind the property you listed in (4)
- Strings
                  def hash_string(string_key):
                    M = 1001
                    # R is the size of the alphabet. Because we are working with ASCII 257, we set R = 256
                    R = 256
                    hash_value = 0
                    for char in string_key:
                      hash_value = (hash_value * R + int(char)) % M
                    return hash_value

- Float numbers
                      import math
                      def hash_modulo(float_key):
                        # set M equal to a large prime number
                        M = 97
                        return  math.floor(integer_key % 97)

- The following cat object. Similar to above!
  class Cat:
    def __init__(self, name, age):
      self.name = name # string
      self.age = age       # int
      
 6.) What is the runtime of a hashmap’s get method in the average case? 
O(1) runtime

7.) What is the runtime of a hashmap’s insert method in the average case? 
O(1) runtime.
  
8.) What is the runtime of the insert function in the worst-case?
O(N)

9.) What type of input would give you the worst-case runtime for a hashmap? Describe this one in English.
When its mappped to same key-value air. And in fact turns into a linked list

10.) Please provide an example of the worst-case input (let’s say for size N = 10) for each of the hash functions  on one of the hash functions you provided in (5)
            # Hash returns the current time in seconds mod 97.
            def non_deterministic_hash(integer_key):
              M = 97
              current_time_int = int(time.time())
              return current_time_int % 97  
          
11.) What are the tradeoffs between linear probing and separate chaining? What types of inputs will have better performance for one over the other? 
Please provide a sample input for each example
Takes O(N) runtime for every get and put operation 

class Node:
    def __init__(self, key, value):
        self.key = key
        self.val = value
        self.next = None
        
class SearateChainingHashMap:
    # initialize HashMap
    def __int__(self, capacity):
        #O(capacity) rt
        #O(capacity) space
        self.map = [Node("dummy", "dummy") for _ in range(capacity)]
        
    # returns index that key is stored
    def hashedIndex(self, key):
        return key % len(self.map)
        
    # adds an item to the hash map. uses separate chaining for collisions   
    def put(self, key, val):
        #O(N)/capacity RT
        #O(1) space
        idx = self.hashIndex(key)
        cur = self.map[idx]
        while(cur.next):
            if cur.next.key == key:
                cur.next.val = val
                return
            cur = cur.next
        cur.next = Node(key, val)
        
    # finds item with given key and returns associated val    
    def get(self, key):
        #O(N)/capacity RT
        #O(1) space
        idx = self.hashedIndex(key)
        cur = self.map[idx]
        while(cur.next):
            if cur.next.key == key:
                return cur.next.val
            cur = cur.next
    
    # deletes a key and its val from teh HashMap        
    def delete(self, key):
        idx = self.hashedIndex(key)
        prev = self.map[idx]
        cur = prev.next
        while(cur):
            if cur.key == key:
                prev.next = cur.next
            prev = cur
            cur = cur.next