Table of Contents

• Overview / Logistics
  • Learning Objectives
  • Data / Starter Code
  • What To Submit
• Programming Tasks
  • Part 1: Hash Codes And Object Equality in Python (6 Points)
  • Part 2: HashSet (24 Points)
  • Part 3: HashMap (17 Points)
  • Part 4: Rebalancing (10 Points)
  • Part 5: Russian Troll Tweet Wrangling (15 Points)

Overview / Logistics

The purpose of this assignment is to implement one of the most important data structures in all of CS: a hash map, which is actually quite simply just an array of singly-linked lists. This will enable us to implement two abstract data types (ADTs): the Set and the Map (also known as a dictionary in python), which both have tons of applications. Before you proceed, review the notes at this link, which cover the background for hash tables.

Learning Objectives

• Implement a singly-linked list in python
• Implement hash tables using pythonic object oriented paradigms
• Use hash table to fulfill set and map ADTs, including exception handling
• Apply the dictionary API to natural language processing

Data / Starter Code

Click here to download the starter code for this assignment. Actually, the starter code is quite minimal; it mainly has a dataset you'll be using in the last task.

What To Submit

Submit your files wizard.py and hash.py to canvas, as well as any other .py files and notebooks you made. Also submit answers to the following questions on Canvas

1. The name of your buddy, if you chose to work with one.
2. Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write about it. The more you articulate the problem the more partial credit you will receive (fine to leave this blank)

---

Programming Tasks

To explain the data structures you'll be implementing, let's first look at python's built in versions of them. First, we'll examine a set, which is a unordered collection of objects without repetition

This prints

Notice how the numbers are not in the same order we put them in (since the set order is arbitrary), and that even though we added 2 twice, it only showed up once (no repetitions).

Actually, the set is quite flexible, and we can add anything to it, as long as it has a hash code. For example, we can add

and then we'll see

But then if we try to do

then we get

This is because a list can change, so it's impossible to generate a unique hash code for it, since one of the properties of hash codes is that they remain fixed, so they can only work with "immutable" objects.

Part 1: Hash Codes And Object Equality in Python (6 Points)

Let's now consider a more interesting class that's been provided with the assignment. I've created a Wizard class in wizard.py that mirrors the Harry Potter hashing class exercise. Let's run the following code from within some .py file or notebook in the same directory as wizard.py:

but then this prints out

It seems like the set's not working, because it's not supposed to have more than one copy of the same object! But let's drill down and look at the hash codes. We can do this by calling the built-in method hash in python:

When I run this, I get the following on my computer (but you will get something different every time you run this, which will become clear in a moment):

What on earth are these numbers, and how did python come up with them? Let's try one more thing. If we run the built-in id() method, it will tell us the memory address of the object passed to it:

which yields the following

As it turns out, since we haven't told python how to make a hash code for a wizard, it ends up using the memory address // 16.

However, even so, there are some collisions here: the only unique hash codes are 8785000196838 and 8785000196229. So why are we still seeing 5 unique objects in the set? Well, python doesn't actually know that they're equal; if we don't tell python how to compare objects, it will default to comparing them by their memory address. Since each of the 5 objects has a different memory address, they are considered unique.

Your Task

Write code in wizard.py to override the default behavior of object equality and hashing for the Wizard class:

1. Implement the __hash__ method, which takes no parameters (other than self), and which returns the month*31 + day
2. Implement the __eq__ method, which takes one parameter (in addition to self) which is object to which to compare it. Return True if the name, month, day, and year are equal between this object and the other object, and False otherwise.

If this works properly, the hash codes for all of the Snape wizards above should be 83, and when you run

It should print True. Finally, you should only see one Snape wizard in the set if you add them in the loop.

---

Part 2: HashSet (24 Points)

Now that we've convinced ourselves that the built-in python set class works properly, let's implement our own verison of a set from scratch using a hash table.

Your Task

Create a singly-linked list class and/or linked node class that wraps around a key object, which is what will be stored in the set. Create a class HashSet that aggregates and array of linked lists, and which has the following instance methods (that all have self as a first parameter)

