The Great Stanford Hash-Off

Due Friday, March 5 at 11:30 am Pacific

• Submissions received by due date receive a small on-time bonus.
• All students are granted a pre-approved extension or "grace period" of 48 hours after the due date. Late submissions are accepted during the grace period with no penalty.
• The grace period expires Sun, Mar 7 at 11:30 am Pacific, after which we cannot accept further late submissions.
• In this course, we express all date/times in Pacific time GMT -8. Our Paperless submission system also displays/records due dates and submission times in Pacific time.

Hash tables are one of the most ubiquitous data structures in software engineering, and a lot of effort has been placed into getting them to work quickly and efficiently. In lecture, we coded up chained hashing. We also talked about two other hashing approaches:

• Linear Probing: A hashing strategy where items can “leak out” of the slots they’re supposed to stay in. This strategy is surprisingly fast in practice!
• Robin Hood Hashing: This slight modification on linear probing “smooths out” the cost of lookups in a linear probing table, which leads to some interesting consequences.

Your task in this assignment is to code up these two hashing strategies and evaluate their performance against chained hashing. How do they hold up in practice? Which hash table implementations tend to work well in which scenarios?

Due Friday, March 5th at 11:30AM. You are welcome to work in pairs on this assignment.

As usual, we recommend making slow and steady progress on this assignment throughout the week rather than trying to do everything here in one sitting. Here’s our recommended timetable for this assignment:

• Aim to complete the enumeration warmup the day this assignment goes out.
• Aim to complete the Linear Probing Warmup the day this assignment goes out.
• Aim to complete the Linear Probing Coding component within three days.
• Aim to complete the Robin Hood Warmup within three days.
• Aim to complete the Robin Hood Coding component within six days.
• Aim to complete the Performance Analysis component within seven days.

Problem One: Enumerations Warmup

At a few points in this assignment, you’ll be asked to work with enumerated types, a form of custom C++ type representing one out of several different options. We haven’t used enumerated types before this assignment, so in this section we figured we’d give you the rundown. 😃

To kick things off, consider the following C++ code:

enum class StudentType {
    FRESHMAN,           
    SOPHOMORE,          
    JUNIOR,             
    SENIOR,             
    SUPER_SENIOR,       
    COTERM,             
    MS_STUDENT,         
    PHD_STUDENT,        
    SCPD_STUDENT        
};                      

This defines a new type called StudentType. Each variable of type StudentType can take on one of the values listed above. For example, we can write code like this:

StudentType mia   = StudentType::FRESHMAN;   
StudentType chase = StudentType::COTERM;     
StudentType erika = StudentType::PHD_STUDENT;

You can compare two StudentTypes against one another using the == operator, reassign them using =, etc.

Enumerated types are useful for remembering which of many mutually exclusive options a particular object happens to be in. You’ll make use of them in your linear probing hash table to remember whether a slot is empty, full, or a tombstone.

There are no deliverables for this part of the assignment; just make sure you’ve read the above code and understand it. 😃

Problem Two: Linear Probing Warmup

The linear probing hash strategy that we talked about in Wednesday’s class is very different from the style of hash table (chained hashing) that we saw on Monday. Here’s a few of the differences:

• Each slot in a chained hash table is a bucket that can store any number of elements. Each slot in a linear probing table is either empty or holds a single element.
• Every element in a chained hash table ends up in the slot corresponding to its hash code. Elements in a linear probing table can leak out of their initial slots and end up elsewhere in the table.
• Deletions in a linear probing table use tombstones; deletions in chained hashing don’t require tombstones. Before moving on, we’d like you to answer a few short answer questions to make sure that you’re comfortable with linear probing as a collision resolution strategy.

Before moving on, we’d like you to answer a few short answer questions to make sure that you’re comfortable with linear probing as a collision resolution strategy.

Problem Three: Implementing Linear Probing

Your task in this part of the assignment is to implement the LinearProbingHashTable type. Here’s the interface for that type, as given in the header file:

class LinearProbingHashTable {
public:
    LinearProbingHashTable(HashFunction<std::string> hashFn);
    ~LinearProbingHashTable();

    bool contains(const std::string& key) const;

    bool insert(const std::string& key);
    bool remove(const std::string& key);

    bool isEmpty() const;
    int  size() const;

    void printDebugInfo();

private:
    enum class SlotType {
        TOMBSTONE, EMPTY, FILLED
    };

    struct Slot {
        std::string value;
        SlotType type;
    };

    Slot* elems;

    /* The rest is up to you to decide; see below */
};

