Hello.
I have a few Qs about Hash tables.
how does std::hash
return a std::size_t
? for example how does it convert a std::string("Hello")
to std::size_t
?
How do these functions work? i have no idea what's hash_combine
and seed
do in hashval.hpp
This is from STL 2nd edition.
hashval.hpp
#include <functional>
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html
template <typename T>
inline void hash_combine (std::size_t& seed, const T& val)
{
seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T>
inline void hash_val (std::size_t& seed, const T& val)
{
hash_combine(seed,val);
}
template <typename T, typename... Types>
inline void hash_val (std::size_t& seed,
const T& val, const Types&... args)
{
hash_combine(seed,val);
hash_val(seed,args...);
}
// auxiliary generic function to create a hash value out of a heterogeneous list of arguments
template <typename... Types>
inline std::size_t hash_val (const Types&... args)
{
std::size_t seed = 0;
hash_val (seed, args...);
return seed;
}
main.cpp
#include <unordered_set>
#include <string>
#include <iostream>
#include "hashval.hpp"
#include "print.hpp"
using namespace std;
class Customer {
private:
string fname;
string lname;
long no;
public:
Customer (const string& fn, const string& ln, long n)
: fname(fn), lname(ln), no(n) {}
friend ostream& operator << (ostream& strm, const Customer& c) {
return strm << "[" << c.fname << "," << c.lname << ","
<< c.no << "]";
}
friend class CustomerHash;
friend class CustomerEqual;
};
class CustomerHash
{
public:
std::size_t operator() (const Customer& c) const {
return hash_val(c.fname,c.lname,c.no);
}
};
class CustomerEqual
{
public:
bool operator() (const Customer& c1, const Customer& c2) const {
return c1.no == c2.no;
}
};
int main()
{
// unordered set with own hash function and equivalence criterion
unordered_set<Customer,CustomerHash,CustomerEqual> custset;
custset.insert(Customer("nico","josuttis",42));
PRINT_ELEMENTS(custset);
}
This line is most confused one.seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed<<6) + (seed>>2)
Is it worth of implementing a Hash table from scratch while we have Unordered Associative containers(since c++11)?
What are the advantages of using custom Hash function with Unordered containers ?
I'm sorry if the Qs are total n00b.
I appreciate your help.