"""
 hash_table_template.py

 Your mission, should you decide to accept it: 
 implement a hash table ADT in python, with keys as strings.

 This file is a starting place.

 You'll need to pick

   (a) a hash function
       See https://en.wikipedia.org/wiki/Hash_table#Hashing

   (b) a collision resolution recipe
       See https://en.wikipedia.org/wiki/Hash_table#Collision_resolution 
       i.e. one of
       - separate chaining
            - with a python list
            - with a linked list
       - open addressing , with a scheme like
            - linear probing 
            - quadratic probing
            - double hashing
       This is related to the "birthday problem"; 
       let's discuss that if you haven't seen it before.

   (c) dynamic resizing of the array
       See https://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing
       - perhaps double array size when array is 60% full
       - ... but for a first pass, skip this part and instead
         just pick an array about twice as big as the total
         number of things that might go in it

 I suggest starting with some simple choices, 
 getting that to work, then seeing where that goes.

 We may have some sort of race to see whose code is fastest ...
 we'll see.

 Start by making a copy of this file with a different name,
 and adding your name(s) here.

 Jim Mahoney | cs.bennington.college | MIT License | March 2021 
"""

def hash_function(string):
    """ Given a string, return a (largish) integer hash value """
    # TODO : implement one and test it. (See ./hash_functions)
    return 0

class HashTable:
    """ a hash table (python dictionary) with "get" and "set" methods """

    def __init__(self):
        """ create an initially empty hash table """
        # TODO :
        # (1) pick an initial value of n, the number of bins
        #     (for a first pass, pick a relatively large number)
        # (2) create an array of of size n, with initially empty slots.
        pass  # ... replace this with your code

    def set(self, key, value):
        """ add a (key,value) to the hash table """
        # TODO :
        # (0) if there are too many elements, grow the array ...
        #     (but for a first pass, don't do this; just start big)
        # (1) calculate the hash key
        # (2) using that, try to put the (key, value) into the array.
        # (3) if there's a collision, find the next place
        # (4) repeat (3) if need be
        pass

    def get(self, key):
        """ return the corresponding value or None if not found """
        # TODO :
        # (1) calculate the hash key
        # (2) using that, look for that key in the array
        # (3) if that spot is taken, look in the next
        #     ... until its found or not.
        # (4) return the found value or None

def main():
    print("-- hash table testing --")
    hashtable = HashTable()
    # TODO :
    # test it by 
    # (1) generate M randomly chosen words (keys) and values (whatever)
    # (2) and put them into the hash
    # (3a) look them up
    # (3b) look up ones not in the hash
    # (4) Find the time it takes for (2,3a,3b) as a function of M.
    # (5) Print out some sort of summary.

if __name__ == '__main__':
    main()