• Choose a category
• All
• Classic-Fiction

By Root 1124 0

string object, and not just of the actual text. The result is that two string objects with the same text will generate different hash values, because some fields of the string objects will be different. Therefore, it’s a good idea to provide a specialization of the DefaultHash class for strings. Template specialization is discussed in detail in Chapter 19:

// Specialization for strings

template <>

class DefaultHash

{

public:

// Throws invalid_argument if numBuckets is illegal

DefaultHash(size_t numBuckets = 101) throw (invalid_argument);

size_t hash(const string& key) const;

size_t numBuckets() const { return mNumBuckets; }

protected:

size_t mNumBuckets;

};

Code snippet from Hashmap\BasicHashmap\hashmap.h

// Throws invalid_argument if numBuckets is illegal

DefaultHash::DefaultHash(size_t numBuckets) throw (invalid_argument)

{

if (numBuckets <= 0) {

throw invalid_argument("numBuckets must be > 0");

}

mNumBuckets = numBuckets;

}

// Uses the division method for hashing after summing the

// ASCII values of all the characters in key.

size_t DefaultHash::hash(const string& key) const

{

size_t sum = 0;

for (size_t i = 0; i < key.size(); i++) {

sum += (unsigned char)key[i];

}

return (sum % mNumBuckets);

}

Code snippet from Hashmap\BasicHashmap\hashmap.cpp

If the client wants to use other pointer types or objects as the key, she should write her own hash class for those types.

The hash functions shown in this section are examples for the basic hashmap implementation. They do not guarantee uniform hashing for all key universes. If you need more mathematically rigorous hash functions, or if you don’t know what “uniform hashing” is, consult an algorithms reference from Appendix B.

The Hashmap Interface

A hashmap supports three basic operations: insertion, deletion, and lookup. Of course, it provides a constructor, destructor, copy constructor, and copy assignment operator as well. With C++11 it should also support a move constructor and move assignment operator. Here is the public portion of the hashmap class template:

template ,

typename Hash = DefaultHash>

class hashmap

{

public:

typedef Key key_type;

typedef T mapped_type;

typedef pair value_type;

// Constructors

// Throws invalid_argument if the hash object specifies an illegal

// number of buckets

explicit hashmap(const Compare& comp = Compare(),

const Hash& hash = Hash()) throw(invalid_argument);

// destructor, copy constructor, move constructor,

// copy assignment operator and move assignment operator

~hashmap();

hashmap(const hashmap& src);

hashmap(hashmap&& src); // C++11

hashmap& operator=(

const hashmap& rhs);

hashmap& operator=(

hashmap&& rhs); // C++11

// Inserts the key/value pair x

void insert(const value_type& x);

// Removes the element with key x, if it exists

void erase(const key_type& x);

// find returns a pointer to the element with key x.

// Returns nullptr if no element with that key exists.

value_type* find(const key_type& x);

// operator[] finds the element with key x or inserts an

// element with that key if none exists yet. Returns a reference to

// the value corresponding to that key.

T& operator[] (const key_type& x);

protected:

// Implementation details not shown yet

};

Code snippet from Hashmap\BasicHashmap\hashmap.h

As you can see, the key and value types are both template arguments like in the STL map. The hashmap stores pair as the actual elements in the container. The insert(), erase(), find(), and operator[] methods are straightforward. However, a few aspects of this interface require further explanation.

The Template Argument Compare

Like the map, set, and other standard containers, the hashmap allows the client to specify the comparison type as a template parameter and to pass a specific comparison object of