The LinearProbingHashTable type is analogous to Set<string> in that it stores a collection of strings with no duplicate elements allowed. However, it differs in a few key ways:

1. The LinearProbingHashTable type has its hash function provided to it when it’s created. In practice, a hash table should choose a hash function internally. This is both to make it easier to test things (we can construct tests where we know exactly where each element is going to land).
2. The Set<string> type has no upper bound to how big it can get. For reasons that we’ll discuss later, the LinearProbingHashTable type you’ll be implementing is built to have a fixed number of slots, which is specified in the constructor. (Specifically, you’re given a particular HashFunction<string>, and that HashFunction<string> is built to work with a specific number of slots.) This means that there’s a maximum number of elements that can be stored in the table, since a linear probing table can’t store more than one element per slot.

In terms of the internal representation of the LinearProbingHashTable: as with the HeapPQueue, you also need to do all your own memory management, though we suspect this will be easier than the HeapPQueue because the size of your hash table never changes. You should represent the hash table as an array of objects of the type Slot, where Slot is the struct type defined in LinearProbingHashTable. Each slot consists of a string, along with a variable of the enumerated type SlotType indicating whether the slot is empty, full, or a tombstone. If the slot is empty or a tombstone, you should completely ignore the string value, since we’re pretending the slot is empty in that case. If the slot is not empty, the string value tells you what’s stored in that particular slot.

We’ve provided you with a fairly extensive set of automated tests you can use to validate that your implementation works correctly. To assist you with testing, we’ve also provided an “Interactive Linear Probing” environment akin to Assignment 6’s “Interactive PQueue” button that lets you issue individual commands to a linear probing table to see what happens.

Some notes on this problem:

• Do not implement contains, remove, or insert recursively. Some of the stress tests we’ll be subjecting your code to in the time tests will involve working with extremely full tables, and you can easily get a stack overflow this way because the call stack won’t be big enough to hold space for all the stack frames.
• Make sure you store the hash function that we provide you in the constructor and use that hash function throughout the table. Variables of type HashFunction<string> are like other types of variables; you can assign them by writing code to the effect of hashFn1 = hashFn2;.
• If you have a variable of type HashFunction<string> named hasnFn and an element to hash named elem, you can compute the hash code of elem by writing hasnFn(elem).
• Remember that, like the Set<string> type, your LinearProbingHashTable should not allow for duplicate elements. If the user wants to insert a string that’s already present, you should not insert a second copy.
• A common mistake in implementing this hash table is to try to set the element field of a Slot to nullptr when removing a string from the hash table, with the idea of saying “this string doesn’t exist any more.” That, unfortunately, doesn’t work. Remember that in C++, a string represents an honest-to-goodness string object, so you can’t have a “null string” the same way you can’t have a “null integer.” Unfortunately, it is legal C++ code to assign nullptr to a string, which C++ interprets as “please crash my program as soon as I get here” rather than “make a null string.” Instead, just change the type field to indicate that although there is technically a string in the slot, that string isn’t meaningful.
• Make sure not to read the contents of a string in a Slot if that Slot is empty. If the slot is empty, it means that the string value there isn’t meaningful. There are a lot of bugs that can arise if you accidentally read the string in a Slot when the slot is empty.
• Your table should be able to store any strings that the user wants to store, including the empty string.
• The contains, insert, and remove functions need to function correctly even if the table is full. Specifically, insert should return false because there is no more space, and remove and contains should operate as usual. You may need to special-case the logic here – do you see why?
• You are encouraged to add private helper functions, especially if you find yourself writing the same code over and over again. Just don’t change the signatures of any of the existing functions. If you do define any helper functions, think about whether they should be marked const. Specifically, helper functions that don’t change the hash table should be marked const, while helper functions that do make changes to the table should not be const.
• You are likely to run into some interesting bugs in the course of coding this one up, and when you do, don’t forget how powerful a tool the debugger is! Feel free to set breakpoints in the different test cases so that you can see exactly what your code is doing when it works and when it doesn’t work. Inspect the contents of your array of slots and make sure that it’s consistent with what you expect to see. Once you’ve identified the bug – and no sooner – edit your code to fix the underlying problem.
• You must not use any of the container types (e.g. Vector, Set, etc.) when solving this problem. Part of the purpose of this assignment is to let you see how you’d build all the containers up from scratch.

private:                    
    Slot* hsAreCute();

LinearProbingHashTable::Slot* LinearProbingHashTable::hsAreCute() {
    // Wow, this pun lost a lot in translation.                    
}                                          

LinearProbingHashTable::Slot* LinearProbingHashTable::hsAreCute() {
    Slot* h = new Slot[137]; // Totally fine!                      
    return h;                                                      
}                                                                  

