This lab focuses on two separate topics, the first being hashing and the second being sorting. Up until now, you have been doing exhaustive searching, where you have had to go to every item in your data structure in order to find something you were looking for. Well there is a better way to do random access. You can instead use a data structure called a hash table, that stores objects in an array, but places them in the array based on the output of a function. You will also be implementing two very important sorting functions this week. Bubble sort, insertion sort, and selection sort are not the most efficient sorting algorithm around, with all of those having a running time of n^2. We want something that goes quite a bit faster. Some very smart people decades ago found some great algorithms. You will be implementing two of them; quicksort and merge sort. Both of these will be using your `doubly_linked_list` from lab 6, so make sure that that is fully working. ### Lab Instructions ### Implement the hash table using the three most common probing techniques: linear, quadratic, double. Use the two provided hashing functions `hash_1` and `hash_2`. When the hash table gets more than 70% full, you will need to double the size of the hash table to help reduce the number of collisions that could occur. There are three common techniques of probing a hash table. * *linear*: When a collision is found at `table[n%max_size]`, go to the array location `table[(n+attempt)%max_size]`, where `n` is the output of the `hash_1` function and attempt is the number of collisions encountered so far. Continue moving along the array cell by cell until the desired location is found. * *quadratic*: When a collision is found at `table[n%max_size]`, go to the array location `table[(n + attempt^2)%max_size]`. * *double*: When a collision is found at `table[n%max_size]`, go to the array location `table[(n+attempt*m)%max_size]`, where `m` is the output of the `hash_2` function. Implement both merge sort and quicksort. Verify they sort. We will only provide basic tests. *You* must implement the sorts using their algorithms. There are thousands of videos on YouTube that cover these topics in much more depth than we will have the opportunity during class. Use them for more help understanding the assignment. If you find one that helped you, post it in the Lab 8 channel on slack to help your fellow classmates out. ### Hash Table Information ### * Wikipedia article on [Hash Function](https://en.wikipedia.org/wiki/Hash_function) * Wikipedia article on [Hash Table](https://en.wikipedia.org/wiki/Hash_table) * Youtube video on [Hash Table](https://www.youtube.com/watch?v=shs0KM3wKv8) ##### Function Explanation ##### * `hash_1(std::string)`: DJB2 String hashing algorithm * `hash_2(std::string)`: BKDR String hashing algorithm * `expand()`: Increases the size of the hash table when the hash table gets more than 70% full. New max size comes from PRIMES array. * `hash_table(char)`: Constructor that takes in the type of probing to be used. * `~hash_table()`: Deconstructor. * `insert(std::string, int)`: Take in a key and it's value and insert them into the hash_table. Handle collisions in the way defined by the constructor that created the hash table. If the key already exists in the hash table, return false and do not insert or update the item. * `get(std::string)`: Get the value associated with that key. * `remove(std::string)`: Remove the key and value from the hash table * `in_table(std::string)`: Checks to see if that key is in the hash table * `update(std::string, int)`: Change the value associated with a key. If the value is not in the hash table, insert it. * `to_string()`: Convert the hash table to a string for testing. Yay! No operator overloading!

#ifndef CMPE126S18_LABS_HASH_TABLE_H #define CMPE126S18_LABS_HASH_TABLE_H #include  #include  namespace lab8{ struct key_value{ std::string key; int value; }; class hash_table{ key_value hash_table_array[]; char probing; unsigned max_size; unsigned current_size; const int PRIMES[] = {31, 67, 137, 277, 557, 1117, 2237, 4481, 8963, 17929, 35863, 71741, 143483, 286999, 574003, 1148029}; // PRIME[n+1]= next prime after 2*PRIME[n]. Use this for setting max size unsigned hash_1(std::string to_hash); unsigned hash_2(std::string to_hash); void expand(); public: hash_table(char type); ~hash_table(); bool insert(std::string key, int value); int get(std::string key); void remove(std::string key); bool in_table(std::string); void update(std::string key, int value); // Functions use for testings unsigned get_size(){ return current_size; }; unsigned get_max_size(){ return max_size; }; std::string to_string(); //Used for testing }; } 

#include "../inc/hash_table.h" namespace lab8{ unsigned hash_table::hash_1(std::string to_hash) { // DJB2 Hashing Algorithm unsigned int hash = 5381; for(char c: to_hash){ hash = ((hash << 5) + hash) + c; } return hash; } unsigned hash_table::hash_2(std::string to_hash) { // BKDR Hashing Algorithm unsigned int seed = 131; unsigned int hash = 0; for(char c: to_hash){ hash = (hash * seed) + c; } return hash; } void hash_table::expand() { // Expand the hash table by a factor of 2 every time this function is called } hash_table::hash_table(char type) { /* * Define the probing technique * 'l': Linear probing * hash_1() + attempt * 'q': Quadratic probing * hash_1() + attempt^2 * 'd': Double Probing * hash_1() + attempt * hash_2() * * Create a hash table with an initial size of 100 */ } hash_table::~hash_table() { } bool hash_table::insert(std::string key, int value) { // Insert a key according to the defined probing technique return true; } bool hash_table::in_table(std::string key){ // Checks to see if that key is in the table. // Use the specified probing technique // Keep collisions in mind return true; } int hash_table::get(std::string key) { // Get the int value from the node that has key // Use the specified probing technique return 0; } void hash_table::update(std::string key, int value){ // Update a key in the hash table. // Keep collisions in mind // Use the specified probing technique } void hash_table::remove(std::string key){ // Remove an item from the hash table. Keep collisions in mind // Use the specified probing technique } std::string hash_table::to_string(){ // Run through the entire array and create a string following this format. The {} brackets aren't part of the return // [{array location}]{key_value.key}:{key_value.int} return std::string(); } } 

 #endif //CMPE126S18_LABS_HASH_TABLE_H