mCRL2
Searching...
No Matches
hash_utility.h
Go to the documentation of this file.
1// Author(s): Jan Friso Groote
2// Copyright: see the accompanying file COPYING or copy at
3// https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4//
6// (See accompanying file LICENSE_1_0.txt or copy at
8//
9
18#ifndef MCRL2_UTILITIES_HASH_UTILITY_H
19#define MCRL2_UTILITIES_HASH_UTILITY_H
20
21#include <cstddef>
22#include <vector>
23#include <map>
24
25namespace mcrl2
26{
27namespace utilities
28{
29namespace detail
30{
31
32inline std::size_t hash_combine(const std::size_t h1, const std::size_t h2)
33{
34 // This hash function is inpired by boost.
35 return h1 ^ (h2 + 0x9e3779b9 + (h1<<6) + (h1>>2));
36}
37
39inline std::size_t hash_combine_cheap(const std::size_t seed, const std::size_t hash_number)
40{
41 // Addition works better than xor, because xor maps equal inputs to 0 which
42 // can lead to many collisions. However, with addition we also want to prevent
43 // symmetry, i.e a + b equals b + a, so a relative cheap solution is to multiply
44 // one side by a number. For this purpose we chose hnr + floor(2.5 * seed);
45 return hash_number + (seed << 1) + (seed >> 1);
46}
47
48} //end namespace detail
49} //end namespace utilities
50} //end namespace mcrl2
51
52namespace std
53{
54
55template <class X>
56struct hash< std::vector < X > >
57{
58 std::size_t operator()(const std::vector < X >& v) const
59 {
60 hash<X> hasher;
61 // This follows boost.
62 std::size_t hash=0;
63 for(const X& x: v)
64 {
66 }
67 return hash;
68 }
69};
70
71template <class X, class Y>
72struct hash< std::map < X, Y > >
73{
74 std::size_t operator()(const std::map < X, Y >& v) const
75 {
76 hash<X> hasher1;
77 hash<Y> hasher2;
78 // This follows boost.
79 std::size_t hash=0;
80 for(const std::pair< X, Y>& p: v)
81 {
84 hasher2(p.second)));
85 }
86 return hash;
87 }
88};
89
90template <class X, class Y>
91struct hash< std::pair < X, Y > >
92{
93 std::size_t operator()(const std::pair < X, Y >& p) const
94 {
95 hash<X> hasher1;
96 hash<Y> hasher2;
97
98 return mcrl2::utilities::detail::hash_combine(hasher1(p.first),hasher2(p.second));
99 }
100};
101
102} // namespace std
103
104
105#endif // MCRL2_UTILITIES_HASH_UTILITY_H
106
107
std::size_t hash_combine(const std::size_t h1, const std::size_t h2)
std::size_t hash_combine_cheap(const std::size_t seed, const std::size_t hash_number)
Auxiliary function to combine seed with a hash number.
A class that takes a linear process specification and checks all tau-summands of that LPS for conflue...
Definition indexed_set.h:72
STL namespace.
std::size_t operator()(const std::map< X, Y > &v) const
std::size_t operator()(const std::pair< X, Y > &p) const
std::size_t operator()(const std::vector< X > &v) const
#define hash(l, r, m)
Definition tree_set.cpp:23