//
// Created by YUQIONG LI on 13/9/2018.
//
#ifndef HASHMAP_HASHTABLE_H
#define HASHMAP_HASHTABLE_H
template<>
class hash<string>{
public:
size_t operator()( const string & key){
size_t hashVal;
for (char ch: key){
hashVal = 37 * hashVal + ch;
}
return hashVal;
}
};
template <typename HashedObj>
class HashTable {
public:
explicit HashTable(int size = 101);
bool contains(const HashedObj & x) const; // a member function, cannot change
void makeEmpty();
bool insert(const HashedObj & x);
bool insert(HashedObj && x);
bool remove(const HashedObj & x);
private:
vector< list<HashedObj> > theLists;
int currentSize;
void rehash();
size_t myhash(const HashedObj & x) const;
};
size_t HashTable::myhash(const HashedObj & x) const {
static hash<HashedObj> hf; // declare and initialize a hash function
return hf(x) % theList.size(); // scale down the output
}
void HashTable::makeEmpty(){
for (auto & thisList : theList){
thisList.clear();
}
}
bool HashTable::contains(const HashedObj & x) const {
auto & whichList = theLists[myhash(x)]; // find the list to look for. Note the grammar
return find( begin(whichList), end(whichList), x) != end( whichList);
}
bool remove( const HashObject & x){
auto & whichList = theLists[myhash(x)];
auto itr = find(begin(whichList), end(whichList), x);
if (itr == end(whichList))
return false;
whichList.erase( itr );
--currentSize;
return true;
}
#endif //HASHMAP_HASHTABLE_H
First trial.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.