• (4 Points) __init__: The construtor should take one parameter specifying the number of buckets to use, and you should initialize an array of empty linked lists with that number of buckets

• (4 Points) __contains__: A method that takes one parameter, the key, and which returns True if the key is in the linked list and False otherwise. When you've finished implementing this method, then saying

  Should print out True. Note the "syntactic sugar" with the in keyword, which you can use to make your code look nicer. Under the hood, saying x in y in python is equivalent to calling y.__contains__(x)

• (4 Points) add: Takes one parameter and adds that object to the set. You should compute the hash code of the object, find its appropriate bucket index, and add it if it doesn't already exist (we don't want duplicate objects).

• (4 Points) remove(obj): Remove obj from the hash table if it exists in the table, or throw a KeyError if the object isn't in the table. You can do this with the following code:

• (4 Points) __len__: A method with no parameters (other than self) which returns how many elements are in the set. This should run in constant time; you should not have to loop through all of the linked lists to count. Instead, store a member variable that keeps track of the number of objects as they are added and deleted so you can simply return that member variable.

  Note also the syntactic sugar; if we say len(s), this is equivalent to saying s.__len__()

• (4 Points) keys: A method with no parameters that returns all of the elements in the set as a python list.

If you're not sure where to get started, have a look at the needle in a haystack notes, as well as some starter code for linked lists that we made in class.

Tips

The first thing you should do in the __contains__, add, and remove methods is to compute the hash code for the object that's being passed in and % it by the number of buckets to figure out which bucket you should start looking in. We will assume here that the objects passed along have implemented __hash__, so that calling hash(obj) will give the hash code. Python already has built-in hash codes for ints, strings, floats, etc.

If this is all working properly, then the following code:

should print something like this (note that the order is arbitrary):

---

Part 3: HashMap (17 Points)

