The goal is to implement a datatype called Tracker that we can use to keep track of how many times a string appears in a list. For example, if we were given a list such as ['a','b','a'] we want to know that 'a' appears twice and 'b' appears once. A tracker has two methods, put and get. The put method allows you to use the tracker to record the occurance of string, while the get method returns the count for some string. Here is the abstract data type.

class Tracker:

def put(self,key):

raise MethodImplementationMissing('put')

def get(self,key):

raise MethodImplementationMissing('get')

One possible way to implement Tracker is to use a list of all the strings that we put in the tracker. A slightly better, yet still naive, implementation would record what strings have been put in the tracker so far, and record the number of occurences. Here is a possible implementation.

class naiveImplementation(Tracker):

def __init__(self):

self.keys = []

self.counts = []

def get(self,key):

try:

index = self.keys.index(key)

return self.counts[index]

except ValueError:

return 0

def put(self,key):

try:

index = self.keys.index(key)

value = self.counts[index] + 1

self.counts.insert(index,value)

except ValueError:

self.keys.append(key)

self.counts.append(1)

def print(self):

print(self.counts)

print(self.keys)

We can declare a new tracker.

naive_tracker = naiveImplementation()

And try it out on our example.

l = ['a','b','a']

for key in l:

naive_tracker.put(key)

print('a:', naive_tracker.get('a'))

print('b:',naive_tracker.get('b'))

print('c:',naive_tracker.get('c'))

Output:

a: 2 b: 1 c: 0 

We use a hash table with linear chaining to implement a slightly better tracker. To that end, we need to be bale to hash strings. This can be done very easily using python's hash function.

example = 'hello, world!'

print(hash(example))

Output:

8072055050985534680 

In practice, we want to set the size of our hash table to a chosen fixed size, so the numbers returned by hash are too large.

**PROBLEM 1) Implement a my_hash function that hashes a string and ensures that the returned hash is less than size.

def my_hash(string,size):

#pass

**Below is the implementation of the Tracker data type using a hash table with linear chaining.

class LinearChaining(Tracker):

def __init__(self,size):

#pass

self.hashTable = [[] for i in range(size)]

self.size = size

def get(self,key):

#pass

index = my_hash(key, self.size)

chain = self.hashTable[index]

for i in chain:

if (i[0] == key):

return item[1]

return 0

def put(self,key):

#pass

ix = my_hash(key, self.size)

c = self.hashTable[ix]

if len(c) == 0:

c.append([key, 1])

else:

for i in range(len(c)):

if (c[i][0] == key):

c[i][1] += 1

return

c.append([key, 1])

#PROBLEM 2) Implement a tracker that does not store the strings at all. Note that you are allowed to make a few and rare small errors where a string might be counted too many times.

Both problems need to be implemented in Python.