|
Quick Links: |
Provide a namespace for hash functions. More...
| bsl::hash | hash function for fundamental types |
bsl::hash, implementing the std::hash functor. bsl::hash applies a C++ standard compliant, implementation defined, hash function to fundamental types returning the result of such application. h are: size_t value between 0 and numeric_limits<std::size_t>max(). k. For multiple evaluations with the same argument k, the value returned must be always the same. TYPE, for which operator== is defined, and we want to be able to quickly look up whether an element is in the array, without exhaustively applying operator== to all the elements in sequence. The array itself is guaranteed not to change for the duration of our interest in it. buckets. We do not need to copy the values into our own area, so we don't have to create storage for them, or require that a copy constructor or destructor be available. We only require that they have a transitive, symmetric equivalence operation bool operator== and that a hash function be provided. size_t value that will be very randomized. Ideally, the slightest change in the value of the TYPE object will result in a large change in the value returned by the hash function. In a good hash function, typically half the bits of the return value will change for a 1-bit change in the hashed value. We then use the result of the hash function to index into our array of buckets. Each bucket is simply a pointer to a value in our original array of TYPE objects. We will resolve hash collisions in our array through linear probing, where we will search consecutive buckets following the bucket where the collision occurred, testing occupied buckets for equality with the value we are searching on, and concluding that the value is not in the table if we encounter an empty bucket before we encounter one referring to an equal element. HashCrossReference template class, with the two type parameters TYPE" (the type being referenced and HASHER, which defaults to bsl::hash<TYPE>. For common types of TYPE such as int, a specialization of bsl::hash is already defined: template <class TYPE, class HASHER = bsl::hash<TYPE> > class HashCrossReference { // This table leverages a hash table to provide a fast lookup of an // external, non-owned, array of values of configurable type. // // The only requirement for 'TYPE' is that it have a transitive, // symmetric 'operator==' function. There is no requirement that it // have any kind of creator defined. // // The 'HASHER' template parameter type must be a functor with a // function of the following signature: //.. // size_t operator()(const TYPE) const; or // size_t operator()(const TYPE&) const; or //.. // and 'HASHER' must have a publicly available default constructor and // destructor. // DATA const TYPE *d_values; // Array of values table is to // cross-reference. Held, not // owned. size_t d_numValues; // Length of 'd_values'. const TYPE **d_bucketArray; // Contains pointers into // 'd_values'. size_t d_bucketArrayMask; // Will always be '2^N - 1'. HASHER d_hasher; bool d_valid; // Object was properly // initialized. bslma::Allocator *d_allocator_p; // Held, not owned. private: // PRIVATE ACCESSORS bool lookup(size_t *index, const TYPE& value, size_t hashValue) const // Look up the specified 'value', having hash value 'hashValue', // and return its index in 'd_bucketArray' stored in the specified // 'index'. If not found, return the vacant entry in // 'd_bucketArray' where it should be inserted. Return 'true' if // 'value' is found and 'false' otherwise. { const TYPE *ptr; for (*index = hashValue & d_bucketArrayMask; static_cast<bool>(ptr = d_bucketArray[*index]); *index = (*index + 1) & d_bucketArrayMask) { if (value == *ptr) { return true; // RETURN } } // value was not found in table return false; } // NOT IMPLEMENTED HashCrossReference(const HashCrossReference&); HashCrossReference& operator=(const HashCrossReference&); public: // CREATORS HashCrossReference(const TYPE *valuesArray, size_t numValues, bslma::Allocator *basicAllocator = 0) // Create a hash table refering to the specified 'valuesArray' // containing the specified 'numValues' elements. Optionally // specify 'basicAllocator' or the default allocator will be used. : d_values(valuesArray) , d_numValues(numValues) , d_hasher() , d_valid(true) , d_allocator_p(bslma::Default::allocator(allocator)) { size_t bucketArrayLength = 4; while (bucketArrayLength < numValues * 4) { bucketArrayLength *= 2; BSLS_ASSERT_OPT(bucketArrayLength); } d_bucketArrayMask = bucketArrayLength - 1; d_bucketArray = (const TYPE **) d_allocator_p->allocate( bucketArrayLength * sizeof(TYPE **)); memset(d_bucketArray, 0, bucketArrayLength * sizeof(TYPE *)); for (unsigned i = 0; i < numValues; ++i) { const TYPE& value = d_values[i]; size_t idx; if (lookup(&idx, value, d_hasher(value))) { // Duplicate value. Fail. printf("Error: entries %u and %u have the same value\n", i, unsigned(d_bucketArray[idx] - d_values)); d_valid = false; // don't return, continue reporting other redundant // entries. } else { d_bucketArray[idx] = &d_values[i]; } } } ~HashCrossReference() // Free up memory used by this cross-reference. { d_allocator_p->deallocate(d_bucketArray); } // ACCESSORS int count(const TYPE& value) const // Return 1 if the specified 'value' is found in the cross // reference and 0 otherwise. { BSLS_ASSERT_OPT(d_valid); size_t idx; return lookup(&idx, value, d_hasher(value)); } bool isValid() const // Return 'true' if this cross reference was successfully // constructed and 'false' otherwise. { return d_valid; } };
main, we will first use our cross-reference to cross-reference a collection of integer values. We define our array and take its length: const int ints[] = { 23, 42, 47, 56, 57, 61, 62, 63, 70, 72, 79 }; enum { NUM_INTS = sizeof ints / sizeof *ints };
hcri and verify it constructed properly. Note that we don't specify the second template parameter HASHER and let it default to bsl::hash<int>, which is already defined by bslstl_hash: HashCrossReference<int> hcri(ints, NUM_INTS); assert(hcri.isValid());
hcri to verify numbers that were and were not in the collection: assert(1 == hcri.count(23)); assert(1 == hcri.count(42)); assert(1 == hcri.count(47)); assert(1 == hcri.count(56)); assert(0 == hcri.count( 3)); assert(0 == hcri.count(31)); assert(0 == hcri.count(37)); assert(0 == hcri.count(58));
bsl::hash for a custom class. We can use the modular hashing system implemented in bslh rather than explicitly specializing bsl::hash. We will re-use the HashCrossReference template class defined in Example 1. Point, a class that allows us to identify a location on a two dimensional Cartesian plane. class Point { // This class is a value-semantic type that represents a two- // dimensional location on a Cartesian plane. private: int d_x; int d_y; double d_distToOrigin; // This value will be accessed a lot, so we // cache it rather than recalculating every // time. public: Point (int x, int y); // Create a 'Point' with the specified 'x' and 'y' coordinates double distanceToOrigin(); // Return the distance from the origin (0, 0) to this point.
operator== as a friend so that we will be able to compare two points. friend bool operator==(const Point &left, const Point &right);
hashAppend as a friend so that we will be able hash a Point. template <class HASH_ALGORITHM> friend void hashAppend(HASH_ALGORITHM &hashAlg, const Point &point); // Apply the specified 'hashAlg' to the specified 'point' }; Point::Point(int x, int y) : d_x(x) , d_y(y) { d_distToOrigin = sqrt(static_cast<double>(d_x) * d_x + static_cast<double>(d_y) * d_y); } double Point::distanceToOrigin() { return d_distToOrigin; }
operator==. Notice how it only checks salient attributesd_distToOrigin which is not required to determine equality. bool operator==(const Point &left, const Point &right) { return (left.d_x == right.d_x) && (left.d_y == right.d_y); }
hashAppend. This method will allow any hashing algorithm to be applied to Point. This is the extent of the work that needs to be done by type creators. They do not need to implement any algorithms, they just need to call out the salient attributes (which have already been determined by operator==) by calling hashAppend on them. template <class HASH_ALGORITHM> void hashAppend(HASH_ALGORITHM &hashAlg, const Point &point) { using ::BloombergLP::bslh::hashAppend; hashAppend(hashAlg, point.d_x); hashAppend(hashAlg, point.d_y); }
Box, that has a Point as one of its salient attributes. class Box { // This class is a value-semantic type that represents a box drawn on // to a Cartesian plane. private: Point d_position; int d_length; int d_width; public: Box(Point position, int length, int width); // Create a box with the specified 'length' and 'width', with its // upper left corner at the specified 'position'
operator== and hashAppend as we did before. friend bool operator==(const Box &left, const Box &right); template <class HASH_ALGORITHM> friend void hashAppend(HASH_ALGORITHM &hashAlg, const Box &box); // Apply the specified 'hashAlg' to the specified 'box' }; Box::Box(Point position, int length, int width) : d_position(position), d_length(length), d_width(width) { }
operator==. This time all of the data members contribute to equality. bool operator==(const Box &left, const Box &right) { return (left.d_position == right.d_position) && (left.d_length == right.d_length) && (left.d_width == right.d_width); }
hashAppend for Box. Notice how as well as calling hashAppend on fundamental types, we can also call it on our user-defined type Point. Calling hashAppend on Point will propagate the hashing algorithm functor hashAlg down to the fundamental types that make up Point, and those types will then be passed into the algorithm functor. template <class HASH_ALGORITHM> void hashAppend(HASH_ALGORITHM &hashAlg, const Box &box) { hashAppend(hashAlg, box.d_position); hashAppend(hashAlg, box.d_length); hashAppend(hashAlg, box.d_width); }
Box. We create an array of unique Boxs and take its length: Box boxes[] = { Box(Point(0, 0), 2, 3),
Box(Point(1, 0), 1, 1),
Box(Point(0, 1), 1, 5),
Box(Point(1, 1), 5, 6),
Box(Point(2, 1), 1, 13),
Box(Point(0, 4), 3, 3),
Box(Point(3, 2), 2, 17) };
enum { NUM_BOXES = sizeof boxes / sizeof *boxes };
hcrsts and verify that it constructed properly. Note we don't pass a second parameter template argument and let HASHER default to bsl::hash<TYPE>. Since we have not specialized bsl::hash for Box, bsl::hash<TYPE> will attempt to use bslh::hash<> to hash Box. HashCrossReference<Box> hcrsts(boxes, NUM_BOXES);
ASSERT(hcrsts.isValid());
for(int i = 0; i < NUM_BOXES; ++i) { ASSERT(1 == hcrsts.count(boxes[i])); }
ASSERT(0 == hcrsts.count(Box(Point(3, 3), 3, 3)));
ASSERT(0 == hcrsts.count(Box(Point(3, 2), 1, 0)));
ASSERT(0 == hcrsts.count(Box(Point(1, 2), 3, 4)));
ASSERT(0 == hcrsts.count(Box(Point(33, 23), 13, 3)));
ASSERT(0 == hcrsts.count(Box(Point(30, 37), 34, 13)));
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< bool >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< bool >::operator() | ( | bool | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< char >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< char >::operator() | ( | char | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< signed char >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< signed char >::operator() | ( | signed char | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< unsigned char >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< unsigned char >::operator() | ( | unsigned char | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< wchar_t >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< wchar_t >::operator() | ( | wchar_t | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< short >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< short >::operator() | ( | short | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< unsigned short >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< unsigned short >::operator() | ( | unsigned short | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< int >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< int >::operator() | ( | int | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< unsigned int >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< unsigned int >::operator() | ( | unsigned int | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< long >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< long >::operator() | ( | long | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< unsigned long >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< unsigned long >::operator() | ( | unsigned long | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< long long >::~hash | ( | ) | [inherited] |
Destroy this object.
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< long long >::operator() | ( | long long | x | ) | const [inherited] |
Return a hash value computed using the specified x.
Create a hash object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| bsl::hash< unsigned long long >::~hash | ( | ) | [inherited] |
Destroy this object.
| hash& bsl::hash< unsigned long long >::operator= | ( | const hash< unsigned long long > & | rhs | ) | [inherited] |
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. Note that as hash is an empty (stateless) type, this operation has no observable effect.
| std::size_t bsl::hash< unsigned long long >::operator() | ( | unsigned long long | x | ) | const [inherited] |
Return a hash value computed using the specified x.
1.7.1