private:                            
    void iLostMoneyToA(Slot* machine);

void LinearProbingHashTable::iLostMoneyToA(Slot* machine) {
    // Don't make the same mistake as me!                  
}                                                          

Problem Three: Robin Hood Warmup

Robin Hood hashing is a clever variation on linear probing that reduces the variance in the costs of insertions, deletions, and lookups. As a reminder, Robin Hood hashing is based on linear probing, but differs in the following ways:

1. Each element in a Robin Hood hash table is annotated with the distance it is from its home slot. This distance is measured by the number of steps backwards you have to take, starting at that element, to get the index of its home slot. (As in linear probing, we wrap around the ends of the table if we reach that point.)
2. Lookups in a Robin Hood hash table can stop early. Specifically, if the element we’re looking for is further from home than the currently-scanned table element, we know that the element we’re looking for isn’t in the table and can stop our search. (Do you see why the element can’t be there?)
3. When inserting an element into a Robin Hood hash table, if the element being inserted is further from home than the element in the table slot being scanner, we displace the element in the table at that index, place the element we wanted to insert there, then continue onward as if we were inserting the displaced element all along. (We do not do anything if the distances are tied.)
4. There are no tombstones in a Robin Hood hash table. Instead, when deleting an element, we use backwards-shift deletion: we shift elements back one spot in the table until we either (1) find an empty slot or (2) find an element in its natural home spot.

Before coding up a Robin Hood hash table, few minutes to work through some quick short answer questions.

Problem Four: Robin Hood Hashing

Your next task is to implement the RobinHoodHashTable type, which represents a hash table implemented using Robin Hood hashing, as described in lecture. Here’s what we’ve provided you:

class RobinHoodHashTable {
public:
    RobinHoodHashTable(HashFunction<std::string> hashFn);
    ~RobinHoodHashTable();

    bool contains(const std::string& key) const;

    bool insert(const std::string& key);
    bool remove(const std::string& key);

    bool isEmpty() const;
    int  size() const;

    void printDebugInfo();

private:
    static const int EMPTY_SLOT = /* something */;

    struct Slot {
        std::string value;
        int distance;
    };

    Slot* elems;

    /* The rest is up to you to decide; see below */
};

In many ways, what we’ve given you for RobinHoodHashTable is the same as that for the LinearProbingHashTable: the constructor takes in a HashFunction<string> that lets you know how many slots to use, you need to support insert, contains, and remove, the table never grows, etc.

There are, however, some notable differences. First, note that there’s no longer a SlotType enumerated type. That’s because there are only two options for each table slot – either the slot is empty, or the slot is filled and the item there is some distance from home. You should mark slots empty by setting their distance value to the constant EMPTY_SLOT. Any slot whose distance is not the value EMPTY_SLOT is assumed to be full and to be the indicated number of spots away from home.

Second, as the name suggests, this class should be implemented using Robin Hood hashing rather that linear probing. You may find parts of your LinearProbingHashTable useful as starting points for your design of the RobinHoodHashTable, but the differences between the two table types (tracking elements’ distances from their home, displacing elements on insertions, cutting off searches early, backward-shift deletion, the lack of tombstones, and the different Slot representation) will require you to rewrite each of the core functions (contains, insert, and remove) to some degree.

Here’s what you need to do:

Some notes on this problem:

• Do not implement contains, insert, or remove recursively; this may cause stack overflows when working with large tables.
• You might find the swap function, defined in <algorithm>, useful here. It takes in two arguments and swaps them with one another. For example:

  int x = 137, y = 42;               
  swap(x, y); // Now x = 42, y = 137.
  

• As with linear probing, make sure not to read the element field of a slot until you’ve checked that the slot isn’t empty. Otherwise, you’ll read a string that may or may not be in the table.
• When inserting an element, you should only displace an element if it is strictly closer to its home than the inserted element is to its home. For example, if the element you’re inserting is two steps from home and the currently-scanned element is two steps from home as well, you should not displace that element.
• When removing an item from the table, you’ll need some way to refer to “the slot after the current one, wrapping around.” It’s easy to remember the “slot after the current one” bit, and easy to forget the “wrapping around” part. 😃
• You must not use any of the container types (e.g. Vector, Set, etc.) when solving this problem. Part of the purpose of this assignment is to let you see how you’d build all the containers up from scratch.

Problem Five: Performance Analysis

We implemented chained hashing in class, and we’ve included a ChainedHashTable type in the Demos/ directory along the lines of the two hash tables you built here. You just implemented a linear probing table and a Robin Hood hash table. The question then is – how do they stack up against one another?

