(C++)

Hash Table

The purpose of this assignment is to reinforce your knowledge of Hash Table data structures. Consider the following Hashtable class definition for a Hash Table class.

template struct Node { Node() : m_act(false), m_del(false) {} Node(const T& v) : m_val(v), m_act(true), m_del(false) {} void insert(const T& val) { m_val = val; m_act = true; m_del = false; } void remove() { m_act = false; m_del = true; } // only remove marking. void vacate() { m_act = false; m_del = false; } // completely removing. bool is_active() const { return m_act && !m_del; } // entry is active. bool is_occupied() const { return !m_act && m_del; } // entry for probe est. bool is_vacated() const { return !m_act && !m_del; } // entry is inactive. bool operator==(const Node& rhs) const { return m_val == rhs.m_val; } bool operator!=(const Node& rhs) const { return m_val != rhs.m_val; } bool operator<(const Node& rhs) const { return m_val < rhs.m_val; } bool operator>(const Node& rhs) const { return m_val > rhs.m_val; } T m_val; bool m_act; // flag indicating node is active in probe chain. bool m_del; // flag indicating node is deleted. }; template class HashTable { public: enum ProbeType { Linear, Double }; class const_iterator { public: const_iterator(const Node* table =0, const int table_size =0); const_iterator operator++() { assert(!m_seq.empty()); m_seq.pop(); m_current = m_seq.front(); if (m_seq.empty()) m_current = 0; // set the end of traversal. return *this; } const T& operator*() const { return m_current->m_val; } const T* operator->() const { return &(m_current->m_val); } bool operator==(const const_iterator& rhs) const { return m_current == rhs.m_current && m_seq == rhs.m_seq; } bool operator!=(const const_iterator& rhs) const { return m_current != rhs.m_current || m_seq != rhs.m_seq; } private: queue*> m_seq; // used for step-by-step iteration of sorted T's. Node* m_current; // current for m_seq queue. }; HashTable(const ProbeType type = Linear, const int size = 811) : m_type(type), m_size(size), m_number(0), m_oprtns(0), m_probes(0) { m_tab = new Node[size]; assert(m_tab); } HashTable(const HashTable&); HashTable& operator=(const HashTable&); ~HashTable() { assert(m_tab); delete [] m_tab; }; void insert(const T&); // insert value based on defined probing. void remove(const T&); // remove value based on defined probing. bool is_member(const T&); // search for a value based on defined probing ProbeType type() const { return m_type; } int size() const { return m_size; } int count() const { return m_number; } int probes() const { return m_probes; } int operations() const { return m_oprtns; } void reset() { m_oprtns = m_probes = 0; } // Resets variables used for statistics const_iterator begin() const { return const_iterator(m_tab, m_size); } const_iterator end() const { return const_iterator(0, 0); } friend ostream& operator<<(ostream& o, const HashTable& b); private: ProbeType m_type; int m_size; // the maximum size reserved for hash buckets. Node* m_tab; // dynamic hash table. int m_number; // count of elements in the table. int m_oprtns; // count of total insert/delete/search functions. int m_probes; // count of total probing operations. }; 

Implement the given Hashtable class definition. This Hash Table supports Linear Probing and Double Hashing via an enum selector and keeps track of several counts used for generating statistics. Example Instantiation: HashTable ltab(HashTable::Linear); HashTable dtab(HashTable::Double); TODO: - Use a student class(You should have a SSID, 1 Final Exam Grade, comparators (<,>, =), output override, and anything else you might need) - Implement a "Key()" function for your student class that returns a hash value. Use the C++ hashing function to create a string hash and an int hash for the SSID and Final Exam Score; return the absolute value of the sum of both hashes. - Linear probing will use the hash generated from the key function to calculate an index for it's underlying dynamic array. - Double Hashing will also do the same probing as Linear probing except that it will calculate an additional offset multiplier during insertion. deletion, and search: for (int i = 0; i < m_size; ++i) { int new_pos = (pos + i * off) % m_size; //Offset will always equal to 1 for Linear Probing //PROBING LOGIC } To test your implementation, produce the following main program using your implementation of Hashtable:

Generate 300 student records randomly and insert them into a Bag b1. Iterate on b1 to subsequently insert the obtained values to Hashtable t1. Remove 100 student records randomly from b1 and the same elements from t1. Verify if remaining contents of b1 and t1 are identical (by matching both).

Design a helper function that performs an experiment to compare the Linear Probing and Double Hashing modes of your hash table implementation using the counts that you need to keep track of to calculate and output the following:

Maximum Size of the Linear Hash Table

Total Element Count of the Linear Hash Table only (It's the same for Double Hashing so don't output it twice)

Total Weight (element count/size) of the Linear Probe Hash Table

Average search time for open addressing (linear probing): 0.5 + 0.5 / (1 - Total Weight) Table

The average number of probes per operation of the Linear Probe Hash Table

Average search time for open addressing (double hashing): -log(1 - Total Weight) / Total Weight - For Double Hashing Hash Table

The average number of probes per operation of the Double Hashing Hash Table

You will perform the experiment on varying weights of the tables. Use the following code to call your Experiment function in your main function: for (int i = 5; i < 10; ++i) { HashTable ltab(HashTable::Linear); HashTable dtab(HashTable::Double); experiment(ltab, (int)(811 * (i/10.))); // You must pass the hash table and the number of students to generate for insertion experiment(dtab, (int)(811 * (i/10.))); // DEFAULT SIZE OF HASH TABLE IS 811 cout << endl; }