CSCI152 Assignment 6-Solved

In this task, you have to complete an implementation of set over std::string using a hash table. If everything goes well, you will see that the asymptotic performance of set, implemented with a hash table has has a somewhat better performance than the implementation of set implemented with BST.

Download files set.h, set.cpp, main.cpp and Makefile. Set, using hash map, is implemented as follows:

class set
size_t set_size; double max_load_factor;

std::vector< std::list< std::string >> buckets;

Field set_sizecontains the number of string in the hash table. max_load_factor defines the maximal value that the load factor set_size / buckets. size( ) can have. The load factor is the average size of the list in the vector. If the load factor becomes bigger than the allowed maximum, the set must be rehashed

 strings are compared without distinguishing between upper and lower case. You have already implemented a function bool equal( const std::string& , const std::string& ) that is case insensitive. The hash function must agree with equal. Strings for which equal returns true must have the same hash value.

1.   Complete the function hash( const std::string& s ) that computes a hash value for s. This function must agree with equal, which means that it must not distinguish between upper and lower case characters.

So, hash( "NurSultan" ) == hash( "nursultan" ) must return true.

2.   Complete the method bool simp_insert( const std::string& s ) in file set.cpp. As usual, simp_insert returns true, when insertion takes place. It is called ’simp’, because it does not rehash. Do not forget to update set_size when s is inserted.

3.    Implement the method std::ostream& print( std::ostream& out ) const. When you are finished, you can remove #if 0 and #endif around std::ostream& operator << ( std::ostream& out, const set& s ).

4.    Implement bool remove( const std::string& s ) in file set.cpp.

The function must return true if s was found and removed. Do not forget to update set_size when s is removed.

5.    Complete the method void clear( ) in file set.cpp.

6.    Complete the method void rehash( size_t newbucketsize ). It should start with

if( newbucketsize < 4 )

newbucketsize = 4;

std::vector< std::list< std::string >> newbuckets =

std::vector< std::list< std::string >> ( newbucketsize );

7.    Complete method bool set::insert( const std::string& s ). First call simp_insert( const std::string& s ), and after that, decide if a rehash is necessary. As with ensure_capacity, make sure that the bucket size is at least doubled in size.

8 you can now do some measurements. Thecode for doing this is present in main.cpp. The performance should be O(n), and it should be better than the performance of the BST-based implementation of set.

Make two measurements: One for set someset1(default max_load_factor of 3.0), and one using set someset1( 4, 25.0 ) (max_load_factor is

25.0).