I need help to complete this hashtable implementation in c++. Need to finish the
ID: 3688403 • Letter: I
Question
I need help to complete this hashtable implementation in c++. Need to finish the functions where says "TBS". Code below.
Thanks
/* hashtbl.h declaration and implementation of hastable and hashtableIterator NOTE: search for "TBS" to find missing code that is required */ #ifndef _HASHTBL_H #define _HASHTBL_H #include #include #include #include // used by Analysis in hashtbl.cpp #include #include #include #include #include // Swap() namespace fsu { template class HashTable; template class HashTableIterator; //-------------------------------------------- // HashTable //-------------------------------------------- template class HashTable { friend class HashTableIterator ; public: typedef K KeyType; typedef D DataType; typedef fsu::Entry EntryType; typedef fsu::List BucketType; typedef H HashType; typedef typename BucketType::ValueType ValueType; typedef HashTableIterator Iterator; typedef HashTableIterator ConstIterator; // ADT Table Iterator Insert (const K& k, const D& d); bool Remove (const K& k); bool Retrieve (const K& k, D& d) const; Iterator Includes (const K& k) const; // ADT Associative Array D& Get (const K& key); void Put (const K& key, const D& data); D& operator[] (const K& key); // const versions of Get & [] const D& Get (const K& key) const; const D& operator[] (const K& key) const; void Clear (); void Rehash (size_t numBuckets = 0); size_t Size () const; bool Empty () const; // Iterator Begin (); // Iterator End (); ConstIterator Begin () const; ConstIterator End () const; // first ctor uses default hash object, second uses supplied hash object explicit HashTable (size_t numBuckets = 100, bool prime = 1); HashTable (size_t numBuckets, HashType hashObject, bool prime = 1); ~HashTable (); HashTable (const HashTable&); HashTable& operator = (const HashTable&); // these are for debugging and analysis void Dump (std::ostream& os, int c1 = 0, int c2 = 0) const; size_t MaxBucketSize () const; void Analysis (std::ostream& os) const; private: // data size_t numBuckets_; Vector < BucketType > bucketVector_; HashType hashObject_; bool prime_; // flag for prime number of buckets // private method calculates bucket index size_t Index (const KeyType& k) const; } ; //-------------------------------------------- // HashTableIterator //-------------------------------------------- // Note: This is a ConstIterator - cannot be used to modify table template class HashTableIterator { friend class HashTable ; public: typedef K KeyType; typedef D DataType; typedef fsu::Entry EntryType; typedef fsu::List BucketType; typedef H HashType; typedef typename BucketType::ValueType ValueType; typedef HashTableIterator Iterator; typedef HashTableIterator ConstIterator; HashTableIterator (); HashTableIterator (const Iterator& i); bool Valid () const; HashTableIterator & operator = (const Iterator& i); HashTableIterator & operator ++ (); HashTableIterator operator ++ (int); // Entry & operator * (); const Entry & operator * () const; bool operator == (const Iterator& i2) const; bool operator != (const Iterator& i2) const; protected: const HashTable * tablePtr_; size_t bucketNum_; typename BucketType::ConstIterator bucketItr_; // typename BucketType::Iterator bucketItr_; } ; //-------------------------------------------- // HashTable //-------------------------------------------- // ADT Table template HashTableIterator HashTable::Insert (const K& k, const D& d) { EntryType e(k,d); Iterator i; // TBS return i; } template bool HashTable::Remove (const K& k) { // TBS return 0; } template bool HashTable::Retrieve (const K& k, D& d) const { // TBS if(Get(k) != null) return 0; } template HashTableIterator HashTable::Includes (const K& k) const { // TBS return End(); } // ADT Associative Array template D& HashTable::Get (const K& key) { EntryType e(key); size_t bn = Index(key); typename BucketType::Iterator i = bucketVector_[bn].Includes(e); if (i == bucketVector_[bn].End()) i = bucketVector_[bn].Insert(e); return (*i).data_; } template const D& HashTable::Get (const K& key) const { Iterator i = Includes(key); if (i == End()) { std::cerr << "** Error: const bracket operator called on non-existence key "; exit (EXIT_FAILURE); } return (*i).data_; } template void HashTable::Put (const K& key, const D& data) { // any of these works: Insert(key,data); // Get(key) = data; // (*this)[key] = data; } template D& HashTable::operator[] (const K& key) { return Get(key); } template const D& HashTable::operator[] (const K& key) const { return Get(key); } // constructors template HashTable ::HashTable (size_t n, bool prime) : numBuckets_(n), bucketVector_(0), hashObject_(), prime_(prime) { // ensure at least 2 buckets if (numBuckets_ < 3) numBuckets_ = 2; // optionally convert to prime number of buckets if (prime_) numBuckets_ = fsu::PrimeBelow(numBuckets_); // create buckets bucketVector_.SetSize(numBuckets_); } template HashTable ::HashTable (size_t n, H hashObject, bool prime) : numBuckets_(n), bucketVector_(0), hashObject_(hashObject), prime_(prime) { // ensure at least 2 buckets if (numBuckets_ < 3) numBuckets_ = 2; // optionally convert to prime number of buckets if (prime_) numBuckets_ = fsu::PrimeBelow(numBuckets_); // create buckets bucketVector_.SetSize(numBuckets_); } // copies template HashTable ::HashTable (const HashTable& ht) : numBuckets_(ht.numBuckets_), bucketVector_(ht.bucketVector_), hashObject_(ht.hashObject_) {} template HashTable& HashTable ::operator = (const HashTable& ht) { if (this != &ht) { numBuckets_ = ht.numBuckets_; bucketVector_ = ht.bucketVector_; hashObject_ = ht.hashObject_; } return *this; } // other public methods template HashTable ::~HashTable () { Clear(); } template void HashTable::Rehash (size_t nb) { if (nb == 0) nb = Size(); HashTable newTable(nb,hashObject_,prime_); for (size_t i = 0; i < numBuckets_; ++i) { while (!bucketVector_[i].Empty()) // pop as we go saves local space bloat { newTable.Insert(bucketVector_[i].Back().key_,bucketVector_[i].Back().data_); bucketVector_[i].PopBack(); } } fsu::Swap(numBuckets_,newTable.numBuckets_); bucketVector_.Swap(newTable.bucketVector_); } template void HashTable::Clear () { for (size_t i = 0; i < numBuckets_; ++i) bucketVector_[i].Clear(); } template HashTableIterator HashTable::Begin () const { // fsu::debug("Begin()"); HashTableIterator i; i.tablePtr_ = this; i.bucketNum_ = 0; while (i.bucketNum_ < numBuckets_ && bucketVector_[i.bucketNum_].Empty()) ++i.bucketNum_; // now we either have the first non-empty bucket or we've exhausted the bucket numbers if (i.bucketNum_ < numBuckets_) i.bucketItr_ = bucketVector_[i.bucketNum_].Begin(); else { i.bucketNum_ = 0; i.bucketItr_ = bucketVector_[i.bucketNum_].End(); } return i; } template HashTableIterator HashTable::End () const { // fsu::debug("End()"); HashTableIterator i; i.tablePtr_ = this; i.bucketNum_ = numBuckets_ - 1; i.bucketItr_ = bucketVector_[i.bucketNum_].End(); return i; } template size_t HashTable::Size () const { size_t size(0); for (size_t i = 0; i < numBuckets_; ++i) size += bucketVector_[i].Size(); return size; } template bool HashTable::Empty () const { for (size_t i = 0; i < numBuckets_; ++i) if (!bucketVector_[i].Empty()) return 0; return 1; } template void HashTable::Dump (std::ostream& os, int c1, int c2) const { typename BucketType::ConstIterator i; for (size_t b = 0; b < numBuckets_; ++b) { os << "b[" << b << "]:"; for (i = bucketVector_[b].Begin(); i != bucketVector_[b].End(); ++i) os << ' ' << std::setw(c1) << (*i).key_ << ':' << std::setw(c2) << (*i).data_; os << ' '; } } // private helper template size_t HashTable ::Index (const K& k) const { return hashObject_ (k) % numBuckets_; } //-------------------------------------------- // HashTableIterator //-------------------------------------------- template HashTableIterator::HashTableIterator () : tablePtr_(0), bucketNum_(0), bucketItr_() {} template HashTableIterator::HashTableIterator (const Iterator& i) : tablePtr_(i.tablePtr_), bucketNum_(i.bucketNum_), bucketItr_(i.bucketItr_) {} template HashTableIterator & HashTableIterator::operator = (const Iterator& i) { if (this != &i) { tablePtr_ = i.tablePtr_; bucketNum_ = i.bucketNum_; bucketItr_ = i.bucketItr_; } return *this; } template HashTableIterator & HashTableIterator::operator ++ () { // TBS return *this; } template HashTableIterator HashTableIterator::operator ++ (int) { HashTableIterator i = *this; operator ++(); return i; } /* Note: the following would be in Iterator, which would differ from ConstIterator by (1) the underlying bucketItr_ would not be const (2) adding Begin() and End() support (3) adding this non-const dereference template Entry& HashTableIterator::operator * () { if (!Valid()) { std::cerr << "** HashTableIterator error: invalid dereference "; exit (EXIT_FAILURE); } return *bucketItr_; } */ template const Entry& HashTableIterator::operator * () const { if (!Valid()) { std::cerr << "** HashTableIterator error: invalid dereference "; exit (EXIT_FAILURE); } return *bucketItr_; } template bool HashTableIterator::operator == (const Iterator& 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 HashTableIterator::operator != (const Iterator& i2) const { return !(*this == i2); } template bool HashTableIterator::Valid () const { if (tablePtr_ == 0) return 0; if (bucketNum_ >= tablePtr_->numBuckets_) return 0; return bucketItr_ != tablePtr_->bucketVector_[bucketNum_].End(); } // The stub implementations below should remain as-is. // They will be implemented as a project in COP4531. template size_t HashTable::MaxBucketSize () const { std::cout << " ** MaxBucketSize not implemented "; return 0; } template void HashTable::Analysis (std::ostream& os) const { os << " ** Analysis not implemented "; } // Analysis } #endif
Explanation / Answer
I checked your code.. it is very complexity .. and hard to ubnderstand.
Here i giving some easy way to solve hashing in c++. I used linear probing technique
---------------------------------------------------------------------------------------------------------------------------------------
class HashTable {
private:
//variables declared
int HashKey;
int Hashvalue;
public:
//constructor declared
HashTable(int HashKey, int Hashvalue) {
this->HashKey = HashKey;
this->Hashvalue = Hashvalue;
}
/*Getter Setter methods*/
int getHashKey() {
return HashKey;
}
int getHashValue() {
return Hashvalue;
}
};
-------------------------------------------------------------------------------------------------------------------------------------
const int HashBucketSize = 128;
class Hashing {
private:
/*New hashtable object created*/
HashTable **hashingTable;
public:
/*Constructor declared*/
Hashing() {
hashingTable = new HashTable*[HashBucketSize];
for (int i = 0; i < HashBucketSize; i++)
hashingTable[i] = NULL;
}
/*Searching hash value through key*/
int get(int HashKey) {
/*Getting bucket size*/
int hash = (HashKey % HashBucketSize);
/*Searching with key in that bucket*/
while (hashingTable[hash] != NULL && hashingTable[hash]->getHashKey() != HashKey)
hash = (hash + 1) % HashBucketSize;
if (hashingTable[hash] == NULL)
return -1;
else
return hashingTable[hash]->getHashValue();
}
/*Storing new key value pair .. using linear probing hashing technique*/
void put(int HashKey, int Hashvalue) {
int hash = (HashKey % HashBucketSize);
while (hashingTable[hash] != NULL && hashingTable[hash]->getHashKey() != HashKey)
hash = (hash + 1) % HashBucketSize;
if (hashingTable[hash] != NULL)
delete hashingTable[hash];
hashingTable[hash] = new HashTable(HashKey, Hashvalue);
}
/*Destructor declaring*/
~Hashing() {
for (int i = 0; i < HashBucketSize; i++)
if (hashingTable[i] != NULL)
delete hashingTable[i];
delete[] hashingTable;
}
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.