Choose the “Performance Analysis” button from the main menu. This option will run the following workflow on each of the three table types:

• Insert all words in the file EnglishWords.txt into an empty hash table, measuring the average cost of each successful insertion.
• Insert those words again in random order, measuring the cost of each unsuccessful insertion. (These insertions will fail because these hash tables don’t support duplicates.)
• Look up each word in EnglishWords.txt in that hash table, measuring the average cost of each successful lookup.
• Look up the capitalized version of each word in that hash table. Since all the words in EnglishWords.txt are stored in lower-case, this measures the average cost of each unsuccessful lookup.
• Remove the capitalized versions of each word in the hash table. This measures the average cost of unsuccessful deletions, since none of those words are present.
• Remove the lower-case versions of each word in the hash table. This measures the average cost of successful deletions.

The provided starter code will run this workflow across a variety of different load factors α (ratios of numbers of elements in the table to the number of slots in the table), reporting the times back to you. This may take a while to complete; it’s okay if it takes about five or ten minutes to finish running.

As a note, the timing numbers you get will be sensitive to what else is running on your computer. If you leave your program running time tests in the background while, say, watching a YouTube video, the overhead of your computer switching back and forth between different processes can skew the numbers you’ll get back. We recommend that once you click the “Performance Analysis” button, you walk away from your computer for a while, stretch a bit, and return once all the time trials have finished.

Once you have the data, review the numbers that you’re seeing. Look vertically to see how the times for a particular hash table compare across load factors, and horizontally to see how the different tables compare against one another.

(Optional) Problem Six: Extensions

You’ve just implemented two hash tables! If that isn’t enough for you, or if you want to take things a step further, you’re welcome to build on the base assignment and do whatever cool and exciting things seem most interesting to you!

If you’d like to implement a more complex hash table than the ones you did here, please edit the file MyOptionalHashTable.h and MyOptionalHashTable.cpp with your implementations, while leaving your LinearProbingHashTable and RobinHoodHashTable types unmodified. You can then integrate your type into the performance analyzer by editing the file Demos/TimeTestConfig.h. There are instructions there about how to edit that file.

Here are some suggestions of things to try out:

• The hash tables we’ve defined here are fixed-sized and don’t grow when they start to fill up. In practice, you’d pick some load factor and rehash the tables whenever that load factor was reached. Write code that lets you rehash the tables once they exceed some load factor of your choosing. Tinker around to see what the optimal load factor appears to be!
• Tombstone deletion has a major drawback: if you fill a linear probing table up, then delete most of its elements, the cost of doing a lookup will be way higher than if you had just built a brand new table and filled it in with just those elements. (Do you see why?) Some implementations of these hash tables will keep track of how many deleted elements there are, and when that exceeds some threshold, they’ll rebuild the table from scratch to clean out the tombstones. Experiment with this and see what you can come up with!
• There are many other hashing strategies you can use. Quadratic probing and double hashing, for example, are variations on linear probing that cap the number of elements that can be in a slot at one, but choose a different set of follow-up slots to then look at when finding the next place to look. Cuckoo hashing is based on a totally different idea: it uses two separate hash functions and places each element into one of two tables, always ensuring that the elements are either at the spot in the first table given by the first hash function or the spot in the second table given by the second hash function. Hopscotch hashing is like linear probing, but ensures that elements are never “too far” away from their home location. FKS hashing is like chained hashing, but uses a two-layer hashing scheme to ensure that each element can be found in at most two probes. Read up on one of these strategies – or another of your choosing – and code them up. How quickly do they run? You can add your own hash table type to the performance analysis by editing AllHashTables in the file Demos/PerformanceGUI.cpp.
• We provide the hash functions in this assignment, but there’s no reason to suspect that our hash functions are the “best” hash functions and you can change which hash function to use. Research other hash functions, code them up, and update the performance test (it’s the timeTest function in the files Demos/PerformanceGUI.cpp) to use your new hash function. How does your new hash function compare with ours?

Submission Instructions

Once you’ve autoindented your code so that it looks beautiful and worked through the Assignment Submission Checklist, submit the following files on Paperless, plus any other files you modified when writing up extensions:

• ShortAnswers.txt. (Don’t forget this one, even though there’s no code in it!)
• LinearProbingHashTable.h/.cpp. (Remember to submit both of these files!)
• RobinHoodHashTable.h/.cpp. (Remember to submit both of these files!)

And that’s it! You’re done! You’ve just explored how to engineer a hash table and are now an expert at dynamic arrays.

Good luck, and have fun!