ADT Hash Table class template Design a class template for the ADT Hash Table. Th

Question

ADT Hash Table class template

Design a class template for the ADT Hash Table. The basic operations should include(at least) constructors, a deconstructor, a copy constructor, inserting an item into hash table, searching for item in hash table, and deleting an item from hash table. Use random hashing for the hash function and chaining to resolve collisions.

You should also write a driver program to test your template.

Explanation / Answer

template class CHashTableIterator { friend class CHashTable ; public: typedef K KeyType; typedef C BucketType; typedef H HashType; typedef typename C::ValueType ValueType; typedef CHashTableIterator Iterator; CHashTableIterator (); CHashTableIterator (const CHashTableIterator& i); bool Valid () const; CHashTableIterator & operator = (const CHashTableIterator & i); CHashTableIterator & operator ++ (); CHashTableIterator operator ++ (int); Entry & operator * (); const Entry & operator * () const; bool operator == (const CHashTableIterator& i2) const; bool operator != (const CHashTableIterator& i2) const; protected: const CHashTable * tablePtr_; size_t bucketNum_; typename C::Iterator bucketItr_; } ; template CHashTableIterator::CHashTableIterator () : tablePtr_(0), bucketNum__(0), bucketItr__() {} template CHashTableIterator ::CHashTableIterator (const CHashTableIterator& I) : tablePtr_(I.tablePtr_), bucketNum_(I.bucketNum_), bucketItr_(I.bucketItr_) {} template bool CHashTableIterator::Valid () const { if (tablePtr_ == 0) return 0; if (bucketNum_ >= tablePtr_->numBuckets_) return 0; return bucketItr_.Valid(); } template CHashTableIterator & CHashTableIterator::operator = (const CHashTableIterator & I) { // TBS } template CHashTableIterator & CHashTableIterator::operator ++ () { // increment the bucket itr // if bucket itr is not at the end of the bucket, return itr // if bucket itr is at end of bucket, // start at beginning of next non-empty bucket and return itr // if a non-empty bucket is not found, return the end itr } template CHashTableIterator CHashTableIterator::operator ++ (int) { // TBS } template Entry& CHashTableIterator::operator * () const { // if itr is valid, return the pair to which it points } template bool CHashTableIterator ::operator == (const CHashTableIterator& I2) const { if (!Valid() && !I2.Valid()) return 1; if (Valid() && !I2.Valid()) return 0; if (!Valid() && I2.Valid()) return 0; // now both are valid if (tablePtr_ != I2.tablePtr_) return 0; if (bucketNum_ != I2.bucketNum_) return 0; if (bucketItr_ != I2.bucketItr_) return 0; return 1; } template bool CHashTableIterator ::operator != (const CHashTableIterator& I2) const { // TBS }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.