CHAINED HASH

OVERVIEW:

Open address hashing has a few issues that the chained hash tables attempt to resolve.

For one, to prevent clustering, we will store all the keys with the same hash value at the same index of the table in a linked list, or better yet, in an AVL tree - this is known as the Ryan solution. But you will need to implement the generic linked list version before  you try the AVL version. 

We will build a chained_hash class whose private member variables are iterated lists (lists with a built-in iterators)

I have a detailed discussion of the list_iterated class here and a sample "nested class" here.

The chained_hash class:

Here is the declaration of the chained_hash class:



class ChainedHash
{
public:


    ChainedHash( );                              //CTOR

    bool insert(const T& entry);            //insert entry; false if overwriting.
    bool remove(int key);                   //remove this key

    bool find(int key, T& result) const;    //result <- record with key
    bool is_present(int key) const;         //is this key present in table?
    int size( ) const { return total_records; }  //number of keys in the table
    long capacity(){return TABLE_SIZE;}


    //print entire table with keys, etc.
    template<class TT>
    friend ostream& operator << (ostream& outs,
                                 const ChainedHash<TT>& h);

private:
    AVL<T> _data[TABLE_SIZE];               //table chains
    int total_records;                      //number of keys in the table

    int hash(int key) const;                //hash function
};


Please note: The ChainedHash object will never make reference to the _item field of the struct. You may only assume the structure used will have a _key field

struct HashRecord{
    int _key;
    string _item;
    HashRecord(int key=-1, string item=""):_key(key), _item(item){}
    friend ostream& operator <<(ostream& outs, const HashRecord& h){
        cout << "[" << h._key << ":" << h._item << "]";
        return outs;
    }
    friend bool operator < (const HashRecord& left, const HashRecord& right){
        return left._key < right._key;
    }
    friend bool operator > (const HashRecord& left, const HashRecord& right){
        return left._key > right._key;
    }
    friend bool operator == (const HashRecord& left, const HashRecord& right){
        return left._key == right._key;
    }
};

 

The user will also define a to_string() function for the Hash structure:

 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
//We will need a function like this for any class/struct that will specialize 
//      the AVL class. (for use in the AVL's 
//      pre_order(), in_order(), post_order() functions)
string to_string(const HashRecord& h){
    return string(to_string(h._key) + " : " + h._item);
}
//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -






So, you will declare a chained_hash object as follows:

ChainedHash<record> chained;

Test your class by inserting records, deleting records, searching for records and test the existence of records.

You may want to write a function to insert random records into your object and then delete them as well as an interactive function that will allow you to insert specific records to test for collisions.