Sometimes, we may not know everything about a wizard, but we do know partial information like their name. In this case, it's more appropriate to use a map ADT instead of a set ADT to look up more info from the partial info we have. In this ADT, the key is something hashable that we look up in the hash table, but it is glued to something called a value which is the associated thing we're trying to look up. Python calls its implementation of a map a dictionary (in Java it's a Map, in C++ STL it's a map, in PHP it's an called an "associative array", ...). Here's how we might set up some information in a dictionary:

after which we'll see the following output

Note that a python dictionary has a quite convenient syntax; it looks just like an array, but we index it with keys instead of 0-indexed integers. We will use built-in python methods to replicate this syntactic sugar in our implementation of HashMap

Your task

Create a class HashMap which, like the HashSet class, aggregates an array of linked lists. You'll just need to tweak the node class in your linked list to hold a value in addition to a key. For those who had CS 174 with me, it's similar to the last assignment I gave in that class. Below are the instance methods you'll need to implement:

• (2 Points) __init__: The construtor should take one parameter specifying the number of buckets to use, and you should initialize an array of empty linked lists with that number of buckets

• (2 Points) __contains__: A method that takes one parameter, the key, and which returns True if the key is in the linked list and False otherwise. This should be incredibly similar to the __contains__ method in HashSet that you did before.

• (3 Points) __setitem__: A method that takes two parameters, the key and the value that should be associated to that key.

  • If the key doesn't exist in the map, add the key/value pair.
  • If the key already exists in the map, update its value to be the value that's being passed here
  This should be fairly similar to the add method in HashSet that you did before.

• (3 Points) __getitem__: A method that takes one parameter, the key, and which returns the value associated to the key, or which raises a KeyError if that key doesn't exist in the map. This should be fairly similar in structure to the __contains__ method

• (3 Points) __delitem__: A method that takes one parameter, the key, and which deletes the key/value pair associated to this key, or which raises a KeyError if that key doesn't exist in the map. This should be fairly similar in structure to the remove method in your HashSet class

• (2 Points) __len__: A method with no parameters (other than self) which returns how many elements are in the set. As in the HashSet, this should run in constant time

• (2 Points) keys: A method with no parameters that returns all of the keys in the map as a python list.

Tips

If you replace the example above with m = HashMap(10) instead of m = {}, you should get exactly the same behavior. Just make sure your keys are getting evenly distributed throughout the buckets

---

Part 4: Rebalancing (10 Points)

In order for __contains__, __getitem__, __setitem__, and __delitem__ to work in nearly constant time on average, we need to make sure the number of buckets is on the same order as the number of elements stored in the map. For example, if we're storing 100 key/value pairs, we should have around 100 buckets, and if we're storing a million key/value pairs, we should have around a million buckets.

This may seem wasteful since many buckets will be empty, but at worst, we're still have within a constant factor of the the storage of an array with N elements; we now have N pointers to buckets, plus the N elements and the overhead of the linked nodes. What we gain on average is that each bucket only has 1 element in it. Furthermore, if the hash codes are sufficiently staistically random, then most buckets will not have much more than 1 element in them.

In what follows, you will implement a scheme to ensure that the buckets stay balanced in this way, while not incuring much additional computation on average.

Your Task

Modify the constructor to take two parameters: the initial number of buckets and a "load factor." Then, modify the __setitem__ method so that if the number of elements in the map goes beyond load_factor * # buckets, then you should double the number of buckets and re-add every key/value pair that was in there before to the new buckets. This is exactly like how a C++ vector, Java ArrayList, and python list [] work to keep list accesses and adding to the end of the list constant amortized time.

Tips

To keep your code organized, you should make an internal helper instance method to do the rebalancing, which you call from within __setitem__ at the appropriate time.

Make sure the rebalancing doesn't break your code. If everything is working properly and you start off with an initial capacity of 10 and a load factor of 0.75, then you should see 160 buckets after running the following code.

---

Part 5: Russian Troll Tweet Wrangling (15 Points)

Now that you have an industrial strength hash map implementation, it's time to stress test it with an application that's super relevant to the 2024 election cycle. I have provided a file tweets.json with all of the "Left Troll" and "Right Troll" tweets Russian Troll Tweet Dataset archived by FiveThirtyEight (you can read more about it here). This is 476,215 tweets total. To load it, use this code:

Each tweet is a dictionary. For instance, the first tweet, tweets[0], looks like this:

Your Task

At the bottom of your hash.py file, use the HashMap class you made to print out the top 200 trigrams that the left trolls and the right trolls use. A trigram is a tuple of 3 contiguous words in a sentence. For instance, the sentence "CS 271 is my favorite class" has the trigrams

• ("CS", "271", "is")
• ("271", "is", "my")
• ("is", "my", "favorite")
• ("my", "favorite", "class")

Finding all trigrams across all tweets will be a stress test for your implementation, as there are over 2 million unique right trigrams and over 600k unique left trigrams. To get the best results, we'll need to do a basic version "text normalization" to deal with punctuation and capitalization

In this example, this gives us

Hints

The following algorithm will do this task efficiently:

1. Create a HashMap object where the key is a tuple of 3 strings for the trigram, and the associated value is the number of times that trigram appears across all tweets

2. Once this is filled in, grab all of the keys into a list, and create a parallel list of the associated counts

3. Use np.argsort to find the indices of the words with the highest counts (we will talk more about sorting algorithms in the third unit of the course, but we'll take this as a given for now). For instance,

   Will yield [2, 0, 1]

NOTE: If you haven't done rebalancing correctly, this code will take an extremely long time. If you've done it correctly, the left trolls should take under 20 seconds, and the right trolls should take under a minute. If your code is taking a really long time, swap in a dictionary {} for your HashMap object just to test your logic on this part. Then, once it works with the regular dictionary, go and debug your rebalancing.

Results

Content Warning: The results contain highly emotionally charged phrases dealing with issues of race, gender, immigration status, and political violence.

If you've done this correctly, here are the first 200 you should see for type LeftTroll (NOTE: trigrams that have the same number of counts are in an arbitrary order)

Show LeftTroll results Hide LeftTroll Results

And here are the top 200 you should see for type RightTroll

Show RightTroll results Hide RightTroll Results

P.S.

Hopefully now it makes sense why they're called "hash tags"!

Also, if you're curious, click here to see more advanced preprocessing you can do to normalize the text.